Reguläre Ausrücke in endlichen Automaten umwandeln

[aline234]

Hallo,

kann mir jemand einfach und verständlich erklären, wie man einen regulären Ausdruck in einen Automaten umwandelt? Ich könnte natürlich die reguläre Sprache dazu ermitteln, Grammatikregeln aufstellen und anhand dessen den Automaten entwickeln, aber das empfinde ich irgendwie als zu umständlich.

Über ein einfaches Howto oder einfache Regeln zur Vorgehensweise wäre ich dankbar!

LG,

Aline

[flashpixx]

Der formale Weg ist wirklich so wie Du es beschrieben hast. In den meisten Fällen klappt das aber mit "scharf hinschauen" und mit entsprechender Übung. Ein praktischer Tip ist es, erst einmal den gesamten Ausdruck in Teilausdrücke mit den entsprechenden Quantoren zu zerlegen und für jeden Teilausdruck den Automaten aufzustellen und dann die Teilautomaten noch vernetzen.

[Klotzkopp]

Es gibt ein paar einfache Regeln, um aus einem regulären Ausdruck einen nichtdeterministischen endlichen Automaten zu konstruieren, die finde ich nur grad nicht.

Aus dem NEA kann man dann mit der üblichen Potenzmengenkonstruktion einen DEA machen, falls erforderlich.

[flashpixx]

Es gibt ein paar einfache Regeln, um aus einem regulären Ausdruck einen nichtdeterministischen endlichen Automaten zu konstruieren, die finde ich nur grad nicht.

Die Regeln sind im "Thompson-Verfahren" zu finden, über den man beweist, dass zu einem Ausdruck ein nea existiert.

Aus dem NEA kann man dann mit der üblichen Potenzmengenkonstruktion einen DEA machen, falls erforderlich.

Das würde man nicht machen, weil nach der Potenzmengenkonstruktion die Zustände exponentiell wachsen können. Man nimmt die Konstruktion nach dem Satz von Myhill-Nerode

[aline234]

Danke für die Hinweise. Aus einem NEA einen DEA zu machen ist kein Poblem. Nur leider will das Umwandeln regulärer Ausdrücke noch nicht ganz in meinen Kopf

[Limetto]

Weiß nich genau wieso man chronisch alles zu kompliziert machen muss, aber das hier könnte dir doch evtl. helfen? -> http://kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_RegExFSA.pdf