0 Daumen
147 Aufrufe

Aufgabe:

Beweisen Sie mit Hilfe des Pumping-Lemmas: Die Sprache L = {w ∈ {a,b}∗ | |w|a = 2 · |w|b} über dem Alphabet Σ = {a,b} ist nicht regulär.


Problem/Ansatz:

Ich habe zunächst einmal das Wort

V= a^2|b| b gewählt

Mit den zerlegungen kommt man auf

X= a^j

Y=a^k

Z=a^2|b|-j-k b

Wähle v'=xy^i z = xyyz= a^j a^k a^k a^2|b|-j-k b

Zusammengefasst a^k a^2|b| b nicht regulär

Geht das so?

von

1 Antwort

0 Daumen
Ich habe zunächst einmal das Wort V= a2|b| b gewählt

|b| ergibt keinen Sinn.

Sei N die Pumpingzahl.

Wähle aNb2N als Wort zum Pumpen.

von 2,9 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community