Deterministischer endlicher Automat aus regulärem Ausdruck?
Guten Abend,
ich bin bei meiner Klausurvorbereitung auf folgende Aufgabe gestoßen:
Gegeben ist die Sprache 𝐿, die durch den regulären Ausdruck 𝑝(𝑖|𝑎) (𝑝(𝑖|𝑎))∗𝑝𝑜 erzeugt wird.
Geben Sie den Übergangsgraphen eines deterministischen endlichen Automaten (DEA) an, der die Sprache 𝐿 akzeptiert.
Dafür habe ich folgendes entworfen.
Meine Frage ist nun, was ich an den roten Fragezeichen hinschreiben kann. Es kann kein p sein, da es kein DEA mehr wäre. Wie würdet ihr es lösen?
Danke
3 Antworten
Sollte das Sternzeichen oben sein, warscheinlich oder? Also das man bei Bedarf (p(i|a)) beliebig wiederholen kann?
Mit Automaten tue ich mich immer etwas schwer. Ich würde das so probieren: von S nach A mit p dann weiter von A nach B und das so lassen wie du das hast und dann von B eine Transition zurück nach S ohne Terminal Zeichen. Damit könntest du so (𝑝(𝑖|𝑎))∗ beliebig reproduzieren oder auch nicht, weils komplett geklammert ist. Und dann von B mit p nach C und dann mit o in den Entzustand.
Ohne Garantie, aber könnte eigentlich passen aber probiere es vorher aus, eventuell sonst man oder sonst mal (𝑝(𝑖|𝑎))∗ ausklammern und gucken ob das hinkommt. Dazu gibt's ja bestimmt Tools. Oder vielleicht weiß das ja jemand anders noch besser.
Meine regulären ausdrücke sind zu eingerostet.
Du musst auf jeden Fall mit einem O raus. Wenn du in einem Status nach dem P bist.
Ist das zweite P I oder A wirklich optional?
In deinem Beispiel. Kannste vom Status C aus mit einem O nach E gehen. Welches auch gleich dein endstatus ist.
Dann würde der Automat: bei jedem Ausdruck wahr anzeigen der mindestens ein Pi oder Pa hat und mit einem Po endet.
Die Übergänge BE und DE sind falsch. E und F brauchst Du nicht.
Von C geht es mit „o“ direkt nach G. Das sieht man leichter, wenn man den Ausdruck zu „𝑝(𝑖|𝑎) p ((𝑖|𝑎)𝑝)∗ 𝑜“ umformt.