DFA zeichnen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:04 Sa 21.11.2009 | | Autor: | tinakru |
| Aufgabe | | Zeichnen sie einen deterministischen endlichen Automaten, der das Teilwort 0010 g e n a u einmal enthält. Das Alphabeth sei dabei S = {0,1} |
Ich hab jetzt schon zwei Stunden rumprobiert wie ich das hinkriegen könnte. Ich schaffs aber immer nur einen DFA zu zeichnen, der das Wort 0010 mindestens einmal enthält. Aber mit genau einmal hab ich keinen Plan wie ich das machen sollte.
|
|
| |
|
Hallo tinakru,
> Zeichnen sie einen deterministischen endlichen Automaten,
> der das Teilwort 0010 g e n a u einmal enthält. Das
> Alphabeth sei dabei S = {0,1}
Ich denke, folgende Vorgehensweise dürfte zum Ziel führen:
Erstelle einen DEA, der nur Wörter mit (0010(0|1)|0010) am Ende akzeptiert.
Betrachte anschließend folgende Wortbausteine:
00
01
10
000
001
010
011
100
110
11 (x)
101 (x)
111 (x)
Ich denke, daß durch das beliebige Aneinanderreihen dieser Bausteine(, wobei auch Bausteine wiederholt werden dürfen) folgendes gilt: 0010(1|0)* = (0010(0|1)|0010)(<Bausteine durch '|' getrennt>)* . Allerdings ist das noch nicht das, was wir wollen. Denn nach 0010 darf kein 0010 mehr folgen. Du mußt also nur Aneinanderreihungen dieser Bausteine erlauben, die kein 0010 beinhalten. Betrachte erstmal die x-Bausteine, diese Bausteine sind sowas wie "Reset-Schalter" oder "Trenner", weil nach dem Einfügen eines solchen Bausteins der komplette Ausdruck 0010 neu aufgebaut werden muß. Aus den übrigen 9 Bausteinen läßt sich dann auch 0010 zusammenbauen. Du kannst dir ja mal vom Computer z.B. [mm]9^5 = 59049[/mm] Möglichkeiten aus diesen Bausteinen erzeugen lassen, z.B. 00 00 10 01 011, u.s.w. . [mm]9^6[/mm] ist wohl leider bereits zu hoch aber vielleicht sieht man auch so schon bestimmte Baumuster, aus denen 0010 entsteht. Z.B. ist die Aneinanderreihung 00,10,01,011 ein Problem. Ich würde mir vom PC alle Muster rausfiltern lassen, wo 0010 nicht vorkommt und mir daraus ((0010(0|1)|0010)(<zulässige Bildungsmuster durch '|' getrennt> | Trenner)*) basteln.
Danach mußt du noch den ersten Automaten ebenfalls in einen regulären Ausruck umwandeln und dir überlegen, wie man diese Ausdrücke sinnvoll zusammensetzen kann. Danach mußt du den so entstandenen Ausdruck in einen NEA umwandeln und daraus in einen DEA. Diesen DEA wirst du wohl noch minimieren müssen.
Viele Grüße
Karl
P.S. Aber überleg' dir erstmal, ob überhaupt 0010(1|0)* = (0010(0|1)|0010)(<Bausteine durch '|' getrennt>)* gilt. Da bin ich mir selber noch nicht sicher. Sonst machst du dir die ganze Arbeit umsonst.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:18 Sa 21.11.2009 | | Autor: | Karl_Pech |
Allerdings habe ich gerade festgestellt, daß die Bausteine auch in Wechselwirkung mit dem vorhergehenden Ausdruck (0010(0|1)|0010) treten können. Z.B. besteht 0010010 aus:
0010 010 und enthält zwei ineinandergeschachtelte 0010.
Ich glaube mein Ansatz ist wohl doch zu umständlich. Vielleicht geht es ja doch irgendwie einfacher... . Im Internet gibt es jedoch viele Tools, die EAs automatisch minimieren können und reguläre Ausdrücke in DEAs umwandeln können. Das dürfte dir die Arbeit etwas erleichtern, wenn du meinen Ansatz wählen solltest.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:43 Sa 21.11.2009 | | Autor: | felixf |
Hallo!
> Zeichnen sie einen deterministischen endlichen Automaten,
> der das Teilwort 0010 g e n a u einmal enthält. Das
> Alphabeth sei dabei $S = [mm] \{0,1\}$
[/mm]
>
> Ich hab jetzt schon zwei Stunden rumprobiert wie ich das
> hinkriegen könnte. Ich schaffs aber immer nur einen DFA zu
> zeichnen, der das Wort 0010 mindestens einmal enthält.
> Aber mit genau einmal hab ich keinen Plan wie ich das
> machen sollte.
Ich vermute mal dein Automat sieht so aus:
er hat ein paar Zustaende, die nach $0 0 1 0$ suchen, und sobald dies vorkommt geht er in einen neuen Zustand, der einfach nur noch alles an Eingaben nimmt und der gleichzeitig Endzustand ist.
Jetzt ersetz doch den Endzustand praktisch wieder durch eine Kopie des ersten Teiles, die nach $0 0 1 0$ sucht: nur mit dem Unterschied dass man bei einem Treffer in eine Schleife gelangt, die niemals zu einem Endzustand fuehrt, und dass alle anderen Zustande in der zweiten Kopie (also da wo er noch nach dem zweiten $0 0 1 0$ sucht) Enzustaende sind.
Das einzige wodrauf du aufpassen musst, ist dass dein Automat auch $0010010$ erkennt als doppeltes Vorkommen und nicht nur $0010(irgendwas)0010$.
LG Felix
|
|
|
|
