Zitat von Fips1907

Hallo zusammen,

ich benötige etwas hilfe zu folgendem Problem:

a = c* ((a(a|c)*b) | (b(b|c)*a)) (a|b|c)*

Aus diesem regulären Ausdruck möchte ich gerne in einen endlichen Automaten konstruieren, aber irgendwie fehlt mir da der Ansatz.

Habe auch schon versucht mich mit Hilfe von http://www.iti.fh-flensburg.de/lang/compbau/konstruktion.htm ans das Ergebnis ranzutasten (das Applet lässt leider nur max. 20 Zeichen zu), aber habe dann Probleme die "Teil-Automaten" zusammenzuführen.

Hab z.B. schon einen fertigen Automaten zu den Teilen (a(a|c)*b), (b(b|c)*a) und (a|b|c)*..
Nur wie kann ich die sinnvoll zusammenführen?!?

Vielleicht kann mir jemand helfen..

Viele Grüße,
Fips

Alles anzeigen

Du machst vom Startzustand c zwei Pfeile zu den Teilautomaten (a(a|c)*b) und (b(b|c)*a) und vom b des ersten Teilautomatens und vom a des zweiten Teilautomatens machst du noch einen Pfeil zu (a|b|c)*, wobei jeder dieser Zustände ein Endzustand ist.

Zitat von Fips1907

Habe auch schon versucht mich mit Hilfe von http://www.iti.fh-flensburg.de/lang/compbau/konstruktion.htm ans das Ergebnis ranzutasten (das Applet lässt leider nur max. 20 Zeichen zu), aber habe dann Probleme die "Teil-Automaten" zusammenzuführen.

ich kann dir jflap ans herz legen. damit kannst deinen automaten zeichnen und auch testen

Das hätt ich gern als Poster.

Wie wärs mit dem im Anhang? 2 ist Endzustand.

ich hab mir das den automaten von sandybutt angesehen und bin mir zu 99.9% sicher, das er richtig ist und sogar minimal ...

Zitat von Fips1907

aber sicher das man den kompletten ausdruck in so einem "kleinen" automaten abbilden kann?

salopp gesagt: ja ...

so mancher lange und verschachtelte regex ausdruck lässt sich durch ein relativ kleinen automaten repräsentieren