L konkateniert mit Umkehrung regulär

Smith
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 13. Apr 2015 15:45

L konkateniert mit Umkehrung regulär

Beitrag von Smith » 11. Mär 2017 13:57

Hallo,
ich habe eine Aufgabe zu der es keine Lösung gibt, aber vielleicht könnt ihr ja einschätzen, ob ihr das auch so gelöst hättet, oder ob meine Antwort eurer Meinung nach durchgehen würde.

Die Aufgabe lautet:
Zeigen Sie, dass für jede reguläre Sprache \(L\) auch \(LL^{-1}\) regulär ist, wobei \(L^{-1} := \{w^{-1} : w \in L\}\).

Meine Antwort wäre ziemlich straight forward:
Aus der VL wissen wir, dass für jede reguläre Sprache \(L \subseteq \Sigma^*\) auch ihre Umkehrung von einem NFA erkannt wird.
Wegen \(L \text{ erkennbar } \Longleftrightarrow L \text{ regulär}\) ist \(L^{-1}\) also regulär.
Weiter wissen wir durch die Abschlusseigenschaften regulärer Sprachen, dass die Konkatenation zweier regulärer Sprachen wieder eine reguläre Sprache erzeugt.
Wir haben gesehen, dass \(L\) und \(L^{-1}\) regulär sind, somit ist \(LL^{-1}\) regulär.

Irgendwelche Einwände oder Bestätigungen?
Danke!
Phil

Zurück zu „Archiv“