0 Daumen
299 Aufrufe

Frage:


Zeigen oder Widerlegen Sie:
Für jede kontextfreie Sprache \( L \) gilt, dass \( L^{+}:=\left\{w^{n} \mid w \in L, n \geq 1\right\} \) kontextfrei ist.


Code:

ich habe die starke Vermutung, dass man das mit dem Pumping Lemma lösen kann, aber ich habe das noch nie gemacht, kann mir jemand eine "Anleitung" geben?


mfg

ulong

Avatar von

Hallo,

ich habe jetzt folgenden Tipp bekommen:"Da L kontextfrei ist, gibt es eine CFG, die genau L erzeugt. Sei G eine solche.

Entferne aus ihren Produktionen alle Regeln, mittels derer sich das leere Wort ableiten lässt. Gehe hierbei so sparsam wie möglich vor.
Also salopp gesprochen: Streiche alle ε aus rechten Regelseiten.
Wenn danach eine rechte Regelseite leer ist, entferne diese Regel komplett.

Die entstehende Grammatik ist kontextfrei, da die linken Regelseiten nicht verändert werden.

Also gilt die Behauptung: Zu jeder kontextfreien Sprache L ist L+ kontextfrei."

Aber wie soll ich das genau aufschreiben? Also ich weiß auch nicht wie ich das Formal aufschreiben soll.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community