Did somebody did the demonstration?
A languages L is accepted by A DFA if and only if L is accepted by NFA (only if part)
Number of replies: 3
In reply to DENISA ALEXANDRA STOICA
Re: A languages L is accepted by A DFA if and only if L is accepted by NFA (only if part)
by MATTEO PADRIN -
Hi Denisa,
I think it comes directly from this idea:
A deterministic finate state automata is a special case of a non deterministic one (essentially the function $\delta$ is different) so you just have to deal with the fact that the codomain is not a state but a set of one element (i.e. that instead of pointing at q_0 the output is {q_0}
What do you think about this proof?
In reply to MATTEO PADRIN
Re: A languages L is accepted by A DFA if and only if L is accepted by NFA (only if part)
by NICOLA RANZOLIN -
Hi,
I do agree with you, Matteo. A DFA is indeed a special case of an NFA.
Formally, given a DFA D = \( (Q, \Sigma, \delta_D, q_0, F) \), we can construct an equivalent NFA N = by defining:
\(\delta_D(\{q\}, a)\ = \delta_N(q, a)\) .
An observation is that in the subset construction, \(\delta_D\) takes as input a set of states and returns a single state, while \(\delta_N\) takes a single state and returns a set of states. It's interesting to notice how this inversion of roles reflects the relation between determinism and non-determinism.
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 states, alphabet, start and accept states.
Therefore, L(D) = L(N), completing the “only if” part.
In reply to NICOLA RANZOLIN
Re: A languages L is accepted by A DFA if and only if L is accepted by NFA (only if part)
by NICOLA RANZOLIN -
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.