Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

"Kochrezept" für reguläre Ausdrücke?

+3 Punkte
183 Aufrufe
Hallo,

gibt es eine Art Kochrezept zum erstellen von Regulären Ausdrücken aus endlichen Automaten?

Einige Parallelen denke ich sind offensichtlich, wie dass z.b. eine Schleife später wie ein * behandelt wird, aber bei komplexen Aufgaben wie in diesem Fall, ist es gar nicht so einfach alle Fälle abzudecken. Oft vergisst man beispielsweise die trivialen Wörter und bei vielen Klammern fehlt mir meist auch ein bisschen der Überblick.

Da jede reguläre Sprache ja aber durch einen endlichen Automaten und einen regulären Ausdruck dargestellt werden kann, müssen hier doch bestimmt Parallelen liegen, sodass durch ein einfaches Vorgehen die Automaten in reguläre Ausdrücke transformiert werden können, oder nicht?

Meines Wissens haben wir kein Verfahren dieser Art kennen gelernt. Falls doch würde ich mich freuen, wenn mir jemand sagen könnte wo ich dieses im Skript oder in den Übungsaufgaben fnden kann.

Vielen Dank!
Gefragt 16, Jan 2016 in REC-AI von updrr updrr Eins-Komma-Null-Anwärter(in) (3,790 Punkte)  

Eine Antwort

+1 Punkt
Leider ist das mit regulären Ausdrücken nicht ganz so einfach. Ja, sie sind auf endliche Automaten abbildbar und umgekehrt, aber der Algorithmus EA => RA ist nicht ganz einfach und führt vor allem oft zu sehr großen regulären Ausdrücken. Sie können das ja im XWizard testen, indem Sie bei einem endlichen Automaten auf die Konversionsmethode "Regulärer Ausdruck" klicken. Der Algorithmus, der dort implementiert ist, kann im "Hopcroft/Ullman" nachgelesen werden, siehe Info-II-Literaturliste, aber er geht deutlich über die Vorlesung hinaus.

Kurz gesagt, wir werden Ihnen in der Klausur sicher nur einfache endliche Automaten (bzw. reguläre Ausdrücke) zum Umwandeln vorsetzen - und Sie brauchen dann halt ein "gutes Auge", das heißt eben etwas Übung, um solche Aufgaben zu lösen.

Ein paar "Kochrezepte" für Spezialfälle gibt es natürlich schon, etwa, dass es sinnvoll ist, sich von Endzuständen aus entlangzuhangeln.

Viele Grüße

Lukas König
Beantwortet 16, Jan 2016 von Lukas König Dozent (10,065,100 Punkte)  
Eindeutigkeit Lösung reguläre Ausdrücke
...