Satz Kleene Hülle eines NEAs
Einfache Sprache
Def. Satz Kleene Hülle eines NEAs
Sei $\mathcal N_1 = (Q_1,A,\delta_1,\{q_I^1\}, F_1)$ NEA.
Wir definieren den NEA $\mathcal N:= (Q,A,\delta,\{q_I\}, F)$ wobei:
- $Q = Q\overset{\cdot}\cup\{q_I\}$ (hier ist $\overset{\cdot}\cup$ die Disjunkte Vereinigung)
- $\delta:Q\times\Sigma\cup\{\varepsilon\}\to\mathcal P(Q)$ mit $$\delta(q,x):=\begin{cases}\{q_I^1\}&\text{falls } q=q_I\land x=\varepsilon,\\\emptyset&\text{falls } q=q_I\land x\in A,\\\delta_1(q,x)&\text{falls } q\in Q_1\setminus F_1\lor (q\in F_1\land x\not=\varepsilon),\\\delta_1(q,x)\overset{\cdot}\cup \{q_I^1\}&\text{falls } q\in F_1\land x =\varepsilon.\\\end{cases}$$
- $F := F_1\overset{\cdot}\cup \{q_I\}$
Dann gilt $L(\mathcal N) = L(\mathcal N_1)^*$.
Beweisidee: Wir zeigen Gleichheit durch beidseitige Inklusion.
Beweis: Wir zeigen Gleichheit durch beidseitige Inklusion.
“$\supseteq$”: Wir nutzen Induktion über die Elemente von $L(\mathcal N_1)^*$. IA: Aus $\varepsilon\in L(\mathcal N_1)$ folgt $\varepsilon\in L(\mathcal N_1)$, weil $q_I\in F_1$. IH: Für $w\in L(\mathcal N_1)^*$ gilt $x\in L(\mathcal N)$. IS: Sei $y\in L(\mathcal N_1)$. Wir zeigen nun, dass $xy\in L(\mathcal N)$. Aus $x\in L(\mathcal N)$ folgt, aus der Konstruktion von $\mathcal N$, dass $\hat\delta(q_I,x)\in F$. Da $F = F_1\overset{\cdot}\cup\{q_I\}$ können, nach einer zusätzlichen Epsilon-Transition nach $x$ schließen, dass wir unter anderem in $q_I^1$ sein können, also $q_I^1\in\hat\delta(q_I, x\varepsilon)$.Aus $y\in L(\mathcal N_1)$ folgt $\hat\delta(q_I^1, y)\in F_1\subseteq F$. Beides zusammen ergibt $\hat\delta(q_I,xy)\in F$, also $xy\in L(\mathcal N)$.
“$\subseteq$”: Wir nutzen Induktion über die Anzahl der Besuche $n\in\mathbb N$ von $q_I^1$ die benötigt werden um ein Wort zu akzeptiert, dass $L(\mathcal N)\subseteq L(\mathcal N_1)^*$. IA:Für akzeptierte Wörter mit $n=0$ erhalten wir $\varepsilon\in L(\mathcal N)\cap L(\mathcal N_1)^*$. IH: Für akzeptierte Wörter $w'\in L(\mathcal N)$ mit $n$ Besuchen von $q_I^1$ gilt, $w'\in L(\mathcal N_1)^*$. IS: Wir betrachten akzeptierende Wörter $w\in L(\mathcal N)$, mit $n+1$ Besuchen von $q_I^1$. Wir wissen, dass $w'$ ein Präfix von $w$ ist und $w'$ $n$-mal $q_I^1$ besucht. Aus der IH folgt $w'\in L(\mathcal N_1)^*$. Sei $w''\in \Sigma^*$ so, dass $w = w'w''$. Aus $w\in L(\mathcal N)$ können wir schließen, dass $w''\in L(\mathcal N_1)$. Beides zusammen ergibt $w=w'w''\in L(\mathcal N_1)^*$.
Graphisches Beipspiel
