0 Daumen
48 Aufrufe

Aufgabe:

Ist die folgende Sprache kontextfrei? L= {w ∈ {a,b}* | w = 0n1m0n, mit n, m ∈ ℕ, n < m}.


Problem/Ansatz:

Mein Vermutung ist, dass L nicht kontextfrei ist. Das denke ich, da ich keinen NPDA bauen kann, bei dem ich überprüfen kann wie viele 1en ich gelesen habe.

Nun wollte ich dafür das Pumping Lemma verwenden.

Mein Ansatz wäre nun, die beiden 0n aufzupumpen, damit ich |w| ≥ 2N habe.

Leider weiß ich nicht so richtig, wie ich jetzt die Zerlegung w = uvwxy richtig angehe.

Ich habe überlegt, ob es Sinn macht, vwx in 3 Fällen zu betrachten:

1. vwx = 000...111...---

2. vwx = ---111....---

3. vwx = ---111....000...

von

Lege für jede am Anfang gelesene 0 einen Buchstaben auf den Stapel.

Konsumiere die folgenden Einsen.

Entferne für jede nun gelesene 0 einen Buchstaben vom Stapel.

Das ist der Kellerautomat, wenn man die Bedingung n < m überliest.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community