DFA über {0,1} < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:34 Do 04.08.2005 | | Autor: | chris_hs |
Hab ein Problem mit folgender Automatentheorie-Aufgabe.
Hoffe es kann mir einer weiterhelfen.
Es soll ein DFA über {0,1} konstruiert werden der folgende Eigenschaften besitzt:
enhält nicht 101, beginnt nicht mit 01 und endet nicht mit 10.
Ich weiss wie man die einzelnen Automaten durch Pattern Matching hinbekommt, aber wie kann ich die zusammenfügen? Hintereinanderausführung wär nicht sinnvoll, Parallelisierung auch nicht. Ich will auch nicht den DFA für 101 bauen und die andren beiden Bedingungen einbauen. Ein Kreuzproduktautomat müsste wieder minimiert werden. Gibts da nicht ne einfache Möglichkeit wie man die Eigenschaften "beginnt, enhält, endet" miteinander kombinieren kann?
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: www.informatikerboard.de
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:19 Do 04.08.2005 | | Autor: | Bastiane |
Hallo!
> Hab ein Problem mit folgender Automatentheorie-Aufgabe.
> Hoffe es kann mir einer weiterhelfen.
> Es soll ein DFA über {0,1} konstruiert werden der folgende
> Eigenschaften besitzt:
> enhält nicht 101, beginnt nicht mit 01 und endet nicht mit
> 10.
> Ich weiss wie man die einzelnen Automaten durch Pattern
> Matching hinbekommt, aber wie kann ich die zusammenfügen?
> Hintereinanderausführung wär nicht sinnvoll,
> Parallelisierung auch nicht. Ich will auch nicht den DFA
> für 101 bauen und die andren beiden Bedingungen einbauen.
> Ein Kreuzproduktautomat müsste wieder minimiert werden.
> Gibts da nicht ne einfache Möglichkeit wie man die
> Eigenschaften "beginnt, enhält, endet" miteinander
> kombinieren kann?
Was ist denn ein DFA? Ich habe Automatentheorie eigentlich schon gehabt, aber entweder habe ich das einfach vergessen, oder es hieß bei uns anders, oder wir haben es nicht gemacht. Vielleicht kannst du mal sagen, was damit gemeint ist?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:31 Fr 05.08.2005 | | Autor: | Frank05 |
Der Sinn und Zweck der Theorie wie man all diese Automaten zusammenbringt (und NFA->DFA, minimieren,..) ist insbesondere, dass man sich nicht jedesmal neue Loesungsideen einfallen lassen muss.
Bei deiner Aufgabe musst du dir jetzt nur noch ueberlegen, wie man am geschicktesten die Automaten zusammenbaut:
[mm] \neg [/mm] A: enthaelt nicht 101
[mm] \neg [/mm] B: beginnt nicht mit 01
[mm] \neg [/mm] C: endet nicht mit 10
Gesucht ist der Automat, der [mm] \neg [/mm] A [mm] \wedge \neg [/mm] B [mm] \wedge \neg [/mm] C erkennt.
Hier kommt der allseits beliebte DeMorgan ins Spiel, da obiges aequivalent ist zu: [mm] \neg [/mm] (A [mm] \vee [/mm] B [mm] \vee [/mm] C)
Die Negation ist fuer uns vollkommen bedeutungslos, da wir ja einen DFA suchen. (Nebenfrage: Was muss man mit einem DFA machen, um die inverse Sprache zu akzeptieren?) Es muss also nur ein DFA gefunden werden fuer A [mm] \vee [/mm] B [mm] \vee [/mm] C.
An dieser Stelle hast du jetzt zwei Moeglichkeiten:
1. Brute-Force versuchen den DFA zu konstruieren. Das kann am schnellsten sein, aber du riskierst natuerlich auch eine deutlich hoehere Fehlerquote.
2. Oder du gehst nach Schema F vor: Baue die NFAs fuer A, B und C, bilde den Vereinigungsautomaten, wandle ihn um in einen DFA und minimiere diesen. Das entspricht deutlich mehr Aufwand, aber dafuer bekommst du den Korrektheitsbeweis gratis dazu.
Die zweite Moeglichkeit ist "einfach" insofern, als dass du in jedem Schritt genau weisst was zu machen ist. Der Nachteil bei diesen Aufgaben ist natuerlich, dass diese Verfahren viel Zeit in Anspruch nehmen - zumindest wenn man es von Hand machen muss.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:13 Fr 05.08.2005 | | Autor: | chris_hs |
Dann müsste das folgenden Vereinigungsautomat ergeben.
[Dateianhang nicht öffentlich]
Aber das funktioniert ja nicht so richtig!
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:34 Fr 05.08.2005 | | Autor: | Frank05 |
Was sind bei deinem Automaten die Endzustaende? Ich nehme jetzt mal an, dass es die gefuellten Zustaende sind.
Wenn dem so ist, dann hast du wohl die Automaten fuer A,B und C gebaut und deren Zustaende geflippt (Endzustand wird normal und umgekehrt). Danach hast du den Vereinigungsautomaten gebildet. Das gibt aber dann [mm] {\neg A \vee \neg B \vee \neg C} [/mm] und damit nicht das von dir gewollte.
Hast du hingegen zuerst den Vereinigungsautomaten gebildet und dann die Zustaende geflippt, dann solltest du beachten, dass der Vereinigungsautomat ein NFA und kein DFA ist. Ueberleg dir dann noch, warum dieses einfache Zustandsflippen bei einem NFA nicht funktioniert, um die Komplementsprache zu erkennen.
Also zuerst den DFA bauen fuer {A [mm] \vee [/mm] B [mm] \vee [/mm] C} und nicht nur den NFA. Danach kannst du den komplementaeren DFA einfach bekommen.
Davon ganz unabhaengiges Problem: Du hast einmal den Fall, dass du ein Prefix erkennen willst und einmal ein Suffix, aber deine (Teil-)Automaten fuer A und C sind strukturell gleich. Das kann schon aus Prinzip nicht stimmen und du solltest da auch noch einmal ein Auge drauf werfen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:26 Fr 05.08.2005 | | Autor: | chris_hs |
Hui, das wird dann aber zu kompliziert.
Wenn ich den NFA in einen DFA umwandle, muss ich ja die Potenzmenge der Zustände bilden.
Was bei so vielen Zuständen ausartet.
Und wenn ich stattdessen den Durchschnittsautomat der einzelnen Komplemente bauen will (kein DeMorgan),
muss ich den Kreuzproduktautomat konstruieren (ebenfalls viele resultierende Zustände).
Also ist so eine Aufgabe nicht in vertretbarer Zeit zu lösen, außer man probiert.
Aber danke, das hat mir beim allgemeinen Verständnis geholfen.
|
|
|
| |
|
Hi chris_hs!
![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]")
> Hui, das wird dann aber zu kompliziert.
> Wenn ich den NFA in einen DFA umwandle, muss ich ja die
> Potenzmenge der Zustände bilden.
> Was bei so vielen Zuständen ausartet.
Damit hast Du natürlich Recht, allerdings ist es doch eher ein Worst-Case-Fall, das bei der Potenzmengenkonstruktion aus einem NEA mit $n$ Zuständen ein DEA mit [mm] $2^n$ [/mm] Zuständen wird. Das mußt Du bei der Potenzmengenkonstruktion ausnutzen, indem Du nur die Zustände verschmilzt, die vom Startzustand (oder von mehreren Startzuständen) erreichbar sind und dabei außerdem noch darauf achtest, daß Du keine sinnlosen Zustandsteilmengen vom neuen DEA betrachtest (also Teilmengen, aus Zuständen, die niemals "zugleich" erreicht werden können, hmm, ich weiß nicht, wie ich's besser erklären soll ![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]") , aber vielleicht weißt Du ja auch so, was ich meine.  ).
Ich würde dir außerdem bei deiner Aufgabe den Tip geben, den Nichtdeterminismus (also die Entscheidungsfreiheit eines NEA wirklich voll auszunutzen, um drei Automaten mit sowenig Zuständen wie möglich zu bauen (Versuch das Problem wirklich umgangssprachlich zu beschreiben; z.B. "Ok, zuerst alles Mögliche einlesen ... hmm ... irgendwann (Nichtdeterminismus) kommt 101 *grübel* und dann ist's egal, was kommt. Also lese ich wieder alle Zeichen aus dem Alphabet ein). Dann kannst Du mit Frank05s Hinweisen weitermachen.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:20 Sa 06.08.2005 | | Autor: | Frank05 |
> Hui, das wird dann aber zu kompliziert.
> Wenn ich den NFA in einen DFA umwandle, muss ich ja die
> Potenzmenge der Zustände bilden.
> Was bei so vielen Zuständen ausartet.
Das kommt darauf an, ob du die Konstruktion exakt nach dem vorgegebenen Algorithmus machst, oder ob du ein wenig mehr Gehirnschmalz hineinsteckst. Da der Algo prinzipiell ja das simultane Durchlaufen der Zustaende simuliert kannst du eben dieses auch selbst machen. Du beginnst in einem Zustand der alle Startzustaende enthaelt (in deinem Fall waere das ein Zustand, der die 3 Anfangszustaende der Teilautomaten representiert). Von einem solchen Zustand aus kannst du nur 2 Kanten fuer 0 oder 1 haben. Jetzt musst du eben von allen verschmolzenen Zustaenden im NFA aus nachsehen, wo du bei einer 0 bzw. 1 landest. Diese Zustaende werden wieder in einen neuen Zustand fuer den DFA verschmolzen.
Auf diese Art spart man sich sehr sehr viele der [mm] 2^n [/mm] moeglichen Zustaende und es laesst sich noch relativ effizent von Hand durchfuehren.
Zu kompliziert sollte das nicht sein. Probiers einfach mal an kleinen Automaten aus. Dann kannst du den DFA einmal ueber die gesamte Potenzmenge konstruieren und danach mit dem schnelleren Verfahren vergleichen. Wenn du das Prinzip mal verstanden und ein, zwei Beispiele durchgerechnet hast, dann bekommt du das schon in den Griff :)
> Also ist so eine Aufgabe nicht in vertretbarer Zeit zu
> lösen, außer man probiert.
Wobei je nach Aufgabenstellung 'probieren' nicht ausreichend ist. Hast du den Automat 'erraten' wird es ungleich schwieriger zu beweisen, dass der Automat auch wirklich das erwartete Verhalten zeigt.
Aber du hast schon Recht, was den Zeitaufwand fuer eine manuelle Loesung anbelangt. In einer Klausur duerfte sich so eine Aufgabe eher nicht finden lassen. 'Schnellere' Varianten waeren dann eben Einschraenkung auf weniger Teilautomaten (nur Bedingungen A, B und Aufteilen in Teilaufgaben z.B.) oder es genuegt einen NFA zu konstruieren (was es aber fast schon wieder zu einfach macht).
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:39 Mo 08.08.2005 | | Autor: | chris_hs |
Habs mit dem NFA in DFA Algorithmus (vom Startzustand die Folgezustände verschmelzen und deren Folgezustände betrachten)
recht schnell hingekriegt,
indem ich mir gesagt hab, die Endzustände von A und B werden nach dem Komplement ohnehin Fehlerzustände
(beim EZ von C allerdings nicht),
Taucht also beim Algorithmus einer dieser 2 Zustände in einem neuen Zustand auf, brauch ich den nicht weiterbetrachten.
Ohne diesen Trick dauert der Algorithmus trotzdem viel zu lange und ergibt zuviele neue Zustände.
Vielen Dank für die Hilfe!
|
|
|
|
