 Automatentheorie |
Bernd1983
Grünschnabel
Dabei seit: 03.10.2006
Beiträge: 3
 |
|
Hi, ich habe einige Probleme bei Beispielen zu Automatentheorie
Das Bsp hab ich als doc angehängt.
Meine Fragen: Bei den regulären Ausdrücken wie komme ich da zu 000 oder 000(10)*10? Gibt es da ein Lösungsschemata dazu?
Ich kann leider mit diesen bspen nichts anfangen, vielleicht kann mir jemand helfen
| Dateianhang: |
 Automat.zip (7 KB, 779 mal heruntergeladen)
|
|
|
03.10.2006 13:42 |
|
|
abraxas 
Grünschnabel
Dabei seit: 14.09.2006
Beiträge: 9
Herkunft: D
|
|
Hmm... ich verstehe die Frage zwar nicht ganz...
Also, der reguläre Ausdruck heisst ja eigentlich nur: drei Nullen, so oft 1 und 0, wie Du willst (aber mindestens einmal).
Das ist allerdings eine unnötige Variante. Besser wäre:
Beide Ausdrücke sind äquivalent, nur ist der letztere halt kürzer (und verständlicher).
Wenn ich Dich richtig verstanden habe, ist Deine Frage, wie man von einem Automaten zu einem regulären Ausdruck kommt. Nun, das kann schwierig sein, aber ich geb Dir mal den regulären Ausdruck, der den ersten der abgebildeten Automaten beschreibt:
Der Automat oben und dieser Ausdruck würden die selben Wörter durchlassen.
Und ein Lösungsschema (Schemata ist der Plural von Schema) gibt es eigentlich nicht. Das liegt an der bloßen Mächtigkeit der Automatentheorie, die Automaten so ungeheurer Komplexität (Teilgrammatiken für reelle Sprachen lassen sich damit implementieren) erzeugen kann, dass es wirklich schwierig sein würde ein allgemeines Konzept anzugeben.
Der vorliegende Automat (ich red immernoch vom ersten) ist allerdings ein augenscheinlich sehr einfacher. Dazu musst Du Dir einfach mal klarmachen, was die Operatoren in regulären Ausdrücken bedeuten und wie man das einem Automaten klarmacht.
Der Operator * sagt: wiederhole den vorangegangenen Cluster null bis unendlich mal. Wenn ich also schreibe: dann heisst dass: beliebig viele Nullen. Und wenn in einem Automaten ein Pfeil von einem Zustand wieder auf den selben Zustand zeigt (das ist der erste in Deinem Beispiel), dann heisst das: wiederhole das auf dem Pfeil so oft wie's halt da ist! (der Operator + heisst im Übrigen: das muss mindestens einmal aber ansonten beliebig oft vorkommen).
Du gehst also einfach an den Pfeilen entlang einen Weg und schaust, wohin Du gehen kannst. Wenn Du einem Pfeil folgst, der wieder zum Ausgangspunkt hinführt, dann kannst Du einen der Wiederholungsoperatoren verwenden. Ansonsten musst Du darauf aufpassen, dass die Zeichenkette in Deinem reg. Ausdruck genau dem Automaten entspricht.
Du kannst ja mal zur Übung einen Ausdruck für den zweiten Automaten geben (also einen, der ihn vollständig beschreibt.)
(Übrigens hab ich auf Deinen Bildern die finalen Zustände nicht erkennen können... die musst Du natürlich unbedingt berücksichtigen. Nur ein Wort, das auf einem finalen Zustand endet ist auch gültig!)
Grüße, abraxas
PS: falls das verwirrend oder nicht erschöpfend war, dann frag einfach noch mal 
__________________
Never trust an operating system you don't have sources for.
-- Unknown source
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von abraxas: 03.10.2006 14:23.
|
|
|
03.10.2006 14:21 |
|
|
Bernd1983
Grünschnabel
Dabei seit: 03.10.2006
Beiträge: 3
|
|
Halllo, danke für die Antwort. Leider ist es mir immer noch nicht ganz klar.
zu meinem ersten Graphen. Die Finalzustände - die du nicht siehst sind c und d. Nun ist die Musterlösung als reguläre Ausdrücke 00 oder 000 oder 000(10)*10
Warum 000? Verstehe ich nicht. Ich kann ja gar nicht dreimal hintereinander eine 0 begehen, damit ich zu einem Finalzustand komme
00 verstehe ich, weil man so von a nach d kommt
zu 000(10)*10. ist mir komplett unklar. die ersten drei Nullen? Wo führen die hin? Die Klammer ? wofür? dieser Ausdruck ist mir ganz komplex.
Vielleicht kannst du mirs nochmals erklären
|
|
|
03.10.2006 14:39 |
|
|
abraxas
Grünschnabel
Dabei seit: 14.09.2006
Beiträge: 9
Herkunft: D
|
|
Nun, wenn c ein finaler Zustand ist, dann ist auch der Ausdruck 000000000 (und so viele Nullen Du haben magst) gültig. Das liegt daran, dass [i]c[/c] auf sich selbst zeigt (und dafür eine Null haben mag.)
Wenn Du also 000 hast dann ist Deine Kette folgende:
| code: |
1:
|
a->b; b->c; c->c |
|
Der Ausdruck macht folgendes:
| code: |
1:
|
a->a; a->b; b->d; d->b; b->(d|c); |
|
wenn Du den letzten Schritt auf 'd' endest, dann kannst Du so oft Du willst wieder zu b zurück und nochmal eine 1 und 0 hinterherschieben. Das heisst, die letzten beiden Statements sind wiederholbar, solange auf d und nicht auf c geendet wird.
Ich hoffe, dass es Dir jetzt etwas klarer ist...
Grüße, abraxas
__________________
Never trust an operating system you don't have sources for.
-- Unknown source
|
|
|
03.10.2006 15:20 |
|
|
Bernd1983
Grünschnabel
Dabei seit: 03.10.2006
Beiträge: 3
|
|
Ok danke. Das dürft ich nun verstanden haben.
Jetzt hab ich ein weiteres Problem. Bei der Aufgabenstellung steht noch dabei:
Bestimmen Sie dazu einen vollständigen deterministischen Automaten, der dieselbe Sprache erkennt. bei dem besprochenen Verfahren für dieses Problem ergibt sich ein deterministischer Automat, in dem allle Zustände erreichbar sind und mit Teilmengen bezeichnet werden. Dabei kommen vor:
Lösung: {a} und {a,b} und {c}
Wie komm ich nun auf das?
Danke nochmals für die bisherigen verständliche Antworten
|
|
|
03.10.2006 16:23 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
|
|
04.10.2006 11:48 |
|
|
|
