| Autor |
Beitrag |
    
Snowdragon
| | Veröffentlicht am Mittwoch, den 21. März, 2001 - 09:03: | 
|
Suche dringend Hilfe !
Entwerfen Sie ein Zustandsdiagramm für einen endlichen Automaten ohne Ausgabe mit E={0,1}, der ein Eingabewort e genau dann akzeptiert, wenn es mit 101 oder mit 010 endet.
=> Wie kommt man da hin ?
!! Danke für die Hilfe !! |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Mittwoch, den 21. März, 2001 - 16:56: |
|
Hi Snowdragon
Wenn man bei solchen Aufgaben, bei denen die Bedingung ans Ende des Wortes gestellt ist, gar nicht mehr weiterkommt, bietet es sich an, einen nichtdeterministschen Automaten zu bauen, und ihn dann in einen deterministischen zu transformieren. Ist zwar eine Menge Arbeit, jedoch führt sie immer zum Ziel. Da ihr das wahrscheinlich noch nicht gehabt habt, machen wir es direkt mit einem deterministischen:
Erstmal ganz naiv einen (unvollständigen) Automaten, der die beiden Endungen akzeptiert:
Nun fügen wir die fehlenden Übergänge ein:
Zunächt bei q1,q2,q3,q4: Wenn von dort ein noch nicht eingezeichneter Pfeil ausgehen soll, so wird die abwechselnde Folge von Nullen und Einsen unterbrochen, also müsste man die Folge neu anfangen. Die erste Ziffer dafür hat man schon, daher geht man dann in q1 oder q3:
Als letztes müssen wir uns um q5 und q6 kümmern. Kommt in q5 eine 1, so haben wir wieder die Situation, dass eine abwechselnde Folge unterbrochen wird; bei einer 0 sind die letzten Ziffern 010, also gehen wir in q6. Von q6 aus so ähnlich:
Übrigens: Ich habe den Automat erst mit nur einem Endzustand probiert (q5 und q6 zusammengefasst), aber das funktioniert nicht. Versuch doch mal die Konstruktion von da an weiterzumachen, um zu sehen, was dann schief geht.
viele Grüße
SpockGeiger |
Snowdragon
| | Veröffentlicht am Mittwoch, den 21. März, 2001 - 18:54: |
|
Danke SpockGeiger ! |
|
