Poniżej przedstawię Ci treść i dowód twierdzenia o determinizacji automatów skończenie stanowych, znanym mi pod nazwą "Twierdzenia Scotta".
Treść twierdzenia
Twierdzenie Scotta o determinizacji niedeterministycznych automatów skończenie stanowych mówi, że dla każdego niedeterministycznego automatu skończenie stanowego \(\mathcal{A}\) istnieje taki deterministyczny automat skończenie stanowy \(\mathcal{A}'\), że \(L(\mathcal{A})=L(\mathcal{A}')\).
Dowód
Określamy:
- \(\mathcal{A} = (K, T, \delta, q_0, F)\) - automat niedeterministyczny,
- \(\mathcal{A}' = (K', T', \delta', q_0', F')\) - automat deterministyczny,
- \(K' = P(K)\) - zbiór stanów jako zbiór potęgowy stanów NFA,
- \(T' = T\) - alfabet taśmy,
- \(F' = (q \in K' : q \cap F \not = \varnothing)\),
- \(\delta' : K' \times T' \to K'\),
- \(\delta'(q, a) = \bigcup_{S \in q} \delta (S, a) \) - \(q\) jako zbiór stanów,
- \( q'_0 = \{q_0\} \).
Aby pokazać, że dwa automaty DFA i NFA akceptują te same języki musimy pokazać, że ich rozszerzone funkcje przejścia są sobie równe, czyli:
\[ \hat{\delta'} (q_0', P) = \hat{\delta}(q_0, P) \]
Dowodzimy indukcyjnie po długości słowa \(P\). Najpierw przypadek \(P = \varepsilon\):
Lewa strona:
\[ \hat{\delta'}(q_0', \varepsilon) = \hat{\delta'}(\{q_0\}, \varepsilon) \overset{\text{def}}{=} \{q_0\} \]
Prawa strona:
\[ \hat{\delta}(q_0, \varepsilon) \overset{\text{def}}{=} \{q_0\} \]
Zakładamy teraz, że nasz równość zachodzi dla \(P\), czyli:
\[ \hat{\delta'}(q_0', P) = \hat{\delta}(q_0, P) \]
i dowodzić będziemy tezę dla słowa \(P\) o jeden znak dłuższego czyli \(Pa\):
\[ \hat{\delta'}(q_0', Pa) = \hat{\delta}(q_0, Pa) \]
Lewa strona:
\[ \hat{\delta'}(\{q_0\}, Pa) \overset{\text{def}}{=} \delta'(\hat{\delta'}(\{q_0\}, P), a) \overset{\text{zał.}}{=} \delta'(\hat{\delta}(q_0, P), a) = \bigcup_{S \in \hat{\delta}(q_0, P)} \delta (S, a) \]
Prawa:
\[ \hat{\delta}(q_0, Pa) \overset{\text{def}}{=} \bigcup_{S \in \hat{\delta}(q_0, P)} \delta(S, a) \]
Obie strony są sobie równe, dowód jest już prawie skończony. Należy jeszcze pokazać, że dowolne słowo należące do języka akceptowanego przez \(\mathcal{A}\) należy również do języka akceptowanego przez \(\mathcal{A'}\)
\[ P \in L(\mathcal{A}) \iff \]
\[ \hat{\delta}(q_0, P) \space \cap \space F \neq \varnothing \iff \]
\[ \hat{\delta'}(\{q_0\}, P) \space \cap \space F \neq \varnothing \iff \]
\[ \hat{\delta'}(\{q_0\}, P) \in F' \iff \]
\[ \hat{\delta'}(q_0', P) \in F' \iff \]
\[ P \in L(\mathcal{A'}) \]