Satz Korrektheit Potenzmengenkonstruktion ohne epsilon-Kanten

Einfache Sprache

Def. Satz Korrektheit Potenzmengenkonstruktion ohne epsilon-Kanten

Sei $\mathcal{A}=(Q^\mathcal{A},A,\delta^\mathcal{A},I^\mathcal{A},F^\mathcal{A})$ ein NEA und $\mathcal{B}=(Q^\mathcal{B},A,\delta^\mathcal{B},q^\mathcal{B},F^\mathcal{B})$ dessen deterministische Potenzmengenkonstruktion. Dann sind $\mathcal A$ und $\mathcal B$ Äquivalente Automaten.

Beweisidee: Zwei Automaten sind äquivalent genau dann wenn sie genau dieselbe Sprache erkennen. Also jede Eingabe wird entweder von beiden akzeptiert oder von beiden verworfen.

Der Beweis besteht aus zwei aufeinander aufbauende Hilfsaussagen und den eigentlichen Beweis.

Beweis:

Da wir zuerst die epsilon-Eliminierung auf den NEA $\mathcal A$ anwenden haben wir die leicht veränderte erweiterte Transitionfunktion $\bar\delta$ die wie folgt durch Strukturelle Induktion definiert ist:

Grundelemente: Es gilt $\bar\delta(q,\varepsilon)= E(\{q\})$ für alle $q\in Q$.

Konstruktionsvorschrift: Sei $w\in A_\varepsilon^*$, $a\in A$, $q\in Q$ und gilt $T:=\bar\delta(q,w)$, dann gilt

Sei $\mathcal A$ ein NEA und $\mathcal B$ der DEA der durch die Potenzmengenkonstruktion aus $\mathcal A$ entsteht.

1. Hilfsaussage: Für $q,q'\in Q^\mathcal A$ und $w\in A^*$ sind folgende Aussagen äquivalent:

1. Es gibt einen w-Pfad in $\mathcal A$ von $q$ nach $q'$.
2. $q'\in\bar\delta(q,w)$.

Beweis: Per Induktion über $w$.

IA: Sei $w = \varepsilon$. Es gibt eine epsilon-Pfad von $q$ nach $q'$ genau dann, wenn $q'\in E(\{q\})$ gilt. Das ist, nach der Definition oben, äquivalent zu $q'\in\bar\delta(q, \varepsilon)$.

IS: Sei $w\in A^*$ und $a\in A$. Es gibt einen $wa$-Pfad von $q$ nach $q'$ genau dann, wenn es $q_0,\ldots,q_n\in Q$ und $x_0,\ldots,x_{n-1}\in A_\varepsilon$ gibt so, dass $q_0 = q$, $q_n = q'$, $\forall i\in [0,n-1]:q_{i+1}\in\delta(q_i,x_i)$ und $x_0,\ldots,x_{n-1} = wa$.

Dass ist äquivalent dazu, dass es $t_0,t_1\in Q$, einen w-Pfad von $q$ nach $t_0$, die Transition $t_0\overset{a}\rightarrow t_1$ und einen epsilon-Pfad von $t_1$ nach $q'$ gibt.

Durch Anwendung der IH folgt, dass $t_0\in\bar\delta(q,w)$ ist. Aus $t_0\overset{a}\rightarrow t_1$ folgt, dass $t_1\in\delta(t_0, a)$ ist. Gegeben den epsilon-Pfad von $t_1$ nach $q'$, können wir nun $q'$ mithilfe der epsilon-Hülle wie folgt schreiben:

was wiederum, nach der Definition von $\bar\delta$, äquivalent zu $q'\in\bar\delta(q,wa)$.

2. Hilfsaussage: Für $T\subseteq Q$ und $w\in A^*$ gilt

IA: Sei $w = \varepsilon$.

Schlussüberlegung: Für $w\in A^*$ gilt