Non-deterministic Finite Automata (NFA)

In an NFA, δ: Q × (Σ ∪ {ε}) → 2^Q. A state can have zero, one or many moves on a symbol, and ε-moves are allowed. A string is accepted if at least one path ends in a final state.

Key theoremNFAs and DFAs are equally powerful: every NFA has an equivalent DFA. In the worst case an n-state NFA needs 2ⁿ DFA states.

NFA for Strings Ending in "01"

Text

  State  |   0        |  1
 --------+------------+--------
  → q0   |  {q0, q1}  |  {q0}
    q1   |  ∅         |  {q2}
  * q2   |  ∅         |  ∅

NFA for strings ending in 01: q0 guesses where the final 01 begins

Subset Construction

Text

Start with {q0}

  DFA state     |    0         |    1
 ---------------+--------------+------------
  → {q0}        |  {q0, q1}    |  {q0}
    {q0, q1}    |  {q0, q1}    |  {q0, q2}
  * {q0, q2}    |  {q0, q1}    |  {q0}

Any DFA state containing q2 is final.
Renaming A = {q0}, B = {q0,q1}, C = {q0,q2} gives exactly the DFA from the previous lesson.

ε-NFA to NFA/DFA

Compute the ε-closure of each state (all states reachable using only ε-moves). Then δ'(q, a) = ε-closure(δ(ε-closure(q), a)).

Moore and Mealy Machines

Moore	Mealy
Output depends on the state only	Output depends on the state and input
Output length = input length + 1	Output length = input length
Usually needs more states	Usually fewer states

Track your progress through the Theory of Computation course

← Prev Next →