Theory of Computation Lecture 5

Equivalence of NFAs and DFAs

• Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA) recognize the same class of languages.
• NFAs may seem more powerful, yet they do not recognize more languages than DFAs.
• Describing an NFA for a language can often be easier than for a DFA.
• Two machines are considered equivalent if they recognize the same language.

Theorems

• Theorem 1.39: Every NFA has an equivalent DFA.
• Corollary 1.40: A language is regular if and only if some NFA recognizes it.

Steps to Convert NFA to DFA

• Step 1: Initialize Q' to the empty set (ϕ).
• Step 2: Add the start state (q0) of the NFA to Q' and determine transitions.
• Step 3: For each input symbol, find possible sets of states. Add new sets to Q' if they are not already present.
• Step 4: In the DFA, all states containing final states of the NFA will also be final states.

Example Conversions

• Construct a transition table from the given NFA to organize state transitions.
• Form δ' transitions for newly identified sets of states based on input symbols.

Example 1 NFA to DFA Conversion

• Initial state processing:
  • δ'([q0], 0) = [q0]
  • δ'([q0], 1) = [q1]
• State q1 yields a new state:
  • δ'([q1], 0) = [q1, q2]
  • δ'([q1], 1) = [q1]
• Final state processing involves states that include q2.
• Transition table and diagram reflect all derived transitions accurately, eliminating unreachable states.

Example 2: NFA with Null Conversion

• ε-closure method identifies the states based on epsilon transitions:
  • ε-closure(q0) = {q0, q1, q2}
• Determine transitions based on ε-closure outputs leading to combinations of states.
• Final state determination includes every state set containing final states (like q2).

Important Notes for NFA to DFA Conversion

• Transition tables must be drawn accurately to represent all possible states and their transitions.
• If the transition from the start state over an input symbol is null, assign it to a dead state in the DFA.
• Final states in the DFA are any state that contains a final state from the NFA.
• Continue adding states and transitions until no new states remain.