In my textbook, it presents the theorem, "A language L is accepted by some DFA if and only if l is accepted by some NFA". My textbook explains that the "if" portion of the proof is given by the subset construction and theorem if $D=(Q_D, \sigma, \delta_D, {q0}, F_D)$ is the DFA constructed from NFA $N=(Q_N, \sigma, \delta_N, {q0}, F_N)$ by the subset construction, then L(N) = L(D).

However, it leaves it up to the reader to prove the "only if" portion - essentitally, if $\hat\delta_D(q,a) = p$ then $\hat\delta_N(q,a) = {p}$. It suggests that we mu prove this by induction on $|w|$.

I understand how to complete the basis part of this inductive proof, I think.

If w is the empty string, then $$\delta_D(q,\epsilon) = q$$ and $$\delta_N(q,\epsilon) = {q}$$ by definition of the extended transition function.

However, I'm lost as to how to finish the proof. I've come up the starts of something, but I don't know if I'm even in the right direction:

Assume the statement is true for strings shorter than y and break y into $xa$ where $a$ is last symbol of $y$ and x is the string of symbols before a.

$\delta_N(q_0, y) = \bigcup\limits_{i=1}\delta_n(p_i, a)$

$\delta_D(q_0, y) = \delta(\hat\delta(q_), x), a)$

For the full proof we should give the definition of the automata: $N = (Q, \Sigma, \delta_N, q_0, F)$ is the original NFA. We yield a DFA via subset or powerset construction: $D = (2^Q, \Sigma, \delta_D, \{q_0\}, \{P \subseteq Q \mid F \cap P \neq \varnothing\})$, with $\delta_D(P, a) = \{q \in Q \mid \exists p \in P. q \in \delta_N(p, a)\}$.

Now for the induction:
Base case: $\hat{\delta}_D(\{q_0\}, \varepsilon) = \{q_0\}$ by definition and $\hat{\delta}_N(\{q_0\}, \varepsilon) = \{q_0\}$.
Induction step: Let the statement be true for all $w \in \Sigma^n$, i.e. we land in some set $P \subseteq Q$ (which is a state in $D$). Consider some word $wa \in \Sigma^{n+1}$: $\hat{\delta}_D(\{q_0\}, wa) = \delta_D(\hat{\delta}_D(\{q_0\}, w), a) = \delta_D(P, a) = P^\prime$ with $P^\prime$ as given in powerset construction. By induction hypothesis we have that $\hat{\delta}_N(\{q_0\}, w) = P$ and $\hat{\delta}_N(\{q_0\}, wa) = \{q \in Q \mid \exists p \in P. q \in \delta_N(p, a)\} = P^\prime$.


Original answer for the other direction of the proof

I think you are overcomplicating things here. What you want to show is that if there is a language $L$ recognized by some DFA $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$, then there is an equivalent NFA. From your post I assume, your textbook defines NFAs with transition functions $\delta^\prime\colon Q \times \Sigma \to 2^Q$ (an other possible way would be transitions relations $\Delta \subseteq Q \times \Sigma \times Q$).

So, given DFA $\mathcal{A}$, you can just define the NFA $\mathcal{A}^\prime = (Q, \Sigma, \delta^\prime, q_0, F)$ with $\delta^\prime(p, a) = \{\delta(p, a)\}$ for all $p \in Q, a \in \Sigma$, i.e. always map to the singleton with the only possible state that the DFA would reach (i.e. the transition graph is the same). It is obvious that $\mathcal{A}^\prime$ recognizes the same language as $\mathcal{A}$.

In summary, you may say that DFAs are just NFAs where the transition function maps each state and symbol to a singleton (or rephrasing for transition relations: DFAs are just NFAs where the transition relation ist total and functional).

  • in the problem, the textbook says that if $\delta_D(q,a)$ then $\delta_N(q,a) = {p}$ but it asks us to show by induction on w that if $\hat\delta_D(q_0,w) = p$, then $\hat\delta_N(q_0,w) = {p}$ – Matt Mar 12 at 21:46
  • I updated my answer. I think I misinterpreted the question and you still are in the "if" part, where you want to prove that the DFA does the right thing. In this case an induction seems reasonable. $p$ is a set of states (from $Q_N$) here, right? – PHPNick Mar 12 at 22:56
  • Thank you so much for updating your answer. I'm lost on the last pat of the proof - why does $\hat{\delta}_N(\{q_0\}, w) = P$ and $\hat{\delta}_N(\{q_0\}, wa) = \{q \in Q \mid \exists p \in P. q \in \delta_N(p, a)\} = P^\prime$ ? – Matt Mar 13 at 0:07
  • The first equation is the induction hypothesis. The second one is simply one more step from there. For words $w \in \Sigma^\ast$ $\hat{\delta}_N(P, w)$ is the "reachability set" of $N$ from a subset of the states $P$ via word $w$ which can be defined like this. Apparently, it is the same as $P^\prime$ from the powerset construction above. Is this clearer? – PHPNick Mar 13 at 8:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.