Satz Konkatenation zweier NEAs
Einfache Sprache
Def. Satz Konkatenation zweier NEAs
Seien $\mathcal N_1 = (Q_1,A,\delta_1,\{q_I^1\}, F_1)$ und $N_2 = (Q_2,A,\delta_2,\{q_I^2\}, F_2)$ zwei NEAs.
Wir definieren den NEA $\mathcal N:= (Q,A,\delta,\{q_I^1\}, F)$ wobei:
- $Q = Q_1\overset{\cdot}\cup Q_2\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}\delta_1(q,x)&\text{falls } q\in Q_1\land (q\not\in F \lor x\not\in \varepsilon),\\\delta_1(q,x)\overset{\cdot}\cup \{q_I^2\}&\text{falls } q\in F_1\land x = \varepsilon,\\\delta_2(q,x)&\text{falls } q\in Q_2.\end{cases}$$
- $F := F_2$
Dann gilt $L(\mathcal N) = L(\mathcal N_1) \cdot L(\mathcal N_2)$.
Beweis: Seien $\mathcal N_1 = (Q_1,A,\delta_1,\{q_I^1\}, F_1)$ und $N_2 = (Q:2,A,\delta_2,\{q_I^2\}, F_2)$ zwei NEAs. Wir zeigen $L(\mathcal N) = L(\mathcal N_1) \cdot L(\mathcal N_2)$ durch beidseitige Inklusion:
“$\subseteq$”: Sei $w\in L(\mathcal N_1)\cdot L(\mathcal N_2)$. Dann existiert eine Faktorisierung (Zerteilung in zwei(oder mehr) Teile die mit einer Operation das Original ergeben) $w = uv$ so, dass $u\in L(\mathcal N_1)$ und $v\in L(\mathcal N_2)$. Geschrieben in Transitionsfunktionen also $\hat\delta_2(\hat\delta_1(q_I^1, u),v)$. Da $\hat\delta(q_I^1, u)\in F_1$ und damit nach der Konstruktion von $\mathcal N$ und dem Fakt, dass $v\in L(\mathcal N)$, ergibt sich das $\hat\delta_2(\hat\delta_1(q_I^1, u),v) = \hat\delta(q_I^1,uv) = \hat\delta(q_I^1,w)\in F_2$. Also ist $w\in L(\mathcal N)$.
“$\supseteq$”: Wir machen einen Indirekter Beweis und zeigen aus $w\not\in L(\mathcal N_1)\cdot L(\mathcal N_2)$ folgt $w\not\in L(\mathcal N)$. Nach der Definition von Konkatenation existiert keine Faktorisierung $w=uv$ so, dass $u\in L(\mathcal N_1)$ und $v\in L(\mathcal N_2)$. Also ist $\hat\delta_2(\hat\delta_1(q_I^1, u),v) = \hat\delta(q_I^1, uv) = \hat\delta(q_I^1, w)\not\in F$, wehalb $w\not\in L(\mathcal N)$, da es nach der Konstruktion von $\mathcal N$ keine weiteren Transitionen gibt.
Graphisches Beipspiel
Von
Nach
