5. und 6. Vorlesung

Angabe von nicht-regulären Sprachen

Dies folgt aus dem Satz von Nerode.

\[\text{L ist nicht-regulär} \Longleftrightarrow \text{Index von } \simeq_L \text{ ist unedlich (d.h. unendl. viele Äquivalenzklassen)}\]

Beziehungsweise es gibt Wörter \(u_i \in \varSigma^*\) für beliebige \(i \ge 0\), so dass für \(i \neq j\) jeweils ein Wort w existiert mit \(u_i w \in L\) und \(u_j w \notin L\).

Beispiel \(L_i = \{ a^i b^i \mid i \ge 0 \}\)

Wähle \(u_i = a^i\). Für \(i \neq j\) gilt mit \(w = b^i\) :

\[\begin{split}&u_i w = a^i b^i \in L_1 \text{ und } \\ &u_j w = a^j b^i \notin L_1 (\text{da } i \notin j)\end{split}\]

Daraus folgt, dass \(L_1\) nicht regulär ist.

Sei \(L_2 = \{ 0^i 1^j \mid ggT(i,j) = 1 \}\) und wähle \(u_P = 0^P\), wobei p Primzahl ist (beachte es gibt unendlich viele Primzahlen). Für \(P \neq q\) gilt mit \(w = 1^q\):

\[\begin{split}&u_p w = 0^P 1^q \in L_2, \text{ weil }ggT(p,q) = 1 \\ &u_p w = 0^q 1^q \notin L_2, \text{ weil }ggT(q,q) = 1 \ge 2 \\\end{split}\]

Pumping-Lemma

Es sei L eine reguläre Sprache. Dann gibt es eine Zahl \(n \in \mathscr{N}\), sodass sich alle Wörter \(x \in L\) mit \(\mid x \mid \ge n\) zerlegen lassen in x = u v w mit den folgenden Eigenschaften:

1. \(\mid v \mid \ge 1\)
2. \(\mid u v \mid \le n\)
3. \(\forall i \ge 0: u v^i w \in L\)

Formal

\[\text{L ist regulär} \Rightarrow \exists n \in \mathscr{N}: \forall x \in L: \mid x \mid \ge n \Rightarrow x = u v w \wedge 1, 2 \text{ und } 3\]

Beweis

Sei a ein DEA der L akzeptiert. Wir wählen \(n = \mid Q \mid\). Sei \(x \in L\) mit \(\mid x \mid = m \ge n\) und \(x = a_1,...,a_n\) mit \(a_i \in \varSigma\). Dann folgt daraus, dass ein Pfad existiert mit \(\Pi = p_0 a_1 p_1 a_2 p_2 .... a_m p_m\) mit \(p_0 = q_0\) und \(p_w \in F\).

Die Anzahl der Zustände in \(\Pi\) ist \(m + 1 \ge n + 1\) (d.h. ein Zustand kommt mindestens zweimal vor). Daraus folgt, dass unter den ersten n+1 Zuständen \(p_0,...,p_n\) existiert ein Paar k,k’ mit \(0 \le k < k' \le n\) und \(p_k = p_{k'}\). Wähle \(u = a_1 ... a_k\), \(v = a_{k+1} ... a_{k'}\), \(w = a_{k'+1} ... a_m\).

Das heißt, das wegen \(p_k = p_{k'}\) gilt:

\[\forall i \ge 0: u v^i w \in L(a) = L\]

Da \(k < k'\) gilt \(\mid v \mid \ge 1\) und da \(k' \le n\) gilt \(\mid nv \mid \ge n\).

Beispiel 1

Sei \(L = \{ a^i b^i \mid i \ge 1 \}\) nicht-regulär.

Annahme: L ist regulär, also gibt es ein \(n \in \mathscr{N}\), sodass alle Wörter \(x \in L\) die Länge \(x \ge n\) haben. Wähle \(x = a^n b^n\) der Länge 2n, so folgt darus:

\[\begin{split}\exists &Zerlegung x = u v w: (1) \mid v \mid \ge 1, (2) \mid u,v \mid \le n \\ \Rightarrow &uv = a^m: m \le n \wedge m \ge 1 \\ \Rightarrow &v = a^{m'}: 1 \le m' \le m \\ \Rightarrow &uw = a^{n - m'} b^n \in L\end{split}\]

Dies ist ein Widerspruch da \(n - m' \neq n\) und nach Annahme \(a^n b^n\) kann dies nicht gelten.

Beispiel 2

\(L = \{ 0^m \mid \text{ m ist Quadratzahl} \}\) ist nicht regulär.

Annahme: L ist regulär, woraus folgt, dass \(\exists n \in N\), sodass alle Wörter \(x \in L\) die Länge n haben. Wähle \(x = 0^{n^2}\), woraus folgt, dass \(x \in L\) ist und \(\mid x \mid = n^2 \ge n\). Betrachtet man nun eine beliebige Zerlegung x = u v w mit \(1 \le \mid v \mid \le \mid uv \mid \le n\), so ergibt sich \(u v^2 w \in L\). Andererseits gilt:

\[\begin{split}n^2 &= \mid x \mid \\ &= \mid u v w \mid \\ &<^{\mid v \mid \ge 1} \mid u v^2 w \mid \\ &= \mid uvw \mid + \mid v \mid \\ &= n^2 + \mid v \mid \\ &\le n^2 + \mid uv \mid \\ &\le n^2 + n \\ &< n^2 + 2n + 1 \\ &= (n+1)^2\end{split}\]

Dies ist ein Widerspruch, da es eine Quadratzahl ist.

Es wurden die folgenden Definitionen eingeführt

• Reguläre Ausdrücke

Satz von Kleene

Eine Sprache \(L \subseteq \varSigma^*\) ist durch einen NEA erkennbar \(\Longleftrightarrow\) L ist durch einen regulären Ausdruck definiert.

Beweis

\(\Longleftarrow\): durch Induktion über Aufbau der regulären Ausdrücke. Finde für jeden regulären Ausdruck r einen \(\varepsilon\)-NEA \(a_r\) mit einem Endzustand \(L(r) = L(a_r)\)

Induktionsanfang:

Induktionsschluss:

\(\Longrightarrow\): Sei \(a = (Q, \varSigma, q_0, \Delta, F)\) als NEA gegeben mit \(Q = \{ q_0, q_1,...,q_n\}\). Wir definieren für \(0 \le i,j \le n\):

\[L_{ij} = \{ w: a: q_i \rightarrow^w q_j \}\]

So gilt

\[L(a) = \bigcup_{q_j \in F} L_{0 j}\]

Es genügt nun \(r_{ij}\) für \(L_{ij}\) zu finden. Hierzu gelte \(L(r) = \varSigma_{q_j \in F} r_{0 j}\) Der Index(q) für \(q \in Q\) sei dasjenige j mit \(q_j = q\).

Sei

\[\begin{split}L_{ij}^k = \{ w \mid \exists Pfad \Pi = p_0 a_1 p_1 ... p_{m - 1} a_m p_m: w = a_1 ... a_m, p_0 = q_i, p_m = q_j, Index(P_l) < k \text{ für } l = 1,..., m - 1 \}\end{split}\]

Beweis: \(L_{ij} = L_{ij}^{n+1}\)

Zeige: \(\forall k = 0, ..., n + 1: \forall i,j: L_{i,j}^k\) ist durch einen regulären Ausdruck definierbar.

k = 0:

Falls i = j: \(L_{ij}^0 = \{ \varepsilon \} \cup \{ a \mid (q_i, a, q_j) \in \Delta \}\) Sonst: \(\{a \mid (q_i, a, q_j) \in \Delta \}\)

Daraus folgt für \(r_{ij}^0\):

Falls i = j: \(r_{ij}^0 = \varepsilon + \varSigma_{(q_i, a, q_j) \in \Delta} a\) Sonst: \(r_{ij}^0 = \varSigma_{(q_i,a,q_j) \in \Delta} a\)

Induktionsschritt:

Es sei \(L_{ij}^k\) durch den regulären Ausdruck \(r_{ij}^k\) definierbar, also gilt:

\[\begin{split}w \in L_{ij}^{k + 1} &\Longleftrightarrow w \in L_{ij}^k \vee \exists m: w = w_0 w_1 ... w_m \text{ und } w_0 \in L_{ij}^k, w_1,..., w_{m-1} \in L_{kk}^k \text{ und } w_m \in L_{Rj}^k \\ &\Longrightarrow L_{ij}^{k+1} = L_{ij}^k \cup L_{ik}^k (L_{kk}^k)^* L_{kj}^k \text{ und } r_{ij}^{k+1} = r_{ij}^k + r_{ik}^k (r_{kk}^k)^* r_{kj}^k\end{split}\]

Beispiel

k = 0:

k = 1:

\[\begin{split}r_{00}^1 = r_{00}^0 + r_{00}^0 (r_{00}^0)^* r_{00}^0 &= (\varepsilon + 0) + (\varepsilon + 0)^* + (\varepsilon + 0) = 0^* \\ r_{01}^1 = r_{01}^0 + r_{00}^0 (r_{00}^0)^* r_{01}^0 &= 1 + 0^* 1 = 0^* 1 \\ r_{02}^1 = r_{01}^0 + r_{00}^0 (r_{00}^0)^* r_{02}^0 &= \emptyset \\ r_{11}^1 = r_{11}^0 + r_{10}^0 (r_{00}^0)^* r_{01}^0 &= \varepsilon + \emptyset 1 = 1\\ .... &= .... \\ r_{02}^2 = r_{02}^1 + r_{02}^1 (r_{11}^1)^* r_{12}^1 &= \emptyset + 0^* 1 \varepsilon 1 = 0^* 1 1 \\ r_{02}^3 = r_{02}^2 + r_{02}^2 (r_{22}^2)^* r_{22}^2 &= 0^* 1 1 + 0^* 1 1 \varepsilon = 0^* 1 1 = r_{02} = L(a)\end{split}\]

Ziel: Elegantes Verfahren für die Konstruktion von regulären Ausdrücken

Sei \(a = (Q, \varSigma, q_0, \Delta, F)\) mit \(Q = \{ q_0, ..., q_n \}\), \(a_i = (Q, \varSigma, q_i, \Delta, F)\), \(L_i = L(a_i)\) für \(0 \le i \le n\)

Nummerierung der Transiitonen aus \(q_i\): \((q_i, a_{(i,1)}, q_{(i,1)}),...,(q_i, a_{(i,w_i)}, q_{(i,w_i)})\)

\((*)_i\):

\[L_i = \{ a_{(i,1)} \} \cdot L_{(i,1)} \cup ... \cup \{ a_{(i, w_i)} \} L_{(i, w_i)} \cup E_i\]

Mit

\[\begin{split}E_i = \left\{ \begin{array}{ll} \{ \varepsilon \} & \mbox{falls } q_i \in F \\ \emptyset & \mbox{sonst} \end{array} \right.\end{split}\]

Zur Vereinfachung: \(\{ a \} L_j \cup \{ b \} L_j = \{ a,b \} L_j\)

Sei also \(A_{i,j} = \{ a \mid \{ a \} L_j \text{ kommt in der Zeile } (*)_j \text{ vor.}\}\) Daraus folgt: \(L_i = A_{i,0} L_0 \cup A_{i,1} L_1 \cup ... \cup A_{i,n} L_n \cup E_i\), wobei \(A_{i,j} ˜in \varSigma\).

Beispiel

Satz: Das zum NEA gehörige Gleichungssystem ist eindeutig lösbar

Das zum NEA a gehörige Gleichungssystem GS(a) \(X_i = \bigcup_{j = 0}^n A_{ij} X_j \cup E_i\) mit \(A_{ij}, E_i\) wie oben ist eindeutig lösbar und \(L_0,...,L_n\) mit \(L_i = L(a_i)\) ist die Lösung.

Beweis:

\((L_0,...,L_n)\) ist Lösung wegen der Definition von GS(a).

Eindeutigkeit:

Seien \((K_0,...,K_n),(K_0^', ..., K_n^')\) Lösungen von GS(a). Zeige \(\forall w \in \varSigma^*: \{ w \} \cap K_i = \{ w \} \cap K_i^'\)

Indktion über |w|:

IA: |w| = 0

\[\begin{split}\{ \varepsilon \} \cap K_i &= \bigcup_{j=0}^n(\{ \varepsilon \} \cap A_{ij} K_j) \cup (\{ \varepsilon\} \cap E_i)) \\ &= \{ \varepsilon \} \cap E_i\end{split}\]

Analog für K’

IS: |w| = n + 1

Sei \(w = xy\) mit |x| = 1

\[\begin{split}\{ w \} \cap K_i &= \bigcup_{j = 0}^n(\{ w \} \cap A_{ij} K_j) \cup (\{w\} \cap E_i) \\ &= ... \\ &= \{ w \} \cap K_{L}^{'}\end{split}\]