Automatentheorie |
03.10.2006, 13:42 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Bernd1983 | Automatentheorie 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 |
||||||||||||||||||||
|
|||||||||||||||||||||
03.10.2006, 14:21 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
abraxas | 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:
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 |
||||||||||||||||||||
03.10.2006, 14:39 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Bernd1983 | 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, 15:20 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
abraxas | 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:
Der Ausdruck
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 |
||||||||||||||||||||
Anzeige | |||||||||||||||||||||
|
|||||||||||||||||||||
03.10.2006, 16:23 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Bernd1983 | Automaten 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 |
||||||||||||||||||||
04.10.2006, 11:48 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
ed209 | Das Verfahren nennt sich "Potzenmengen-Konstruktion". Hier findet sich zum Beispiel eine Beschreibung: http://www.student.informatik.tu-darmstadt.de/~sf1017/script/fgi_digest.pdf Die Aufgabe verlangt nach einem ganzen Deterministischen Automaten, das heisst du musst vermutlich einen ganzen Automaten angeben und nicht nur drei Zustände. Gruss, Peter |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|