Abgeschlossenheit "rückwärts" < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:52 Mi 03.05.2006 | | Autor: | dobberph |
| Aufgabe | | Zeigen Sie, dass die Klasse der regulären Sprachen abgeschlossen ist unter "rückwärts Lesen", d.h. L' = {w [mm] \varepsilon [/mm] A | w = [mm] x_{k} x_{k-1} x_{k-2} [/mm] . . . [mm] x_{1} [/mm] und [mm] x_{1} x_{2} x_{3} [/mm] . . . [mm] x_{k} \varepsilon [/mm] L} ist regulär, falls L regulär ist. |
Hi ihr,
Ansatz:
Annahme: Zu jeder endlichen Sprache gibt es einen endlichen Automaten.
1.) Vertausche bei dem Automaten Start- und Endzustand
2.) Vertausche die Richtungen der Überführungsfunktionen
Das Ergebnis akzeptiert alle Wörter der Ursprungssprache rückwärts gelesen.
Reicht das? Oder erwische ich damit nicht alle Fälle?
Danke,
DerTobi
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Tobi,
ja, der Ansatz ist genau richtig. Arbeite aber vielleicht noch genauer heraus,
dass Du zB mit einem deterministischen Automaten für L startest und der Automat für
die Sprache ''L rückwärts'' zunächst nichtdeterministisch ist (Du kannst ja dann
über Potenzautomatenkonstruktion wieder einen deterministischen erhalten).
Insbesondere solltest Du jetzt auch Deine Konstruktion formalisieren.
Gruss,
Mathias
|
|
|
|
