Hi everyone,
Just a quick correction to my previous post. I mistakenly inverted \( q \) and \( \{q\} \) and also left out the definition of \( N \).
The corrected and complete version is as follows.
Formally, given a DFA \( D = (Q, \Sigma, \delta_D, q_0, F) \), we can construct an equivalent NFA \( N \) by defining:
\[
N = (Q, \Sigma, \delta_N, q_0, F)
\]
where
\[
\delta_N(q, a) = \{\delta_D(q, a)\}.
\]
By induction on the length of the input string \( w \), one can prove that both automata reach the same state after reading \( w \):
\[
\delta_D^{rec}(\{q_0\}, w) = p \iff \delta_N^{rec}(q_0, w) = \{p\}.
\]
Hence, the NFA \( N \) behaves identically to the DFA \( D \): same set of states, alphabet, initial state and accepting states. Therefore, \( L(D) = L(N) \), completing the “only if” part.
Just a quick correction to my previous post. I mistakenly inverted \( q \) and \( \{q\} \) and also left out the definition of \( N \).
The corrected and complete version is as follows.
Formally, given a DFA \( D = (Q, \Sigma, \delta_D, q_0, F) \), we can construct an equivalent NFA \( N \) by defining:
\[
N = (Q, \Sigma, \delta_N, q_0, F)
\]
where
\[
\delta_N(q, a) = \{\delta_D(q, a)\}.
\]
By induction on the length of the input string \( w \), one can prove that both automata reach the same state after reading \( w \):
\[
\delta_D^{rec}(\{q_0\}, w) = p \iff \delta_N^{rec}(q_0, w) = \{p\}.
\]
Hence, the NFA \( N \) behaves identically to the DFA \( D \): same set of states, alphabet, initial state and accepting states. Therefore, \( L(D) = L(N) \), completing the “only if” part.