aline234 Geschrieben 16. Januar 2012 Geschrieben 16. Januar 2012 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 Zitieren
flashpixx Geschrieben 16. Januar 2012 Geschrieben 16. Januar 2012 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. Zitieren
Klotzkopp Geschrieben 16. Januar 2012 Geschrieben 16. Januar 2012 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. Zitieren
flashpixx Geschrieben 16. Januar 2012 Geschrieben 16. Januar 2012 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 Zitieren
aline234 Geschrieben 16. Januar 2012 Autor Geschrieben 16. Januar 2012 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 Zitieren
Limetto Geschrieben 17. Januar 2012 Geschrieben 17. Januar 2012 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 Zitieren
Empfohlene Beiträge
Dein Kommentar
Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.