FSK-ÜB-5

FSK5-1 Myhill und Nerode (2 Punkte)

a) Sei $L=L(a{b}^{\ast }c)$ eine Sprache über dem Alphabet $\Sigma =\{a,b,c\}$. Geben Sie für jedes der folgenden Wörter $u_i,i\in \{1,2,3\}$, eine kompakte Beschreibung der Äquivalenzklasse $[u_i]$ der Nerode-Relation von $L$ an.

Aufgabenstellung

1. $u_1=abb$
2. $u_2=\epsilon$
3. $u_3=c$

Anleitung zum lösen der Aufgabe

1. Suffix-Erweiterung: Zunächst analysieren wir, um welchen Suffix das Wort erweitert werden muss, damit es in der gewünschten Sprache enthalten ist.
2. Präfix-Analyse: Im nächsten Schritt betrachten wir den identifizierten Suffix und überlegen, um welchen Präfix dieser erweitert werden muss, damit der Suffix in der Sprache enthalten ist.
3. Äquivalenzklasse: Der ermittelte Präfix bildet dann die entsprechende Äquivalenzklasse.

Durch diese methodische Herangehensweise wird sichergestellt, dass das Wort korrekt erweitert und in die richtige Äquivalenzklasse eingeordnet wird.

1. $u_1=abb$

Musterlösung

Präfix suchen was muss nach dem Wort stehen, damit es regulär ist Danach: Präfix damit das Wort gebildet werden kann

$$[abb]=\{a{b}^{\ast }c\}$$

Falscher Ansatz (aufklappbar)

$$[abb]=\{v\in {\Sigma }^{\ast }:vc\in L\text{ und kein anderes }vx\in L>\text{ fu¨r }x\ne c\}$$ $$[abb]=\{v\in {\Sigma }^{\ast }\mid \forall x\in {\Sigma }^{\ast }:vx\in \leftrightarrow x=c\}$$

2. $u_2=ϵ$

Musterlösung

$$[\epsilon ]=\{\epsilon \}$$

Falscher Ansatz (aufklappbar)

$$[\epsilon ]=\{a{b}^{\ast }c\}$$

3. $u_3=c$

Lösung

Erklärung

Das gegebene Problem bezieht sich auf die Bestimmung der Äquivalenzklasse $[u_3]$ mit $u_3=c$.

Problemstellung:

$u_3=c$

Lösungsvorschlag:

Es gibt kein $w$ sodass $cw\in L$ ist. Somit ist $[c]$ die Menge der Wörter $v\in {\Sigma }^{\ast }$, für die mit jedem $w$ gilt: $vw\notin L$. Das ist der Fall für $v\in L(b{\Sigma }^{\ast })$, $v\in L(c{\Sigma }^{\ast })$, $v\in L(aa{\Sigma }^{\ast })$, $v\in L(a{b}^{\ast }a{\Sigma }^{\ast })$ und $v\in L(a{b}^{\ast }c\Sigma {\Sigma }^{\ast })$, wobei $\Sigma$ der reguläre Ausdruck $(a|b|c)$ ist. Somit ist

$$[c]=L((b|c|aa){\Sigma }^{\ast }\mid a{b}^{\ast }a{\Sigma }^{\ast }\mid a{b}^{\ast }c\Sigma {\Sigma }^{\ast })$$

Detaillierte Erklärung des Beweises

Um die Äquivalenzklasse $[c]$ zu bestimmen, folgt man diesen Schritten:

1. Definition der Sprache $L$:
   • Die Sprache $L$ ist nicht explizit gegeben, aber wir müssen feststellen, dass für $u_3=c$ kein Wort $w$ existiert, sodass $cw\in L$.
2. Bestimmung von $[c]$:
   • $[c]$ umfasst alle Wörter $v\in {\Sigma }^{\ast }$, für die gilt: $vw\notin L$ für jedes $w\in {\Sigma }^{\ast }$. Dies bedeutet, dass das Wort $v$ nie zu einem Wort führt, das in $L$ liegt, egal welches $w$ hinzugefügt wird.
3. Analyse von $v$:
   • Wenn $v$ aus der Sprache $L(b{\Sigma }^{\ast })$ stammt, bedeutet das, dass $v$ mit $b$ beginnt und beliebige Zeichen aus $\Sigma$ folgen können.
   • Wenn $v$ aus der Sprache $L(c{\Sigma }^{\ast })$ stammt, bedeutet das, dass $v$ mit $c$ beginnt und beliebige Zeichen aus $\Sigma$ folgen können.
   • Wenn $v$ aus der Sprache $L(aa{\Sigma }^{\ast })$ stammt, bedeutet das, dass $v$ mit zwei $a$ beginnt und beliebige Zeichen aus $\Sigma$ folgen können.
   • Wenn $v$ aus der Sprache $L(a{b}^{\ast }a{\Sigma }^{\ast })$ stammt, bedeutet das, dass $v$ mit einem $a$, gefolgt von beliebig vielen $b$ und einem weiteren $a$ beginnt, gefolgt von beliebigen Zeichen aus $\Sigma$.
   • Wenn $v$ aus der Sprache $L(a{b}^{\ast }c\Sigma {\Sigma }^{\ast })$ stammt, bedeutet das, dass $v$ mit einem $a$, gefolgt von beliebig vielen $b$ und einem $c$ beginnt, gefolgt von zwei Zeichen aus $\Sigma$.
4. Regulärer Ausdruck für $[c]$:
   • Der reguläre Ausdruck, der diese Bedingungen zusammenfasst, ist $(b|c|aa){\Sigma }^{\ast }\mid a{b}^{\ast }a{\Sigma }^{\ast }\mid a{b}^{\ast }c\Sigma {\Sigma }^{\ast }$.

Schlussfolgerung:

Die Äquivalenzklasse $[c]$ besteht aus Wörtern, die nie zu einem Wort in $L$ führen, unabhängig von dem angehängten $w$.

Suffix

$$[c]=\varnothing$$

Präfix ist trickier

Musterlösung

$$[c]=\{L((c\mid b\mid aa){\Sigma }^{\ast })\mid (a{b}^{\ast }a{\Sigma }^{\ast })\mid a{b}^{\ast }c\Sigma {\Sigma }^{\ast })\}$$

b) Bestimmen Sie den Nerode-Index folgender Sprachen $L_i,i\in \{1,2,3\}$, über Alphabeten ${\Sigma }_i$ und entscheiden Sie mit dem Satz von Myhill und Nerode, welche der Sprachen regulär sind. Geben Sie für jede Sprache mit endlichem Nerode-Index alle paarweise verschiedenen Äquivalenzklassen an (1 Repräsentant pro Klasse).

Aufgabenstellung

1. $L_1=\{aaab,aabb,abab,abbb,baab,bbab,bbbb\}$ mit ${\Sigma }_1=\{a,b\}$
2. $L_2=\{w\overline{w}w\mid w\in {\Sigma }_2^{\ast }\}$ mit ${\Sigma }_2=\{a,b\}$
3. $L_3=\{a^i{b}^j{c}^k\mid i,j,k\in \mathbb{N}\text{ und }i=2,\text{ dann }j<k\}$ mit ${\Sigma }_3=\{a,b,c\}$

1. $L_1=\{aaab,aabb,abab,abbb,baab,bbab,bbbb\}$ mit ${\Sigma }_1=\{a,b\}$

Lösung

Erklärung

Das gegebene Problem bezieht sich auf die Bestimmung der Regularität der Sprache $L_1$ über dem Alphabet ${\Sigma }_1=\{a,b\}$.

Sprache $L_1$:

$L_1=\{aaab,aabb,abab,abbb,baab,babb,bbab,bbbb\}$

Lösungsvorschlag:

Die Lösung beinhaltet das Finden der verschiedenen Äquivalenzklassen der Myhill-Nerode-Relation für die gegebene Sprache. Äquivalenzklassen gruppieren Zeichenketten, die von der Sprache $L_1$ nicht unterschieden werden können.

Identifizierte Äquivalenzklassen:

1. $[\epsilon ]$ - Die Klasse, die die leere Zeichenkette enthält.
2. $[a]$ - Die Klasse, die die Zeichenkette “a” enthält.
3. $[aa]$ - Die Klasse, die die Zeichenkette “aa” enthält.
4. $[aaa]$ - Die Klasse, die die Zeichenkette “aaa” enthält.
5. $[aaab]$ - Die Klasse, die die Zeichenkette “aaab” enthält.
6. $[aaaa]$ - Die Klasse, die die Zeichenkette “aaaa” enthält.

Der Nerode-Index, also die Anzahl dieser Äquivalenzklassen, beträgt 6.

Detaillierte Erklärung zur Bestimmung der Äquivalenzklassen

Um die Äquivalenzklassen der Myhill-Nerode-Relation zu bestimmen, folgt man diesen Schritten:

1. Initiale Identifizierung: Beginne mit der leeren Zeichenkette $\epsilon$ und prüfe, welche Zeichenketten durch Anhängen von Symbolen aus ${\Sigma }_1$ entstehen können.
2. Prüfung der Verlängerungen: Betrachte, wie verschiedene Präfixe von Zeichenketten in $L_1$ erweitert werden können, um entweder gültige Zeichenketten in $L_1$ oder andere Zeichenketten zu bilden, die von $L_1$ unterschieden werden können.
3. Äquivalenzklassen-Bildung: Gruppiere Zeichenketten, die durch dieselben Erweiterungen in $L_1$ zu denselben Ergebnissen führen.

Beispiel für die Bestimmung:

• $\epsilon$ (leere Zeichenkette) ist eine eigene Klasse: $[\epsilon ]$.
• “a” ist ein Präfix, das durch Anhängen von “a” oder “b” zu unterschiedlichen Ergebnissen führt, daher eine eigene Klasse: $[a]$.
• “aa” ist ein Präfix, das zu “aaab” führen kann, daher eine eigene Klasse: $[aa]$.
• “aaa” ist ein Präfix, das nur zu “aaab” erweitert werden kann, eine eigene Klasse: $[aaa]$.
• “aaab” ist eine vollständige Zeichenkette in $L_1$, eine eigene Klasse: $[aaab]$.
• “aaaa” ist eine weitere mögliche Erweiterung, eine eigene Klasse: $[aaaa]$.

Jede dieser Klassen ist distinkt, weil Zeichenketten in verschiedenen Klassen zu unterschiedlichen Ergebnissen führen, wenn man weitere Symbole anhängt.

Schlussfolgerung:

Da die Anzahl der Äquivalenzklassen endlich ist, ist die Sprache $L_1$ regulär. Die Anmerkung besagt, dass jede endliche Sprache regulär sein muss, weil sie nur eine endliche Anzahl von Äquivalenzklassen haben kann.

Diese Lösung bestätigt, dass $L_1$ eine reguläre Sprache mit einem Nerode-Index von 6 ist.

Wir brauchen die Äquivalenzklasse von b nicht, da sie schon in a enthalten ist. Die Äquivalenzklasse von a = b

$$\begin{array}{rl}[\epsilon {]}_L& =\{\epsilon \}\\ [a{]}_{\sim L}& =\{a,b\}\\ [aa{]}_{\sim L}& =\{aa,ab,ba,bb\}\\ ...& \end{array}$$

Falscher Ansatz (aufklappbar)

Lösung für Sprache $L_1$

Sprache: $L_1=\{aaab,aabb,abab,abbb,baab,bbab,bbbb\}$ > Alphabet: ${\Sigma }_1=\{a,b\}$

Nerode-Index und Äquivalenzklassen

Bestimmung: Der Nerode-Index von $L_1$ wird durch Analyse der rechtsinvarianten Äquivalenzrelation bestimmt, bei der zwei Wörter $x$ und $y$ äquivalent sind, wenn für alle $z$ gilt, dass $xz\in L_1$ genau dann, wenn $yz\in L_1$.

Äquivalenzklassen:

1. Klasse 1: Alle Wörter in $L_1$. Anhängen von Zeichen führt aus $L_1$ heraus.
2. Klasse 2: Alle Wörter, die nicht in $L_1$ sind. Anhängen von Zeichen führt nicht in $L_1$ hinein.

Anzahl der Äquivalenzklassen: 2 (endlich)

Regulärität der Sprache

Nach dem Satz von Myhill-Nerode ist eine Sprache regulär, wenn die Anzahl ihrer Äquivalenzklassen endlich ist. Da $L_1$ genau zwei Äquivalenzklassen hat, ist $L_1$ regulär.

Fazit: $L_1$ ist eine reguläre Sprache und kann durch einen endlichen Automaten mit zwei Zuständen dargestellt werden.

2. $L_2=\{w\overline{w}w\mid w\in {\Sigma }_2^{\ast }\}$ mit ${\Sigma }_2=\{a,b\}$

Lösung

Erklärung

Das gegebene Problem bezieht sich auf die Bestimmung der Regularität der Sprache $L_2$ über dem Alphabet ${\Sigma }_2=\{a,b\}$.

Sprache $L_2$:

$L_2=\{w\overline{w}w\overline{w}\mid w\in {\Sigma }_2^{\ast }\}$ mit ${\Sigma }_2=\{a,b\}$

Lösungsvorschlag:

Der Nerode-Index ist unendlich. Betrachte für jedes $i\in \mathbb{N}$ die Wörter $u_i=a^{i}b$ und $w_i=b{a}^{2i}b$. Es ist $u_i{w}_i=a^{i}bb{a}^i{a}^{i}b\in L_2$, aber $u_j{w}_i=a^{j}bb{a}^i{a}^{i}b\notin L_2$ für jedes $j\ne i$. Somit ist $[u_i]\ne [u_j]$ für alle $i\ne j$ und es gibt unendlich viele verschiedene Äquivalenzklassen, d.h. $Index({\sim }_{L_2})=\infty$.

Detaillierte Erklärung zur Bestimmung der Äquivalenzklassen

Um zu zeigen, dass der Nerode-Index unendlich ist, betrachte man die folgenden Schritte:

1. Definition der Wörter: Wir definieren für jedes $i\in \mathbb{N}$ die Wörter $u_i=a^{i}b$ und $w_i=b{a}^{2i}b$.
2. Konstruktion von $u_i{w}_i$: Das Produkt $u_i{w}_i$ ergibt $a^{i}bb{a}^i{a}^{i}b$, welches in der Sprache $L_2$ liegt, da es die Form $w\overline{w}w\overline{w}$ hat.
3. Prüfung von $u_j{w}_i$:
   • Wenn $j\ne i$, dann ist $u_j{w}_i=a^{j}bb{a}^i{a}^{i}b$.
   • Dieses Wort liegt nicht in $L_2$, da die Struktur $w\overline{w}w\overline{w}$ nicht erfüllt ist.
4. Unterschiedlichkeit der Äquivalenzklassen: Da $u_i{w}_i$ in $L_2$ liegt und $u_j{w}_i$ nicht in $L_2$ liegt für $j\ne i$, sind die Äquivalenzklassen $[u_i]$ und $[u_j]$ verschieden für alle $i\ne j$.
5. Unendlichkeit der Äquivalenzklassen: Da es für jedes $i\in \mathbb{N}$ eine eigene Äquivalenzklasse gibt, gibt es unendlich viele Äquivalenzklassen.

Schlussfolgerung:

Da die Anzahl der Äquivalenzklassen unendlich ist, ist die Sprache $L_2$ nicht regulär. Dies bestätigt, dass der Nerode-Index von $L_2$ unendlich ist und somit $L_2$ keine reguläre Sprache ist.

3. $L_3=\{a^i{b}^j{c}^k\mid i,j,k\in \mathbb{N}\text{ und }i=2,\text{ dann }j<k\}$ mit ${\Sigma }_3=\{a,b,c\}$

Falscher Ansatz (aufklappbar)

Sprache: $L_3=\{a^i{b}^j{c}^k\mid i,j,k\in \mathbb{N}\text{ und wenn }i=2,\text{ dann }j<k\}$

Regulärität: $L_3$ ist nicht regulär.

Begründung: Die Sprache $L_3$ enthält eine kontextabhängige Bedingung, die verlangt, dass $j<k$, wenn $i=2$. Diese Bedingung führt zu einer unendlichen Anzahl von Äquivalenzklassen, da für jedes $j$ ein $k$ existieren muss, das größer als $j$ ist. Ein endlicher Automat kann diese kontextabhängige Beziehung nicht verarbeiten, da er nur eine feste Anzahl von Zuständen und Übergängen hat, die keine unendlichen, von den Werten anderer Teile des Wortes abhängigen Bedingungen ausdrücken können.

Schlussfolgerung:

Die unendliche Anzahl und die Art der Äquivalenzklassen, die durch die Bedingung $j<k$ entstehen, überschreiten die Möglichkeiten eines endlichen Automaten, was gemäß dem Myhill-Nerode Theorem zur Nicht-Regulärität der Sprache führt.

ii) Sprache $L_2=\{wwww\mid w\in {\Sigma }_2^{\ast }\}$ mit ${\Sigma }_2=\{a,b\}$:

Bestimmung des Nerode-Index:

Wir zeigen, dass $L_2$ unendlich viele Nerode-Äquivalenzklassen besitzt.

Beweis:

Betrachten wir für jedes Wort $w\in {\Sigma }_2^{\ast }$ das Präfix $x_w=w$. Wir behaupten, dass für jedes Paar verschiedener Wörter $u,v\in {\Sigma }_2^{\ast }$ gilt: $u/{\equiv }_{L_2}v$.

Annahme: Angenommen, es gibt zwei verschiedene Wörter $u,v\in {\Sigma }_2^{\ast }$ mit $u{\equiv }_{L_2}v$.

Widerspruch: Wählen wir $z=uuu$. Dann gilt:

• $uz=uuuu\in L_2$, da $uuuu=wwww$ für $w=u$.
• $vz=vuuu\notin L_2$, außer wenn $v=u$, was aber per Annahme nicht der Fall ist.

Da $uz\in L_2$ und $vz\notin L_2$, sind $u$ und $v$ nicht äquivalent. Somit gibt es für jedes Wort $w\in {\Sigma }_2^{\ast }$ eine eigene Äquivalenzklasse.

Schlussfolgerung:

• Nerode-Index: Unendlich
• Regulärität: $L_2$ ist nicht regulär, da es unendlich viele Äquivalenzklassen gibt.

iii) Sprache $L_3=\{a^i{b}^j{c}^k\mid i,j,k\in \mathbb{N},\text{ und wenn }i=2,\text{ dann }j<k\}$ mit ${\Sigma }_3=\{a,b,c\}$:

Bestimmung des Nerode-Index:

Wir zeigen, dass $L_3$ unendlich viele Nerode-Äquivalenzklassen besitzt.

Beweis:

Betrachten wir die Wörter der Form $x_n=a^2{b}^n$ für $n\in \mathbb{N}$.

Für zwei verschiedene natürliche Zahlen $n$ und $m$ mit $n\ne m$ zeigen wir, dass $x_n/{\equiv }_{L_3}{x}_m$.

Annahme: Angenommen, $x_n{\equiv }_{L_3}{x}_m$.

Wählen wir $z=c^{n+1}$. Dann gilt:

• $x_{n}z=a^2{b}^n{c}^{n+1}\in L_3$, da $j=n<n+1=k$.

• $x_{m}z=a^2{b}^m{c}^{n+1}$:

  • Falls $m>n$: $j=m\ge n+1=k$ ⇒ $j\ge k$ ⇒ $x_{m}z\notin L_3$.
  • Falls $m<n$: $j=m<n+1=k$ ⇒ $x_{m}z\in L_3$.

Da das Ergebnis von $x_{m}z$ vom Wert von $m$ abhängt, unterscheiden sich $x_n$ und $x_m$ hinsichtlich der Zugehörigkeit zu $L_3$. Somit sind sie nicht äquivalent.

Schlussfolgerung:

• Nerode-Index: Unendlich
• Regulärität: $L_3$ ist nicht regulär, da es unendlich viele Äquivalenzklassen gibt.

Zusammenfassung:

• Sprache $L_1$: Regulär mit einem endlichen Nerode-Index von 17 Äquivalenzklassen.
• Sprache $L_2$: Nicht regulär aufgrund eines unendlichen Nerode-Index.
• Sprache $L_3$: Nicht regulär aufgrund eines unendlichen Nerode-Index.

Hinweis: Die detaillierten Beweise für $L_2$ und $L_3$ zeigen, dass es unendlich viele paarweise verschiedene Äquivalenzklassen gibt, was nach dem Satz von Myhill-Nerode die Nicht-Regularität der Sprachen bestätigt.

---

FSK5-2 Pumping-Lemma für kontextfreie Sprachen (2 Punkte)

Aufgabenstellung

Zeigen Sie mit dem Pumping-Lemma für kontextfreie Sprachen, dass die Sprache $L_2=\{w\overline{w}w\mid w\in {\Sigma }^{\ast }\}$ über dem Alphabet $\Sigma =\{a,b\}$ nicht kontextfrei ist.

Lösung

Erklärung

Das gegebene Problem bezieht sich auf die Bestimmung, ob die Sprache $L_2=\{w\overline{w}w\mid w\in {\Sigma }^{\ast }\}$ über dem Alphabet $\Sigma =\{a,b\}$ kontextfrei ist.

Sprache $L_2$:

$L_2=\{w\overline{w}w\mid w\in {\Sigma }^{\ast }\}$

Lösungsvorschlag:

Beweis mit dem Pumping-Lemma.

Sei $n\in {\mathbb{N}}_{>0}$ beliebig.

Wir wählen $z\in L_2$ als $z=a^n{b}^{2n}{a}^{2n}{b}^n$ mit $|z|\ge n$.

Sei $z=uvwxy$ eine beliebige Zerlegung von $z$, sodass $|vx|\ge 1$, $|vwx|\le n$ und $u{v}^{i}w{x}^{i}y\in L$ für jedes $i\in \mathbb{N}$. Wir wählen $i=0$. Sei $z^{\prime }=u{v}^{0}w{x}^{0}y$. Sei $k=|vx|$.

Wegen $|vwx|\le n$ sind nur folgende Fälle möglich:

• $z^{\prime }=a^{n-k_1}{b}^{2n-k_2}{a}^{2n}{b}^n$ mit $k_1+k_2=k\ge 1$. Da $z^{\prime }\in L$ ist, gibt es ein $w$, sodass $z^{\prime }=w\overline{w}w$ ist. Dieses $w$ muss von der Form $a^{\ast }{b}^{\ast }$ sein. Somit muss sowohl $2(n-k_1)=2n$ gelten als auch $2n-k_2=2n$. Diese Aussagen können aber nicht beide wahr sein. Widerspruch.
• $z^{\prime }=a^n{b}^{2n-k_1}{a}^{2n-k_2}{b}^n$ mit $k_1+k_2=k\ge 1$. Dann ist (mit der gleichen Begründung wie oben) $z^{\prime }\in L$ nur wenn sowohl $2n=2n-k_1$ als auch $2n=2n-k_2$ gilt, aber diese Aussagen können nicht beide wahr sein. Widerspruch.
• $z^{\prime }=a^n{b}^{2n}{a}^{2n-k_1}{b}^{n-k_2}$ mit $k_1+k_2=k\ge 1$. Dann ist $z^{\prime }\in L$ nur wenn sowohl $2n=2n-k_1$ als auch $2n=2(n-k_2)$ gilt, aber diese Aussagen können nicht beide wahr sein. Widerspruch.

Detaillierte Erklärung des Beweises

Um zu zeigen, dass die Sprache $L_2$ nicht kontextfrei ist, benutzen wir das Pumping-Lemma für kontextfreie Sprachen. Das Pumping-Lemma besagt, dass für jede kontextfreie Sprache $L$ eine Konstante $n\in \mathbb{N}$ existiert, sodass jede Zeichenkette $z\in L$ mit $|z|\ge n$ in fünf Teile $z=uvwxy$ zerlegt werden kann, wobei:

1. $|vx|\ge 1$
2. $|vwx|\le n$
3. $u{v}^{i}w{x}^{i}y\in L$ für jedes $i\in \mathbb{N}$

Beweis:

1. Wahl der Zeichenkette $z$: Wir wählen $z=a^n{b}^{2n}{a}^{2n}{b}^n$ mit $|z|\ge n$. Diese Wahl von $z$ liegt in $L_2$ und erfüllt die Bedingungen des Pumping-Lemmas.
2. Zerlegung von $z$:
   • Sei $z=uvwxy$ eine beliebige Zerlegung von $z$, sodass $|vx|\ge 1$ und $|vwx|\le n$.
   • Da $|vwx|\le n$, kann $vx$ nur innerhalb eines Blocks von $a$s oder $b$s liegen oder an der Grenze zwischen zwei Blöcken, aber niemals den gesamten Block überschreiten.
3. Pumping und Widersprüche:
   • Fall 1: $z^{\prime }=a^{n-k_1}{b}^{2n-k_2}{a}^{2n}{b}^n$. Da $z^{\prime }\in L$ sein soll, müsste $z^{\prime }$ die Form $w\overline{w}w$ haben, was nicht möglich ist, da $2(n-k_1)=2n$ und $2n-k_2=2n$ nicht gleichzeitig wahr sein können. Widerspruch.
   • Fall 2: $z^{\prime }=a^n{b}^{2n-k_1}{a}^{2n-k_2}{b}^n$. Ähnlich wie oben, können $2n=2n-k_1$ und $2n=2n-k_2$ nicht gleichzeitig wahr sein. Widerspruch.
   • Fall 3: $z^{\prime }=a^n{b}^{2n}{a}^{2n-k_1}{b}^{n-k_2}$. Auch hier können $2n=2n-k_1$ und $2n=2(n-k_2)$ nicht beide gleichzeitig wahr sein. Widerspruch.

Schlussfolgerung:

Da in allen möglichen Fällen ein Widerspruch entsteht, ist die Sprache $L_2$ nicht kontextfrei.

Falscher Ansatz (aufklappbar)

Sprache: $L_2$ über $\Sigma =\{a,b\}$.

Lemma: Das Pumping-Lemma für kontextfreie Sprachen besagt, dass für jede kontextfreie Sprache $L$ eine Pumping-Länge $p$ existiert, sodass jedes Wort $z$ in $L$ mit einer Länge von mindestens $p$ in fünf Teile $uvwxy$ zerlegt werden kann, wobei $|vwx|\le p$, $|vx|>0$ und $u{v}^{i}w{x}^{i}y$ für alle $i\ge 0$ in $L$ bleibt.

Anwendung des Lemmas:

1. Wahl des Wortes: Wähle $w=(ab{)}^p$ und damit $z=w\overline{w}w=(ab{)}^p(ba{)}^p(ab{)}^p$, wobei $z$ eine Länge von $6p$ hat.
2. Zerlegung: $z$ wird gemäß dem Lemma in $uvwxy$ zerlegt, wobei $|vwx|\le p$ und $|vx|>0$.
3. Pumpen: Betrachte $u{v}^{2}w{x}^{2}y$.

Widerspruch:

• Das Pumpen von $v$ und $x$ zerstört die spezifische Struktur $w\overline{w}w$ von $L_2$. Beispielsweise führt das Erhöhen der $ab$-Paare im ersten Segment, ohne die entsprechenden Änderungen in den $(ba{)}^p$ und $(ab{)}^p$ Segmenten, dazu, dass das gepumpte Wort nicht mehr die Form $w\overline{w}w$ hat und somit nicht in $L_2$ sein kann.

Schlussfolgerung: Da das Pumpen von $v$ und $x$ dazu führt, dass das Wort $u{v}^{2}w{x}^{2}y$ nicht mehr in $L_2$ liegt, widerspricht dies dem Pumping-Lemma für kontextfreie Sprachen. Daher ist $L_2$ nicht kontextfrei.

---

FSK5-3 Reguläre und nicht-reguläre Sprachen (0 Punkte)

a)Zeigen Sie, dass die Sprache $a^i{b}^j{c}^k\mid i,j,k\in \mathbb{N}\text{ und wenn }i=2,\text{ dann }j<k$ über dem Alphabet $\Sigma =\{a,b,c\}$ die Pumping-Eigenschaft erfüllt.

Lösung

Erklärung

Das gegebene Problem bezieht sich auf die Überprüfung, ob die Sprache $\{a^i{b}^j{c}^k\mid i,j,k\in \mathbb{N}\text{ und wenn }i=2,\text{ dann }j<k\}$ über dem Alphabet $\Sigma =\{a,b,c\}$ die Pumping-Eigenschaft für reguläre Sprachen erfüllt.

Sprache:

$\{a^i{b}^j{c}^k\mid i,j,k\in \mathbb{N}\text{ und wenn }i=2,\text{ dann }j<k\}$

Lösungsvorschlag:

Wir wählen $n=4$.

Sei $z=a^i{b}^j{c}^k\in L$ mit $|z|\ge n$.

Wir müssen für jedes solche $z$ eine Zerlegung $z=uvwxy$ angeben mit $|uvw|\le n$, $|vwx|\ge 1$ und $u{v}^{i}w{x}^{i}y\in L$ für alle $i\in \mathbb{N}$.

Vollständige Fallunterscheidung:

• Fall 1: $i<4$ und $i\ne 2$. Wegen $|z|\ge 4$ ist $j\ge 1$ oder $k\ge 1$.

  • Unterfall 1.1: $j\ge 1$: Wähle die Zerlegung $u=a^i$, $v=b$, $w=b^{j-1}{c}^k$ mit $|uv|\le 4$ und $|v|\ge 1$. Es ist $u{v}^{i}w{x}^i\in L$ für jedes $i\in \mathbb{N}$, da die Anzahl der $a$‘s in $u{v}^{i}w{x}^i$ immer $i\ne 2$ bleibt und somit die Anzahl der $b$‘s und $c$‘s irrelevant ist.
  • Unterfall 1.2: $j=0$: Wähle die Zerlegung $u=a^i$, $v=c$, $w=c^{k-1}$. Diese Zerlegung erfüllt mit analoger Begründung alle Bedingungen.

• Fall 2: $i\ge 4$: Wähle die Zerlegung $u=a^3$, $v=a$, $w=a^{i-4}bj{c}^k$ mit $|uv|\le 4$ und $|v|\ge 1$. Es ist $u{v}^{i}w{x}^i\in L$ für jedes $i\in \mathbb{N}$, da die Anzahl der $a$‘s in $u{v}^{i}w{x}^i$ immer mindestens 3 ist und somit die Anzahl der $b$‘s und $c$‘s irrelevant ist.

• Fall 3: $i=2$: Wähle die Zerlegung $u=\epsilon$, $v=aa$, $w=bj{c}^k$. Es ist $u{v}^{i}w{x}^i\in L$ für jedes $i\in \mathbb{N}$, denn:

  • Für $i=1$ ist $u{v}^{1}w{x}^1=z\in L$.
  • Für $i\ne 1$ enthält $u{v}^{i}w{x}^i$ nicht genau 2 $a$‘s und somit ist die Anzahl der $b$‘s und $c$‘s wieder irrelevant.

Schlussfolgerung:

Die Sprache erfüllt die Pumping-Eigenschaft für reguläre Sprachen, da in allen möglichen Fällen eine geeignete Zerlegung gefunden werden kann, sodass die Bedingungen des Pumping-Lemmas erfüllt sind.

Falscher Ansatz (aufklappbar)

Um zu zeigen, dass die Sprache $L=\{a^i{b}^j{c}^k\mid i,j,k\in \mathbb{N}\text{ und }i=2\Rightarrow j<k\}$ die Pumping-Eigenschaft erfüllt, nutzen wir das Pumping-Lemma für reguläre Sprachen. Dieses besagt, dass es eine Pumping-Länge $p$ gibt, so dass jedes Wort $s$ in $L$ mit einer Länge $\ge p$ so in drei Teile $x,y,z$ zerlegt werden kann, dass gilt:

1. $x{y}^{m}z$ ist ein Wort in $L$ für alle $m\ge 0$,
2. $|xy|\le p$,
3. $|y|>0$.

Beispiel:

Wähle $i=2,j=1,k=2$, dann ist $s=a^2{b}^1{c}^2$ ein gültiges Wort in $L$, da $i=2$ und $j<k$.

Teile $s$ in $x=a^2$, $y=b$, $z=c^2$:

• $xy=a^{2}b$ und $|xy|=3\le p$ (angenommen $p\ge 3$),
• $|y|=1>0$.

Für $m\ge 0$, das Wort $x{y}^{m}z=a^2{b}^m{c}^2$ bleibt gültig in $L$ solange $m<2$, weil wenn $i=2$, dann $j=m<k=2$ erfüllt sein muss.

Fazit:

Dieses Beispiel zeigt, dass die Sprache die Pumping-Eigenschaft erfüllt, solange das gepumpte Wort $y$ die Bedingung $i=2\Rightarrow j<k$ nicht verletzt. Da das Pumping-Lemma für reguläre Sprachen nur fordert, dass es möglich sein muss, ein Wort zu pumpen und in der Sprache zu bleiben, reicht ein Beispiel, um die Erfüllung der Pumping-Eigenschaft zu demonstrieren.

---

b) Sind die folgenden Sprachen $L_i$, $i\in \{1,2,3\}$, über den Alphabeten ${\Sigma }_i$ regulär? Wenn ja, geben Sie einen regulären Ausdruck an, der $L_i$ erkennt. (Sie müssen nicht beweisen, dass der reguläre Ausdruck $L_i$ erkennt.) Wenn nein, zeigen Sie die Nichtregularität mit dem Pumping-Lemma für reguläre Sprachen.

1. $L_1=\{a{c}^{i}b{a}^{j}b\mid i,j\in \mathbb{N}\}$ mit ${\Sigma }_1=\{a,b,c\}$

   Lösung: $L_1$ ist regulär. Ein regulärer Ausdruck, der $L_1$ erkennt, ist:

   $$a{c}^{\ast }b{a}^{\ast }b$$

2. $L_2=\{a^p{b}^p\mid p\in \mathbb{N}\text{ ist prim}\}$ mit ${\Sigma }_2=\{a,b\}$

   Lösung: $L_2$ ist nicht regulär. Wir zeigen dies mit dem Pumping-Lemma:

   • Angenommen, $L_2$ sei regulär. Dann gibt es eine Pumping-Länge $p$.
   • Wähle $s=a^p{b}^p$, wobei $p$ eine Primzahl ist und $|s|\ge p$.
   • Zerlege $s$ in $xyz$, wobei $|xy|\le p$ und $|y|>0$.
   • Da $|xy|\le p$, enthält $xy$ nur $a$‘s. Also besteht $y$ nur aus $a$‘s.
   • Pumpen von $y$: $x{y}^{2}z$ ergibt mehr $a$‘s als $b$‘s, was nicht in $L_2$ liegt. Widerspruch.

   Also ist $L_2$ nicht regulär.

3. $L_3=\{a^{2n+1}\mid n\in \mathbb{N}\}$ mit ${\Sigma }_3=\{a\}$.

   Lösung: $L_3$ ist regulär. Ein regulärer Ausdruck, der $L_3$ erkennt, ist:

   $$a(aa{)}^{\ast }$$

---

FSK5-4 Konservative Erweiterungen regulärer Ausdrücke (0 Punkte)

Aufgabenstellung

In der Praxis werden reguläre Ausdrücke häufig mit weiteren Operatoren erweitert. Eine solche Erweiterung ist konservativ, wenn die erweiterten regulären Ausdrücke nur reguläre Sprachen beschreiben. Geben Sie in jeder Teilaufgabe an, ob die beschriebene Erweiterung konservativ ist, und beweisen Sie Ihre Antwort. Dabei sei $\alpha$ ein regulärer Ausdruck über einem beliebigen Alphabet.

a) $\alpha ?$: Teilwörter, die von $\alpha$ erkannt werden, dürfen vorkommen, müssen aber nicht. Die Semantik von $\alpha ?$ ist also $L(\alpha ?)=\{ϵ\}\cup L(\alpha )$.

Lösung:

Die Erweiterung $\alpha ?$ ist konservativ. Dies lässt sich wie folgt begründen:

Ein regulärer Ausdruck $\alpha ?$ erkennt entweder das leere Wort $ϵ$ oder jedes Wort, das von $\alpha$ erkannt wird. Da $\alpha$ ein regulärer Ausdruck ist, beschreibt $L(\alpha )$ eine reguläre Sprache. Das leere Wort $ϵ$ gehört immer zur Menge der regulären Sprachen. Die Vereinigung einer regulären Sprache mit dem leeren Wort ist ebenfalls eine reguläre Sprache.

Daher beschreibt $\alpha ?$ immer eine reguläre Sprache, und die Erweiterung ist konservativ.

b) ${\alpha }^{+}$: wie ${\alpha }^{\ast }$, aber $\alpha$ muss mindestens einmal vorkommen.

$$L({\alpha }^{+})=\bigcup _{i\in \mathbb{N}>0}L(\alpha {)}^i=L(\alpha )\cup L(\alpha {)}^2\cup L(\alpha {)}^3\cup \dots$$

Lösung:

Die Erweiterung ${\alpha }^{+}$ ist konservativ. Dies lässt sich wie folgt begründen:

Ein regulärer Ausdruck ${\alpha }^{+}$ erkennt alle Wörter, die mindestens einmal aus $\alpha$ bestehen. Das bedeutet, $L({\alpha }^{+})$ ist die Vereinigung der Sprachen $L(\alpha )$, $L(\alpha {)}^2$, $L(\alpha {)}^3$, usw. Da die Konkatenation und Vereinigung regulärer Sprachen wieder reguläre Sprachen ergeben, ist $L({\alpha }^{+})$ regulär.

Daher beschreibt ${\alpha }^{+}$ immer eine reguläre Sprache, und die Erweiterung ist konservativ.

c) ${\alpha }^{\{i,j\}}$ mit $i,j\in \mathbb{N}$ und $i\le j$: wie ${\alpha }^{\ast }$, aber $\alpha$ muss mindestens $i$-mal und darf höchstens $j$-mal wiederholt werden.

$$L({\alpha }^{\{i,j\}})=\bigcup _{k=i}^{j}L(\alpha {)}^k=L(\alpha {)}^i\cup L(\alpha {)}^{i+1}\cup L(\alpha {)}^{i+2}\cup \dots \cup L(\alpha {)}^j$$

Lösung:

Die Erweiterung ${\alpha }^{\{i,j\}}$ ist konservativ. Dies lässt sich wie folgt begründen:

Ein regulärer Ausdruck ${\alpha }^{\{i,j\}}$ erkennt alle Wörter, die aus $\alpha$ bestehen und mindestens $i$-mal und höchstens $j$-mal vorkommen. Das bedeutet, $L({\alpha }^{\{i,j\}})$ ist die Vereinigung der Sprachen $L(\alpha {)}^i$, $L(\alpha {)}^{i+1}$, $L(\alpha {)}^{i+2}$, usw., bis $L(\alpha {)}^j$. Da die Konkatenation und Vereinigung regulärer Sprachen wieder reguläre Sprachen ergeben, ist $L({\alpha }^{\{i,j\}})$ regulär.

Daher beschreibt ${\alpha }^{\{i,j\}}$ immer eine reguläre Sprache, und die Erweiterung ist konservativ.

d) $\backslash n$ mit $n\in \mathbb{N}$. In einem regulären Ausdruck $\alpha$ bezeichnen wir den $n$-ten Teilausdruck der Form $({\alpha }_0)$ (wobei ${\alpha }_0$ ein regulärer Ausdruck ist) als die $n$-te Capturing Group. Ein Teilausdruck $\backslash n$ in $\alpha$ wird dann als Backreference bezeichnet und erkennt genau die Zeichenkette, die von ${\alpha }_0$ erkannt wurde. Beispielsweise erkennt $(a|b)\backslash 1$ die Wörter aa und ab, aber nicht ab oder ba.

Lösung:

Die Erweiterung $\backslash n$ ist nicht konservativ. Dies lässt sich wie folgt begründen:

Backreferences sind nicht durch endliche Automaten erkennbar, da sie sich auf vorherige Teile des Eingabewortes beziehen und somit eine Art Gedächtnis erfordern, das endliche Automaten nicht haben. Daher können sie kontextfreie oder sogar kontextsensitive Sprachen beschreiben, die nicht notwendigerweise regulär sind.

Ein Beispiel dafür ist der reguläre Ausdruck $(a|b)\backslash 1$, der die Sprache $\{aa,bb,ab\}$ beschreibt. Diese Sprache kann nicht durch einen endlichen Automaten erkannt werden, da der Automat das erste Symbol speichern und mit dem zweiten Symbol vergleichen müsste.

Daher beschreibt $\backslash n$ nicht immer eine reguläre Sprache, und die Erweiterung ist nicht konservativ.

---