Zeigen Sie mit Hilfe des Pumping Lemmas, dass die von G erzeugte Sprache L(G) nicht regulär ist.

Question

Ist mein Beweis mit dem Pumping Lemma richtig, um zu beweisen, dass die Sprache nicht regulär ist?

Aufgabe:

Wir betrachten die folgende Grammatik, die genau die korrekt geklammerten Additionen der Bezeichner \( a \) und \( b \) enthält: \( G=(\{(, \mathrm{a},+, \mathrm{b})\},,\{S\}, S, P) \) mit
\( P=\{S \rightarrow(S)|S+S| \mathrm{a} \mid \mathrm{b}\} \)
Zeigen Sie mit Hilfe des Pumping Lemmas, dass die von \( G \) erzeugte Sprache \( L(G) \) nicht regulär ist.

Meine Lösung:

Angenommen L∈R. Sei n die Zahl, die nach dem Pumping-Lemma für L(G) existiert.

Wir betrachten aus Wort (^[n-3] a+b )^[n-3] mit |x| = 2(n-3)+3 = 2n-3 > n.

Da x ∈ L(G), lässt sich x so in x = uvw = (^[n-3] a+b )^[n-3] zerlegen, das gilt:

1. |uv| ≤ n, d.h. uv = (^[n-3] a+b

2. |v| ≥ 1, d.h. v = a+b

3. ( ∀ i ≥ 0) [uv^iw ∈ L(G)]

   Für i = 2:

        uv^2w = (^[n-3] a+ba+b )^[n-3] ∈ L(G),

was ein Widerspruch zur Definition von L(G) ist. Also ist L(G) nicht regulär.

Answer 1

Wir betrachten aus Wort (^[n-3] a+b )^[n-3] mit |x| = 2(n-3)+3 = 2n-3 > n.

Was ist x?

|uv| ≤ n, d.h. uv = (^[n-3] a+b

Nein. Da steht |uv| ≤ n, nicht |uv| = n.

Wähle das Wort stattdessen so, dass öffnende Klammern hochgepumpt werden müssen.

Begründe warum ein so erhaltenes Wort nicht durch die Grammtik erzeugt werden kann.

|v| ≥ 1, d.h. v = a+b

Nein. Es könnte auch v = b oder v = +b oder v = (a+b oder v = ((a+b etc sein.

was ein Widerspruch zur Definition von L(G) ist

Das ist richtig, das aufgepumpte Wort kann nicht durch G erzeugt werden. Eine Begründung dafür fehlt aber.