Unverständnis der Bemerkung in der Lösung

Question

Bei dieser Aufgabe (66) habe ich eine Frage zu der Bemerkung, die in der Lösung gemacht wird.

 

Es wird geschrieben, dass $L' = \{0^i1^i2^j3^j \ | \ i, j \in \mathbb{N}\}$ und $L'' = \{0^i1^j2^j3^i\ | \ i, j \in \mathbb{N}\}$ kontextfrei sind. 

 

$L=\{0^i1^j2^i3^j\ | \ i,j \in \mathbb{N}\}$ ist nicht kontextfrei, wie es in der Aufgabe gezeigt wird. 

 

Das finde ich noch nachvollziehbar und mit dem Kellerautomaten gut vorstellbar!

Wenn ich aber mit dem Pumping-Lemma prüfen wollte, ob $L'$ oder $L''$  kontextfrei sind, würde ich auf ein anderes Ergebnis kommen:

 

Ich würde in beiden Fällen das selbe "Testwort" nehmen wie für $L$, nämlich: $z = 0^k1^k2^k3^k$

Mit dem selben Startwort, käme ich allerdings auch auf das selbe Ergebnis: Die Sprache ist nicht kontextfrei. 

 

Wie ist das zu erklären? Ist  $z = 0^k1^k2^k3^k$  kein gültiges Startwort für $L'$ oder $L''$?

Comments

Hey,

könntest du mir grad sagen wo geschrieben steht, dass L' und  L'' kontextfrei sind?

Danke!

---

Das steht in den Lösungen zu Aufgabe 66:

"Bemerkung: Es mag überraschen, dass eine Sprache, die eine so einfache Struktur hat wie $L = \{0^i1^j2^i3^j\ | \ i, j \in \mathbb{N}\}$ nicht kontextfrei ist, während "ähnliche" Sprachen wie beispielsweise $L' = \{0^i1^i2^j3^j\ | \ i, j \in \mathbb{N}\}$ oder $L'' = \{0^i1^j2^j3^i\ | \ i, j \in \mathbb{N}\}$ kontextfrei sind. Der Grund für die Schwierigkeit von $L$ liegt in der Verschränkung der Blöcke, die jeweils gleich viele Zeichen haben sollen, ineinander. Salopp gesagt müsste ein Kellerautomat sich zunächst sowohl die Anzahl der Nullen als auch die Anzahl der Einsen merken, indem er entsprechend viele Zeichen in den Keller schreibt; dann müsste er die Anzahl der Nullen mit der Anzahl der Zweien vergleichen, die Nullen liegen aber unter den Einsen und können wegen des LIFO-Prinzips nicht betrachtet werden."

---

Wie würden Sie für Ihr Testwort denn mit dem PPL argumentieren? (Es kann ja nicht funktionieren, also müssen wir herausfinden, wo Ihr Denkfehler liegt :-) )

Answer 1

Hallo Maximilian,

Die beiden Sprachen L' und L'' kannst du dir schön im Kellerautomaten vorstellen, damit wird auch klar wieso diese beiden kontextfrei sind.

Bei L={0$^i$1$^i$2$^j$3$^j$ | i,j $\in$ $\mathbb{N}$} legt der Kellerautomat zuerst die 0 in den Keller, prüft anschließend ob es genau so viele 1 gibt, anschließend sollte der Keller leer sein, danach überprüft er das selbe mit 2 und 3.

Bei L''={0$^i$1$^j$2$^j$3$^i$ | i,j $\in$ \mathbb{N}}legt der Kellerautomat alle 0er ab, danach alle 1er, prüft ob es gleich viele 2er wie 1er gibt und anschließend prüft er ob es gleich viele 3er wie 0er gibt. Nach dem LiFo Prinzip, ist es relativ anschaulich wie ein Kellerautomat so etwas akzeptieren könnte.

 

Ich hoffe ich konnte dir helfen, falls du noch weitere Fragen hast stelle sie gerne :)

 

Viele Grüße,

 

Marc (Tutor)

Comments

Hallo Marc,

ich habe schon verstanden, dass die beiden Sprachen L' und L'' kontextfrei sind und verstehe auch, warum!
Meine Frage ist eigentlich die folgende:
Wenn ich mit dem Pumping-Lemma ein Gegenbeispiel für L' oder L'' suche, finde ich es relativ schnell: Ich wähle das Wort z = 0^k 1^k 2^k 3^k, welches sowohl Element der Sprache L' als auch L'' ist. Von diesem Punkt aus argumentiere und verfahre ich wie beim Pumping-Lemma für die Sprache L, was in Aufgabe 66 beschrieben wird. Somit komme ich auf das Ergebnis:
L' und L'' sind nicht kontextfrei (wie auch L).

Wo ist jetzt der Fehler in meinem Vorgehen bezüglich des Pumping-Lemmas?
Wieso ist z = 0^k 1^k 2^k 3^k kein gültiges Startwort für L' oder L'', für L aber schon??

---

Wie würden Sie denn genau argumentieren? Das Problem ergibt sich ja erst im Detail. Schreiben Sie bitte einmal genau auf, wie Ihr Beweis laufen würde. (Am besten als Edit in Ihre originale Frage.)

---

Ich habe das nicht vollständig ausformuliert, glaube aber, meinen Denkfehler gefunden zu haben.
Ich bin davon ausgegangen, dass das selbe Startwort beim Pumping-Lemma auch immer zur selben Lösung (kontextfrei oder nicht) führt. Dabei habe ich die gegebene Grammatik völlig außer Acht gelassen. Dass sich die Argumentationen nach dem "Pumpen" bei L und L'/L'' unterscheiden, hatte ich nicht bedacht.
Unter diesen Aspekten ist es tatsächlich nicht möglich, mithilfe des Lemmas ein Gegenbeispiel für L' oder L'' zu finden, wovon ich anfangs ausgegangen bin.
Somit ist meine Frage geklärt.
Vielen Dank für die schnellen Antworten!!

---

Das habe ich mir fast schon gedacht - und deshalb so gefragt :-)

---

Hallo, bin eben auf die Frage gestoßen und habe mir das ganze mal angeschaut.
Leider treffe ich auf ähnliches Problem, wenn ich analog wie in Aufgabe 66 bis zu den drei Fällen vorgehe.
Erster Fall:
Die Anzahl der Nullen ist kleiner als die Anzahl der Zweien, somit wäre L'' nicht kontextfrei.
Zwar würde Fall zwei für L'' passen, Fall drei jedoch nicht. Müssen bei solch einer Fallunterscheidung alle Fälle der Sprache widersprechen?

Kann mir da jemand weiterhelfen?