Sprache auf DEA abbilden? < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:10 Sa 29.06.2013 | | Autor: | bandchef |
| Aufgabe | Konstruieren Sie für die folgende Sprache über [mm] $\Sigma [/mm] = [mm] \{0,1\}$ [/mm] jeweils einen DEA.
[mm] $L_2=\{w | \text{001 ist in w enthalten und w beginnt mit 0 und endet mit 1}\}$ [/mm] |
Hi Leute!
Ich hab mir nun gedacht, einen DEA für die Sprache über drei Teil-DEAs zu konstruieren. Ich hab ein Bild hochgeladen das die drei Teil-DEAs illustriert. Könnt ihr mir sagen, ob man das so machen kann und ob die Teil-DEAs richtig sind? Link zum Bild: http://s14.directupload.net/file/d/3301/hfo5enrv_jpg.htm
Wenn sie richtig sind, muss ich die drei DEAs wohl über die Produkautomaten-Konstruktion zu einem DEA der L2 repräsentiert, zusammenbauen. Muss ich hierfür dann die Vereinigungsmenge aus dem ersten und zweiten Teil-DEA bilden und diesen neu entstandenen DEA dann noch mit dem dritten Teil-DEA vereinigen, damit ich den DEA für L2 bekomme?
Kann mir jemand meine Fragen beantworten?
Edit: Im Bild fehlt leider die Beschriftung einer Transition. Im Automaten für "w beginnt mit 0" muss an die Transition von q0 zu q1 natürlich eine 0 hin!
|
|
| |
|
Hallo bandchef,
warum machst Du es Dir hier so kompliziert? Du weißt, wie der DEA aussieht, der "001 ist in w enthalten" erkennt. Jetzt musst Du doch nur noch an diesen "davor" ein "beginnt mit 0" einbauen und am Ende ein "endet mit 1". That's it.
Gruß
Anna
|
|
|
| |
|
Hi!
Ich hab hier nun deinen Rat befolgt und die Aufgabe nochmal von vorne begonnen. Hier dazu nochmal ein Bild, dann kann ich besser erklären, was ich gemacht habe: http://s1.directupload.net/file/d/3303/qyg7yfif_jpg.htm
Ich hab nun zu dem Teil "w enthält 001$ versucht über einen NEA und der PMK den DEA dafür zu konstruieren/berechnen. Den DEA siehst du auf dem Bild ganz oben und den daraus berechneten DEA in der Mitte. Das Problem an diesem DEA ist nun, dass der letzte Zustand des DEAs eine 1-Transition auf den ersten Zustand und eine 0-Transition auf den zweiten Zustand hat!
Wenn ich nun den Teil "w beginnt mit 0" an den berechneten DEA anhänge ist das noch kein Problem, das funktioniert auch sehr gut.
Aber wenn ich den Teil "w endet mit 1" an den DEA anhängen will, dann bekomm ich von q4 aus (im vorherigen berechneten DEA war das akzeptierende Zustand!) eine 1-Transitionen! Da wäre das ja wieder ein NEA! Und vor allem: Hat der neue DEA dann zwei akzeptierende Zustände, nämlich q4 (der akzeptierende Zustand vom alten, berechneten DEA und einen neuen akzeptierenden Zustand q5 (wegen "w endet mit 1")?
Irgendwie leuchtet mir das ganze noch nicht so ein... Vor allem die Sache mit den zwei akzeptierenden Zustände und der zwei 1-Transitionen. Ich könnte mir denken, dass der akzeptierende Zustand an q4 einfach kein akzeptierender Zustand mehr ist, da der fertige DEA ja einfach nur auf "1 enden" soll. Dann hab ich aber immer noch das Problem mit den zwei 1-Transitionen von q4 aus!
Ich hoffe, du kannst mir helfen 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:20 Mi 03.07.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
