 Aus einem NFA einen regulären Ausdruck erzeugen |
HB
unregistriert
 |
|
| 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 11:44 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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 12:55 |
|
|
HueHang
unregistriert
|
|
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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von HueHang: 09.07.2012 21:42.
|
|
|
09.07.2012 21:42 |
|
|
|
