Verified
Theorem: a language L is recognized by a DFA if and only if L is recognized by a NFA.
Must prove two directions:
(⇒) L is recognized by a DFA implies L is recognized by a NFA.
(⇐) L is recognized by a NFA implies L is recognized by a DFA.
(⇒) L is recognized by a DFA implies L is recognized by a NFA
Proof: a deterministic finite automaton is a nondeterministic finite automaton for which each state has exactly one outgoing transition for each symbol (with exception of epsilon transitions, which have no outgoing ones).
(⇐) L is recognized by a NFA implies L is recognized by a DFA.
Proof: we will build a DFA that simulates the NFA (and thus recognizes the same language).
– alphabet will be the same
– what are the states of the NFA?
– given NFA M = (Q, Σ, δ, q0, F)
– construct DFA M’ = (Q’, Σ’, δ’, q0’, F’)
– same alphabet: Σ’= Σ
– states are subsets of M’s states: Q’ = ℘(Q)
– if we are in "superstate" R∈Q’ and we read symbol a∈Σ’, what is the new state?
– given NFA M = (Q, Σ, δ, q0, F)
– construct DFA M’ = (Q’, Σ’, δ’, q0’, F’)
Helpful definition:
Eps(S) = {q ∈ Q : q reachable from subset S by traveling along 0 or more ε-transitions}
– new transition fn: δ’(R, a) = ∪r∈R Eps(δ(r, a))
= “all nodes reachable from R by following an a-transition, and then 0 or more ε-transitions”
– given NFA M = (Q, Σ, δ, q0, F)
– construct DFA M’ = (Q’, Σ’, δ’, q0’, F’)
– new start state: q0’= Eps({q0})
– new accept states: F’ = {R ∈ Q’ : R contains an accept state of M)
We have proved (⇐) by construction. Formally we should also prove that the construction works, by induction on the number of steps of the computation.
– at each step, the state of the DFA M’ is exactly the set of reachable states of the NFA M…
Theorem: the set of languages recognized by NFA is closed under union, concatenation, and star.
Theorem: a language L is recognized by a DFA if and only if L is recognized by a NFA.
Corollary: the set of languages recognized by DFA is closed under union, concatenation, and star.