Equivalence of NFA and DFA

Main Theorem

Theorem: The class of languages recognised by NFAs equals the class recognised by DFAs.

$L \text{ is NFA-recognisable} \iff L \text{ is DFA-recognisable}$

Proof Outline

DFA $\Rightarrow$ NFA

Every DFA is trivially an NFA where each state-symbol pair has exactly one transition.

NFA $\Rightarrow$ DFA

The subset construction converts any NFA to an equivalent DFA.

Since subset construction preserves language, any NFA-recognisable language is DFA-recognisable.

Extending to NFA-$\varepsilon$

NFA-$\varepsilon$ $\Rightarrow$ NFA

Given NFA-$\varepsilon$ $M = (Q, \Sigma, \Delta, \tau, s, F)$:

Construct NFA $M' = (Q, \Sigma, \Delta', s, F')$ where:

$\Delta' = \{(q, a, q') : \exists q''. q \xrightarrow{\varepsilon^*} q'' \land (q'', a, q') \in \Delta\}$

$F' = F \cup \{q : E(q) \cap F \neq \emptyset\}$

Intuitively: absorb $\varepsilon$-transitions into labelled transitions.

Proof of Correctness

The extended transition relation is preserved:

• In $M$: $q \Rightarrow_w q'$ via labelled and $\varepsilon$-transitions
• In $M'$: $q \xrightarrow{w} q'$ via labelled transitions only

Complete Equivalence

All three models recognise the same languages:

$\text{DFA} \subset \text{NFA} \subset \text{NFA-}\varepsilon$

where each $\subset$ is strict in expressive convenience but equal in language-theoretic power.

The Class: Regular Languages

Definition

A language $L$ is regular if there exists a finite automaton (DFA, NFA, or NFA-$\varepsilon$) that recognises it.

Equivalent Characterisations

$L$ is regular iff any of:

1. $L = L(M)$ for some DFA $M$
2. $L = L(M)$ for some NFA $M$
3. $L = L(M)$ for some NFA-$\varepsilon$ $M$
4. $L = L(R)$ for some regular expression $R$ (Kleene’s theorem)
5. $L$ is generated by a regular grammar
6. $L$ is the language of a syntactic monoid

Practical Implications

For Design

• NFAs are often easier to design (less constrained)
• NFA-$\varepsilon$ enables modular composition
• DFAs have unique minimal form (useful for optimisation)

For Implementation

• DFAs run in $O(|w|)$ time
• NFAs can be simulated in $O(|w| \cdot |Q|)$ time
• Subset construction may cause exponential blowup

For Theory

• Closure properties are easier to prove with NFAs
• Decidability results apply to all three

Closure Properties

Regular languages are closed under:

• Union: disjoint union or NFA-$\varepsilon$ construction
• Concatenation: sequential composition
• Kleene star: loop back construction
• Complement: swap accepting/non-accepting in DFA
• Intersection: product construction on DFAs

---

Summary

• DFA, NFA, and NFA-$\varepsilon$ are equally expressive
• All recognise exactly the regular languages
• Subset construction: NFA $\to$ DFA
• Epsilon elimination: NFA-$\varepsilon$ $\to$ NFA
• Each model has practical advantages