Ist die folgende Sprache kontextfrei?

Question

Aufgabe:

Ist die folgende Sprache kontextfrei? L= {w ∈ {a,b}* | w = 0ⁿ1^m0ⁿ, 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 0ⁿ 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...

Comments

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.