0 Daumen
2,4k Aufrufe

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.

Avatar von

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:


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 ;).

1 Antwort

0 Daumen

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

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community