Nondeterministic finite state machine/Proofs

Theorem

" For every NFA, there exists an equivalent DFA"

$$ Let $M\; =\; (S,,\; Sigma\; ,,\; T,,\; s\_\{0\},,\; A)$ be an NFA that recognizes some language $,\; L$

:Construct a DFA $M\text{'}\; =\; (S\text{'},,\; Sigma\; \text{'},,\; T\text{'},,\; s\_\{0\}\text{'},,\; A\text{'})$ defined as follows:

:$,\; S\text{'}\; =\; P(S)$

:$,\; Sigma\; \text{'}\; =\; Sigma$

:$,\; T\text{'}:\; S\text{'}\; imesSigma\; \text{'}\; ightarrow\; S\text{'}$ such that

:$,\; s\_\{0\}\text{'}\; =\; E(\{s\_\{0\}\})$

:$,\; A\text{'}\; =\; \{\; Rin\; S\text{'}\; :\; Rcap\; A\; eq\; phi\; \}$

:Let $,\; w\; =\; x\_\{1\}x\_\{2\}cdots\; x\_\{n\}in\; L$ where $x\_\{1\},\; x\_\{2\},cdots\; x\_\{n\}inSigma$

:Since $,\; M$ recognizes $,\; L,$ $exists\; r\_\{0\},\; r\_\{1\},\; r\_\{2\},cdots\; r\_\{n\}in\; S$ such that

:$,\; r\_\{0\}in\; E(\{s\_\{0\}\})$

:$,\; r\_\{i+1\}in\; E(T(r\_\{i\},\; x\_\{i+1\}))\; i\; =\; 0,\; 1,\; cdots\; n-1$

:$,\; r\_\{n\}in\; A$

$,\; Let\; r\_\{0\}\text{'}\; =\; s\_\{0\}\text{'}\; =\; E(\{s\_\{0\}\})$

:

:

:$,\; vdots$

:

:It can be proved by induction that $,\; r\_\{n\}in\; r\_\{n\}\text{'}$

:Obviously, $,\; r\_\{0\}in\; r\_\{0\}\text{'}$ because $,\; r\_\{0\}\text{'}\; =\; E(\{s\_\{0\}\})$

:Assume $,\; r\_\{k\}in\; r\_\{k\}\text{'}$

:

:Hence, we have proved that $,\; r\_\{n\}in\; r\_\{n\}\text{'}cap\; A$

:Therefore, $,\; r\_\{n\}\text{'}in\; A\text{'}$

Comment

The idea of Powerset construction was originally derived from this proof idea.

References

* Michael Sipser, "Introduction to the Theory of Computation" ISBN 0-534-94728-X. "(See . Theorem 1.19, section 1.2, pg. 55.)"