zeige mit dem pumping-lemma,dass die sprache nicht regulär ist

Question

zeigen sie mit dem pumping-lemma ,dass die folgenden sprache nicht regulär ist:

L1 ={ y^k | k ≥ 2 und y ∈ {a,b}* } ⊆ { a,b}*

Achten sie auf vollständige beweisstruktur.

Comments

Junge, du kannst doch nicht einfach dein ganzes Übungsblatt der theoretischen Informatik an der HHU hier rein stellen, mach doch mal was selbst.

---

Also dieses Video könnte helfen:

https://www.youtube.com/watch?v=kZzH8E-s-9o

---

Ok, die Sprache ist schon sehr anders als auf dem Video. Aber in dieser Aufgabe muss man bedenken, dass k≥2 ist, also y mindesten 2 Buchstaben hat. Wäre dem nicht so, wäre L glaube ich regulär. Weil man könnte sonst jedes Wort beliebig in uvw einteilen und trotzdem wäre sogar für i = 0 =>

uv^{i}w ∈ L, egal für welches w. Da hier aber k≥2 gilt, wäre für i = 0 und w = y^1 dann uvw ∉ L, denn jedes Wort hat wie gesagt mindestens 2 Buchtaben.

---

Korrigiere:

[...] für i = 0 und w = y^0 dann uvw ∉ L denn jedes Wort hat wie gesagt mindestens 2 Buchtaben.

---

Habe die Sprache etwas falsch verstanden:

Also, alle Wörter dieser Sprache werden aus mindestens zwei gleiche Wörtern (die aus den Buchtaben „a” und „b” gebildet werden) zusammengesetzt.

Also das Video würde doch helfen ;).

Answer 1

Ich brauche hilfe mit dem folgenden:

A = {a^m a^L cb^(m+1) | m,L∈ N}

Wie beweist man, dass diese Sprache nich regulär ist