Beweis zur gespiegelten Sprache?

1 Antwort

zu 1: Rein formal solltest Du die Mengenklammern in deiner Lösung beibehalten.

zu 2: Nimm eine rechtsreguläre Grammatik für L und drehe alle Regeln um (aus X→Yw wird X→wY). Dann hast Du eine linksreguläre Grammatik für L^rev.

Wäre es dann im Prinzip in Ordnung wenn ich ein beliebiges Beispiel also eine beliebige Sprache L angebe mit der zugehörigen Grammatik und dessen Regeln dann einfach umdrehe?

1
@KHTM21

Grundsätzlich schon. Sei Dir aber bewusst, dass ein Beispiel kein Beweis ist. Insbesondere musst Du natürlich beweisen, dass die so konstruierte Grammatik tatsächlich L^rev erzeugt.

Vielleicht hat ja jemand Anderes eine bessere Beweisidee, die formal leichter aufzuschreiben ist. Stell die Frage einfach nochmal ein.

1

Was möchtest Du wissen?