Aus einem NFA einen regulären Ausdruck erzeugen |
| 09.07.2012, 11:44 | Auf diesen Beitrag antworten » |
| HB | Aus einem NFA einen regulären Ausdruck erzeugen Meine Frage: Hallo, ich versuche aus einem gegeben NFA einen regulären Ausdruck zu erzeugen. Die Vorgehensweise ist folgendermassen. Man erzeugt aus jedem einzelnen Zustand einen Ausdruck und fügt diese dann am Ende zusammen. Einigermassen kann ich das auch schon. Jedoch versuche ich mir ein Schema abzuleiten, z.B. mit welchen Zustand man anfängt. Vielleicht kann mir jemand erläutern was für Kriterien erfüllt sein sollten mit Zustand x anzufangen? Danke Meine Ideen: Meine Idee, wäre es einen Zustand zu wählen, der viele ankommen Übergänge besitzt. |
|
|
|
| 09.07.2012, 12:55 | Auf diesen Beitrag antworten » |
| Karlito | Wenn ich das recht in Erinnerung habe, macht man das einfach vom Anfangszustand abhängig. und dann fängt man an die entsprechenden Gleichungen aufzustellen. Stichwort Lemma von Arden... VG, Karlito |
| 09.07.2012, 21:42 | Auf diesen Beitrag antworten » |
| HueHang | Man kann auch den NFA zu einem verallgemeinerten (generalised) GNFA umbauen und dann mithilfe von Eliminationen der Zustände einen regulären Ausdruck bekommen. Mehr Informationen hier: http://www.cs.uiuc.edu/class/sp09/cs373/lectures/lect_08.pdf |
|
|
