Equivalence of DFA and NFA
Deterministic Finite Automata (DFA) and Non-Deterministic Finite Automata (NFA) are fundamentally equivalent because they recognize exactly the same class of languages—regular languages.
Core Concept of Equivalence
- Two automata are said to be equivalent if they accept the same language, meaning for any input string, both will either accept or reject it together.
- Every DFA is a specific case of NFA where, for each input symbol, there is exactly one transition from any state.
- Conversely, for every NFA, there exists an equivalent DFA that can be constructed using the subset (power-set) construction method.
We naturally try to find the relationship between DFA and NDFA. Intuitively we now feel that:
i. A DFA can simulate the behavior of NDFA by increasing the number of states.
In other words. a DFA (Q, ∑, δ, q0, F) can be viewed as an NDFA (Q, ∑, δ’, q0, F) by defining δ’(q, a) = {δ(q, a)}.
ii. Any NDFA is a more general machine without being more powerful We now give a theorem on the equivalence of DFA and NDFA.
Equivalence of DFA and NFA
| DFA | NFA |
|---|---|
| 1. Only one transition per input symbol | 1. It can have multiple transitions per input symbol |
| 2. Equivalent to NFA | 2. Equivalent to DFA |
| 3. Subset construction: DFA from NFA | 3. Direct simulation and conversion |