DFA-NFA Equivalence

1. From DFA to NFA: The Easy Direction

Let's start with the more straightforward part of the proof: showing that for any given DFA, there's an NFA that accepts the same language.

Intuitively, this makes sense because a DFA is essentially a very restricted type of NFA. It's an NFA that happens to have:

• No $ϵ$-transitions.
• Exactly one outgoing transition from every state for each symbol in the alphabet.

To formalize this, we just need to show how to represent a DFA's components in the NFA's format. The key difference lies in the transition function.

• A DFA's transition function, ${\delta }_{DFA}$, maps a state and a symbol to a single state: ${\delta }_{DFA}:Q\times \Sigma \to Q$.
• An NFA's transition function, ${\delta }_{NFA}$, maps a state and a symbol to a set of states: ${\delta }_{NFA}:Q\times (\Sigma \cup \{ϵ\})\to \mathcal{P}(Q)$.

The following video explains this relationship clearly.

To complete the formal conversion, we can construct an NFA $N=(Q_N,\Sigma ,{\delta }_N,q_{0N},F_N)$ from a DFA $D=(Q_D,\Sigma ,{\delta }_D,q_{0D},F_D)$ as follows:

• $Q_N=Q_D$
• $q_{0N}=q_{0D}$
• $F_N=F_D$
• For every state $q\in Q_D$ and symbol $a\in \Sigma$, if ${\delta }_D(q,a)=p$, we define ${\delta }_N(q,a)=\{p\}$.
• For any state $q\in Q_N$, ${\delta }_N(q,ϵ)=\varnothing$.

Since the constructed NFA $N$ perfectly mimics the single path of the DFA $D$ for any input string, it accepts the exact same language. This completes the first part of our proof.

2. From NFA to DFA: The Subset Construction Revisited

Now for the more involved direction: proving that for any NFA, there's a DFA that accepts the same language. In the previous lesson, you learned the algorithm for this: the subset construction. Now, we will use it as the basis for our formal proof.

The core insight, as you know, is to create a DFA whose states correspond to sets of the NFA's states. This allows the DFA to deterministically track all parallel computations occurring in the NFA.

Let's watch a concise, high-level explanation of this idea, which will serve as a great warm-up for the formal proof.

The Formal Construction and Proof of Correctness

The video laid out the construction. Now, let's dive into the formal proof that this construction is correct. This is where your appreciation for mathematical rigor will be valuable. We will prove that the language of the constructed DFA is identical to the language of the original NFA.

The following resource provides a concise but complete proof. We will walk through its logic step by step.

Let's break down the proof from the notes.

The proof uses induction on the length of the input string $w$. This is a natural strategy because the machine's operation is defined step-by-step, symbol by symbol.

Let our NFA be $N=(Q,\Sigma ,\delta ,q_0,F)$ and our constructed DFA be $D=(Q^{\prime },\Sigma ,{\delta }^{\prime },q_0^{\prime },F^{\prime })$.

• Let ${\hat{\delta }}^{\prime }(q_0^{\prime },w)$ denote the state the DFA $D$ is in after reading string $w$.
• Let $\hat{\Delta }(q_0,w)$ denote the set of states the NFA $N$ can be in after reading string $w$. (The notes use $\hat{\Delta }$ for the NFA's extended transition to avoid confusion with the DFA's $\delta$).

The core claim we want to prove is:
$\forall w\in {\Sigma }^{\ast },{\hat{\delta }}^{\prime }(q_0^{\prime },w)=\hat{\Delta }(q_0,w)$
This claim states that the single state our DFA reaches after reading $w$ is exactly the set of all possible states the NFA could have reached. If we prove this, the equivalence of the languages follows directly.

1. Base Case: $|w|=0$

• Here, $w=ϵ$.
• For the DFA, ${\hat{\delta }}^{\prime }(q_0^{\prime },ϵ)=q_0^{\prime }$ by definition. By construction, $q_0^{\prime }=\hat{\Delta }(q_0,ϵ)$ (which is the $ϵ$-closure of the NFA's start state).
• For the NFA, the set of states it can reach from $q_0$ on $ϵ$ is, by definition, $\hat{\Delta }(q_0,ϵ)$.
• So, the statement holds for $w=ϵ$.

2. Inductive Step

• Inductive Hypothesis (I.H.): Assume the claim holds for all strings $u$ of length $n$. That is, ${\hat{\delta }}^{\prime }(q_0^{\prime },u)=\hat{\Delta }(q_0,u)$.
• Goal: We must show it holds for any string $w=ua$ of length $n+1$, where $a\in \Sigma$.
• Let's analyze the DFA's state after reading $ua$:
  ${\hat{\delta }}^{\prime }(q_0^{\prime },ua)={\delta }^{\prime }({\hat{\delta }}^{\prime }(q_0^{\prime },u),a)(\text{by definition of }{\hat{\delta }}^{\prime })$
• Using our I.H., we can substitute $\hat{\Delta }(q_0,u)$ for ${\hat{\delta }}^{\prime }(q_0^{\prime },u)$:
  $={\delta }^{\prime }(\hat{\Delta }(q_0,u),a)$
• Now, we use the definition of our constructed transition function ${\delta }^{\prime }$:
  $={\bigcup }_{q\in \hat{\Delta }(q_0,u)}\hat{\Delta }(q,a)$
• This final expression is precisely the definition of $\hat{\Delta }(q_0,ua)$—the set of all states reachable from the start by reading $u$ and then $a$.
• Thus, ${\hat{\delta }}^{\prime }(q_0^{\prime },ua)=\hat{\Delta }(q_0,ua)$. The claim holds for strings of length $n+1$.

By induction, the claim is true for all strings $w$.

Why does this prove language equivalence?
A string $w$ is accepted by the DFA $D$ if ${\hat{\delta }}^{\prime }(q_0^{\prime },w)\in F^{\prime }$. By our construction, a state $S\in F^{\prime }$ if and only if $S\cap F\ne \varnothing$.
Since we just proved ${\hat{\delta }}^{\prime }(q_0^{\prime },w)=\hat{\Delta }(q_0,w)$, the DFA accepts $w$ if and only if $\hat{\Delta }(q_0,w)\cap F\ne \varnothing$. This is the exact condition for the NFA to accept $w$.

Therefore, $L(D)=L(N)$.

Conclusion: The Power of Equivalence

Today, you have formally proven one of the most important theorems in the first part of this course. By showing a constructive path from any DFA to an NFA and, more significantly, from any NFA back to a DFA, you have established that these two models of computation are equivalent in power.

Key Takeaways:

• Equivalence is a Two-Way Street: To prove two models are equivalent, you must show that each can simulate the other.
• DFA $\to$ NFA: This direction is straightforward. A DFA is just a specialized NFA where each transition leads to a singleton set and there are no $ϵ$-moves.
• NFA $\to$ DFA: This direction is proven using the subset construction. The proof relies on induction on the input string's length to show that the DFA state after reading a string is identical to the set of possible states the NFA could be in.
• The Class of Regular Languages: This equivalence establishes that the set of languages recognized by DFAs is the same as that recognized by NFAs. This robust and well-defined class of languages is known as the regular languages.

Preview of the Next Lesson:
We've proven DFAs and NFAs are equivalent in what they can do, but this says nothing about their practical differences. In the next lesson, we will compare the trade-offs between DFAs and NFAs. We'll discuss when to use one over the other, focusing on the trade-off between the number of states (space complexity) and the ease of design and combination.