◀ ▲ ▶Branches / Theoretical-computer-science / Formal-languages / Proof

Proof

(related to Theorem: Reduction of NFA to DFA (Rabin-Scott Theorem))

We will prove the theorem by showing the set equality $\mathcal L(\operatorname{NFA})=\mathcal L(\operatorname{DFA}).$

$\mathcal L(\operatorname{DFA}) "\subseteq" \mathcal L(\operatorname{NFA})$

• The definition of the deterministic finite automaton. DFA is a special case of the definition of the non-deterministic finite automaton. NFA.
• This is because in a given DFA definition $A=(C,\Sigma,\delta,F,s_0),$ we just have to replace $s_0$ by the set $S=\{s_0\}$ and the function $\delta$ is a special case of a relation $\Delta$ (in fact, every function is a left-total, right-unique relation.
• With these replacements, we have $A=(C,\Sigma,\Delta,F,S)$ as a special case of an NFA.

just to replace the function definition by the other by replacing the function `$\d

$\mathcal L(\operatorname{DFA}) "\supseteq" \mathcal L(\operatorname{NFA})$

• Let $A=(C,\Sigma,\Delta,F,s_0)$ be an NFA.
• We construct a DFA $A^\prime=(C^\prime,\Sigma,\delta,F^\prime,s_0^\prime)$ by making the following replacements:
  • We replace the set of states $C$ of the NFA by the power set of $C$, i.e. $$C^\prime:=\mathcal P( C).$$ Note that the power set has also finitely many elements, just like $C$ has.
  • We set the starting state of the DFA to $$s_0^\prime:=\{s_0\}\in C^\prime$$ (the singleton containing the starting state of the NFA).
  • Note that if for a string $\sigma_0,\sigma_1,\ldots,\sigma_n\in\Sigma^*$ the NFA is in a state $q$, this means by the definition of $L(\operatorname{NFA})$ that there is a starting state $s_0\in S$ with $q=\Delta(\ldots\Delta(\Delta(s_0,\sigma_0),\sigma_1),\ldots,\sigma_n)\in F$.
  • We define for all words $\sigma_0,\sigma_1,\ldots,\sigma_n\in\Sigma^*$ and all states $Q\in C^\prime$ the function $\delta:(C^\prime\times \Sigma^*)\to C^\prime$ by $$\delta(\ldots\delta(\delta(s_0,\sigma_0),\sigma_1),\ldots,\sigma_n)=Q\in C^\prime\Longleftrightarrow \exists s_0\in S,\; \Delta(\ldots\Delta(\Delta(\{s_0\},\sigma_0),\sigma_1),\ldots,\sigma_n)=q\in Q\subseteq C$$
  • This means, we define the DFA to be exactly in the state $Q\in C^\prime,$ if and only if for the same word the corresponding NFA produces one of the states $q\in Q\subseteq C.$
  • The final states $F^\prime$ will be defined by all $Q\in C^\prime$ containing at least one final state $q\in F$, in other words, $$F^\prime:=\{Q\in C^\prime\mid Q\cap F\neq\emptyset\}.$$
• It follows by construction, that $A^\prime$ is a DFA accepting exactly the same words as the given NFA.
  ∎

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition
2. Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015