Konstruktion eines Epsilon Automaten & NFA

[b1zarRe]

Hi,

wir haben folgende Grundformen gelernt: http://www7.pic-upload.de/21.08.11/iy3jf7evdcze.jpg

und ich habe zu folgendem Regulären Ausdruck versucht ein Epsilon Automaten aufzustellen... Es soll dabei immer so vorgegangen werden, dass man diese "Grundformen" verbindet....leider bin ich oftmals dort sehr unsicher... was haltet ihr davon? http://www7.pic-upload.de/21.08.11/r4ev23v7ud8.jpg

Und wie geht ihr vor, beim Streichen von Epsilon Übergängen? Bei mir geschieht das noch relativ nach gesundem Menschenverstand, indem ich schaue, was aus dem Folgezustand eines Epsilon Überganges gemacht werden kann...

 

[Marcinek]

1. Das Vorgehen nennt sich Thompson Konstruktion von NFAs aus Regulären Ausdrücken.

Ich denke da kann man viele Infos zu googlen oder nachschlagen ;D

http://tcs.rwth-aachen.de/lehre/FSAP/SS2009/handout-2009-05-05.pdf

NFA => DFA

So habe ich es damals gemacht:

NFA -> DFA

Dies ist ein Verfahren, dass auch in Klausuren vorausgesetzt wird.

----

Zu deinem Automaten. Ich glaube er ist nicht korrekt nach Thompson hergestellt.

ab müsste so aussehen

S --- e ---> q1 --- a ---> q2 --- e ---> q3 --- b ---> q4 --- e ---> q5 Und dann weiter. Hier fehlt bei dir der letzte Epsilon.

 

[b1zarRe]

Hi,

Zu den folien: so aehnlich hatten wir das auch gelernt aber der begriff thompsonbverfahren ist leider nie gefallen, danke.

Zu meinem automaten: sprich nach b kommen noch 2 epsilon uebergaenge bevor das a+b kommt?
Und einre fragr zum nulloperator(also die durchgesttichrichene 0).. wie wuerde man einen automatrn konstruieren wenn da stuende: a + nulloperator ?