Non-Deterministic Finite Automatons (NFAs)

COMP218 Tutorials 2021-10-08

1. Consider the following automaton:

    stateDiagram-v2
    direction LR
    [*] --> 1
    1 --> 2:a
    1 --> 4:b
    2 --> 3:b
    2 --> 4:b 
    3 --> 6:a
    3 --> 5:c
    4 --> 1:a
    4 --> 3:b
    4 --> 5:a
    5 --> 6:c
    4 --> [*]
    6 --> [*]
   

   1. There are multiple of the same transition going out from the same state.

   2. You can take the following route:

       flowchart LR
       1 -->|1| 2 -->|2| 4 -->|3| 1 -->|4| 4 -->|5| 5 -->|6| 6
      

   3. There is no route to an accepting state. (Go through the path to prove that you’re in a reject state.)

2. Consider the following automaton:

    stateDiagram-v2
    direction LR
    [*] --> 1
    1 --> 2:a
    2:2
    2 --> 3:b
    3 --> 1:b
    1 --> 3:a
   

   1. You can take the following route:

       flowchart LR
       1 -->|1| 3 -->|2| 1 -->|3| 2 -->|4| 3 -->|5|2 -->|6| 1
      

   2. The conversion can be completed with the following table:

      	$a$	$b$
      $1$	$\{2,3\}$	$\emptyset$
      $\{2,3\}$	$\emptyset$	$\{3,1\}$
      $\emptyset$	$\emptyset$	$\emptyset$
      $\{1,3\}$	$\{2,3\}$	$1$

       stateDiagram-v2
       direction LR
       [*] --> 1
       1 --> 2,3:a
       2,3 --> 1,3:b
       1 --> emptyset:b
       emptyset --> emptyset:a, b
       2,3 --> emptyset:a
       1,3 --> 2,3:a
       1,3 --> 1:b
       2,3:2,3
      

3. Language is $\{0,1\}$. End with $00$:

   1. NFA diagram:

       stateDiagram-v2
       direction LR
       [*] --> a
       a --> a:0,1
       a --> b:0
       b --> c:0
       c: c
      

   2. DFA diagram:

       stateDiagram-v2
       direction LR
       [*] --> a
       a --> a,b:0
       a --> a:1
       a,b --> a,b,c:0
       a,b --> a:1
       a,b,c:a,b,c
       a,b,c --> a:1
       a,b,c --> a,b,c:0
      

4. Language is $\{0,1\}$. Contains $01$ as a sub-string:

   1. NFA diagram:

       stateDiagram-v2
       direction LR
       [*] --> a
       a --> a:0,1
       a --> b:0
       b --> c:1
       c --> c:0,1
       c:c
      

   2. DFA diagram:

       stateDiagram-v2
       direction LR
       [*] --> a
       a --> a,b:0
       a --> a:1
       a,b --> a,b:0
       a,b --> a,c:1
       a,c --> a,b,c:0
       a,c --> a,c:1
       a,b,c --> a,b,c:0
       a,b,c --> a,c:1
       a,b,c:a,b,c
       a,c:a,c
      

5. Consider the following NFA:

    stateDiagram-v2
    direction LR
    [*] --> 1 
    1 --> 2:a
    1 --> 3:a
    2 --> [*]
    2 --> 3:b
    3 --> 1:b
   

   This is an alternate notation where the accepting state is the arrow going off.