Der Schnittpunkt der regulären Sprachen
Kapitoly: Schließung von regulären Sprachen, Vereinheitlichung, Zugang zu, Der Unterschied, Ergänzung, Verkettung, Schlussfolgerung
Wir haben zwei reguläre Sprachen L1, L2. Wir beweisen, dass ihre Schnittmenge L = L1 ∩ L2 ebenfalls eine reguläre Sprache ist.
Die Idee eines Beweises
Gegeben zwei reguläre Sprachen L1 und L2, wollen wir beweisen, dass ihre Schnittmenge L1 ∩ L2 ebenfalls eine reguläre Sprache ist. Da L1 und L2 reguläre Sprachen sind, gibt es endliche Automaten A1 und A2, die die Sprachen L1 und L2 akzeptieren, so dass L(A1) = L1 und L(A2) = L2 gelten. Als nächstes konstruieren wir einen endlichen Automaten A, der die Sprache L1 ∩ L2 akzeptiert und beweisen, dass die Sprache L1 ∩ L2 regulär ist.
Ein Wort gehört zur Schnittmenge der Sprachen, wenn es zur Sprache L1 und auch zu L2 gehört. Das Wort muss also sowohl vom Automaten A1 als auch vom Automaten A2 akzeptiert werden. Wir verwenden genau die gleiche Idee wie bei der Vereinheitlichung regulärer Sprachen, nur dass wir die Menge der endlichen Zustände ändern.
Formalisierung des Verfahrens.
Wir haben zwei Automaten,
\begin{eqnarray} A_1&=&\left<Q_1, \Sigma_1, \delta_1, q_0, F_1\right>\A_2&=&\left<Q_2, \Sigma_2, \delta_2, p_0, F_2\right> \end{eqnarray}
Wir konstruieren einen Automaten $A=\left<Q, \Sigma, \delta, q, F\right>$, der die Sprache L(A1)∩ L(A2) akzeptiert. Es gilt, dass
- Q = Q1 × Q2
- $\Sigma = \Sigma_1 \cap \Sigma_2$
- q = <q0, p0>
- F = F1 × F2
Die folgende Beziehung gilt für die Übergangsfunktion δ:
$$ \forall q\in Q_1, p\in Q_2: \delta(\left<q,p\right>, a) = \left<\delta_1(q, a), \delta_2(p, a)\right> $$
Beispiel
Betrachten wir diesen Automaten A1, der alle Wörter akzeptiert, die eine gerade Anzahl von 1 enthalten:
und den Automaten A2, der Wörter akzeptiert, die eine ungerade Zahl von 0 enthalten:
Konstruieren Sie einen Automaten, der die Schnittmenge dieser beiden Sprachen annimmt. Die Menge der Zustände dieses Automaten ist von der Form Q = Q1 × Q2, der Anfangszustand ist der Zustand <q0, p0>, und die Endzustände sind F1 × F2:
Als nächstes vervollständigen wir die Übergänge so, dass δ(<q,p>, a) = <δ1(q, a), δ2(p, a)>:
Zum Beispiel ist in diesem Automaten der Zustand <q0, p0> der Übergang für das Symbol 0 in den Zustand <q0,p1>. Das bedeutet, dass der Automat A1 einen Übergang für das Symbol 0 vom Zustand q0 zurück zum Zustand q0 hat. Der Automat A2 wiederum hat einen Übergang für das Symbol 0 vom Zustand p0 zum Zustand p1.
Wir können den Automaten testen. Er sollte Wörter wie 110 oder 00000 akzeptieren (sie enthalten eine gerade Anzahl von 1en und eine ungerade Anzahl von 0en), aber er sollte Wörter wie 11, 111, 1010 nicht akzeptieren).