Equivalences in Finite Automata

Key Concept

• Non-deterministic Finite Automaton (NFA) and Deterministic Finite Automaton (DFA) recognize the same class of languages, specifically regular languages.

Theorem 1: DFA/NFA Equivalence

• Statement: Every NFA has an equivalent DFA.
• Proof:
  • Construct DFA ( M ) from NFA ( N ) without ( \epsilon ) transitions:
    • States ( Q' ) of ( M ) are the powerset of states of ( N ).
    • Transition function: For ( S \subseteq Q ), ( a \in \Sigma ), new state includes all possible states from ( S ) on input ( a ).
    • Start state of ( M ) corresponds to the set containing the start state of ( N ).
    • Accepting states of ( M ) include those containing any accepting state of ( N ).
  • Extend construction to include ( \epsilon ) transitions:
    • Define reachable states from any state using ( \epsilon ) transitions.
    • Update transition function accordingly.
• Conclusion: DFA simulates NFA, establishing equivalence.

Example

• Consider an NFA that recognizes strings over alphabet ( {a, b} ) with at least two occurrences of ( b ) and ending with ( b ).
• State ( q_0 ) in NFA has two transitions for ( b ), making it non-deterministic.
• Convert this NFA to an equivalent DFA following the construction in Theorem 1.

DFA Construction Result

• The conversion produces a DFA that is not necessarily minimal in terms of number of states.
• Some states in the constructed DFA may not be reachable.
• Questions to consider:
  • How to identify unreachable states?
  • Is removing unreachable states sufficient for minimizing DFA?

Corollary 1

• A language is regular if it is recognized by some NFA (and hence by a DFA).
  • This follows directly from Theorem 1.