Non-Deterministic Finite Automatons (NFAs)

COMP218 Tutorials 2021-10-08

1. Consider the following automaton:

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

   2. You can take the following route:

   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:

   1. You can take the following route:

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

      	$a$	$b$
      $1$	$\{2,3\}$	$\mathrm{\varnothing }$
      $\{2,3\}$	$\mathrm{\varnothing }$	$\{3,1\}$
      $\mathrm{\varnothing }$	$\mathrm{\varnothing }$	$\mathrm{\varnothing }$
      $\{1,3\}$	$\{2,3\}$	$1$

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

   1. NFA diagram:

   2. DFA diagram:

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

   1. NFA diagram:

   2. DFA diagram:

5. Consider the following NFA:

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