Satz Vereinigung zweier NEAs

Einfache Sprache

Def. Satz Vereinigung 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\}, 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,\\\delta_2(q,x)&\text{falls } q\in Q_2,\\\{q_I^1,q_I^2\}&\text{falls } q\in q_I\land x = \varepsilon,\\\emptyset&\text{falls } q\in q_I\land x \in A.\\\end{cases}$$
• $F := F_1\overset{\cdot}\cup F_2$

Dann gilt $L(\mathcal N) = L(\mathcal N_1) \cup L(\mathcal N_2)$.

Beweis: Seien $\mathcal N_1 = (Q,A,\delta_1,\{q_I^1\}, F_1)$ und $N_2 = (Q,A,\delta_2,\{q_I^2\}, F_2)$ zwei NEAs. Wir zeigen $L(\mathcal N) = L(\mathcal N_1) \overset{\cdot}\cup L(\mathcal N_2)$ durch beidseitige Inklusion:

“$\subseteq$”: Sei $w\in L(\mathcal N_1)\cup L(\mathcal N_2)$. Sei o.B.d.A. $w\in L(\mathcal N_1)$. Dann ist $\hat\delta(q_I,w)\in F_1\subseteq F$. Also ist $w\in L(\mathcal N)$.

“$\supseteq$”: Wir machen einen Indirekter Beweis und zeigen aus $w\not\in L(\mathcal N_1)\cup L(\mathcal N_2)$ folgt $w\not\in L(\mathcal N)$. Nach der Definition von Vereinigung ist $w\not\in L(\mathcal N_1)$ und $w\not\in L(\mathcal N_2)$. Also ist $\hat\delta(q_I,w)\not\in F_1\cup F_2$, woraus $w\not\in L(\mathcal N)$ folgt.

Graphisches Beipspiel

oder abstrakter