0 Daumen
401 Aufrufe

Frage:

Zeigen Sie, dass folgende Sprachen nicht regulaär sind:

B={ xxrev |x∈{0,1}*}
Hierbei definieren wir xrev := xl xl−1 · · · x2x1, wenn x = x1x2 · · · xl−1xl.

Lösung:

Sei x = uvw, wir nehmen u= ε, v= 11000 und w= 00011, uvw∈B.

Sei v = yzt mit |y| > 0. Wir nehmen y=1, z= 100 und t = 0. Dann nach Dumping Lemma haben wir x = 1x((100)hoch i )000011.

Falls wir i=2 nehmen dann x= 110010000011 ∈ B.

Deshalb ist B nicht regulär.


Problem:

Ist das ein gültiges Beweis? Falls nein, was soll ich ändern?


Danke.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community