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

Question

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!

Answer 1

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