Beweis zur gespiegelten Sprache?
Hallo,
ich habe hier eine Aufgabe bei der ich nicht weiter komme und hoffe hier etwas Hilfe zu bekommen oder einen Ansatz wie ich voran kommen würde.
Die Aufgabe lautet:
Sei Σ ein Alphabet und A ⊆ Σ ∗ eine Sprache. Wir definieren die gespiegelte Sprache von A als A^ rev = {w | w ^rev ∈ A}.
1. Sei B = {a,aab,abb,abababba}.Geben Sie B rev explizit an.
Dies habe ich wie folgt gelöst: (a, aab, abb, abababba)^rev = a, baa, bba, abbababa
wobei a ein Palindrom ist.
2. Sei L ∈ REG eine beliebige Sprache. Beweisen Sie L^rev ∈ REG.
Bei dem Beweis hier komme ich lediglich nicht weiter. Ich weiß nicht wie ich das im allgemeinen zeigen soll, dass L^rev ∈ REG ist.
Habt ihr Vorschläge? Ich wäre euch sehr dankbar. :)
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.
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.
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?