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.