NFA

NFA

NFA: Non-deterministic finite automata. A 5-tuple (Q, \Sigma, \delta, q_0, F), where

  1. Q is a finite set of states
  2. \Sigma is a finite alphabet
  3. \delta: Q \times \Sigma_\epsilon \to P(Q) is the transition function
  4. q_0 \in Q is the start state, and
  5. F \subseteq Q is the set of accept states.
Example: DFA v.s. NFA

This is a DFA that recognizes 10 over \Sigma = \{ 0 , 1 \}

This is an NFA that does the same thing more succinctly.

Suppose we want to recognize \{ 10, 00, 11 \}, the NFA is simply:

The union operation of three automata is way simpler in NFAs than DFAs, and NFAs are just simpler and less cluttered.

Designing NFAs

  1. Find the essence of the problem
  2. Write test strings
  3. Design only the accepting path.
  4. Test the NFA
Example: Write an NFA that accepts strings where the 3rd-to-last digit is 0. (\Sigma = \{ 0, 1 \})

This NFA can be read as non-deterministically “guessing” to the accepting path.

Example: { w | w starts with 01, has even # of 1s, and ends with 0}

Example: Complement of a Language

Example:

L = { w | w has a # of 1s divisible by 3}

Q: How do we create a DFA to recognize the complement of L?

A: Simply flip the accepting states.

Observations:

Strategies for Flipping an NFA:

  1. You can flip the DFA, or
  2. Write the NFA to find \bar{L} directly.

NFA \to DFA

We can turn any NFA into a DFA.

Steps:

  1. Find the new start state (epsilon closure) E(S) = \text{ \{ q | q is reachable from $S$ via 0 or more $\epsilon$ transitions \} }
  2. Find transitions (only consider reachable subsets from S’, \delta ' (R,a) = \cup_{r \in R} E ( \delta (r,a) ) \\ \small\textit{($\forall R \subseteq Q$)}
  3. Mark accepting states F' = \text{ \{ R | q \in R, TODO \} }

Example

Q: Turn this NFA into a DFA.

A:

Observations:

  1. This NFA starts in either 1 or 3. (E(S) = { 1, 3 })
  2. This is a transition table for the NFA that doesn’t have epsilon (because we’re trying to turn it into a DFA):
a b
1 \phi { 2 }
2 { 2, 3 } { 3 }
3 { 1, 3 } \phi
{ 1, 3 } \phi \cup { 1, 3 } = { 1, 3 } \phi \cup { 2 } = { 2 }
{ 2 } { 2, 3 } { 3 }
{ 3 } { 1, 3 } \phi
{ 2, 3 } { 1, 2, 3 } { 3 }
{ 1, 2, 3 } { 1, 2, 3 } { 2, 3 }

Q: Which ones are accepting?

Q: How many states can the resulting DFA have?

With the transition table, the DFA can now be constructed, starting at state { 1, 3 }.