Übergangstabelle für NEA < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 14:45 Fr 03.05.2013 | | Autor: | bandchef |
| Aufgabe | Welche Sprache akzeptiert der folgende NEA [mm] $M=(Q,\Sigma, \delta, q_0, [/mm] F)$ mit [mm] $Q=(q_0, q_1, q_2)$, $\Sigma [/mm] = [mm] \{0,1\}$, [/mm] $ [mm] F=\{q_2\}$ [/mm] mit folgender [mm] $\delta$-Funktion:
[/mm]
[mm] \begin{tabular}{c c c c}
\delta & q_0 & q_1 & q_2 \\
0 & \{q_0, q_2\} & \{q_0\} & \{\} \\
1 & \{q_0, q_1\} & \{\} & \{\} \\
\end{tabular}
[/mm]
Zeigen Sie anhand des NEA M, dass der Minimierungsalgorithmus nicht direkt für NEA angewendet werden kann. Konstruieren zu dem NEA einen minimierten DEA. |
Hi Leute!
Die Aufgabe ist mir soweit klar. Auch der Minimierungsalgorithmus der angewendet werden soll hab ich verstanden und kann ich soweit auch fehlerfrei anwenden. Die einzige Schwierigkeit an dieser Aufgabe ist nun nur: Ich kann aus der Übergangstabelle keinen NEA konstruieren! Ich weiß nicht wie das geht...
Laut Tabelle komme ich ja vom Startzustand [mm] q_0 [/mm] mit einer 0 in die Zustsandsmenge [mm] $\{q_0, q_2\}$; [/mm] genau das ist aber das Problem? Wie gehe ich mit dieser Zustandsmenge um???
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:31 Fr 03.05.2013 | | Autor: | bandchef |
Naja, da hab ich wohl nun den Wald vor lautern Bäumen nicht gesehen. Ich hab jetzt den NEA konstruiert und aus dem NEA mit der PMK einen DEA gebaut. Hier das Bild dazu: http://s7.directupload.net/file/d/3244/uwdrek75_png.htm
Stimmt der DEA so?
Nun muss ich wohl den Minimierungsalgorithmus auf den DEA anwenden um den letzten Satz der Aufgabe erfüllen zu können.
Das einzige was mir nun Kopfschmerzen bereitet, ist die Aufgabe bei der ich zeigen soll, dass der Minimierungsalgorithmus nicht auf NEAs angewendet werden kann. Wie soll ich das machen? Einfach den Algorithmus auf den NEA anwenden und man sieht dann irgendwann, dass das einfach nicht geht?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:29 Sa 04.05.2013 | | Autor: | tobit09 |
Hallo bandchef,
> Naja, da hab ich wohl nun den Wald vor lautern Bäumen
> nicht gesehen. Ich hab jetzt den NEA konstruiert und aus
> dem NEA mit der PMK einen DEA gebaut. Hier das Bild dazu:
> http://s7.directupload.net/file/d/3244/uwdrek75_png.htm
Der NEA stimmt abgesehen davon, dass du fälschlicherweise einen Zustand [mm] $\emptyset$ [/mm] vorgesehen hast. [mm] $\delta((q,a))=\emptyset$ [/mm] bedeutet, dass keine Übergänge von $q$ mit Verarbeitung von $a$ ausgehen. Wenn von $q$ aus mit Verarbeitung von $a$ ein Übergang zu einem Zustand [mm] $\emptyset$ [/mm] vorgesehen wäre, so müsste es [mm] $\delta((q,a))=\{\emptyset\}$ [/mm] heißen.
> Stimmt der DEA so?
Abgesehen von einem 0-Übergang zu viel oben von [mm] $\{q_0,q_2\}$ [/mm] zu sich selbst: Folgerichtig.
> Nun muss ich wohl den Minimierungsalgorithmus auf den DEA
> anwenden um den letzten Satz der Aufgabe erfüllen zu
> können.
>
> Das einzige was mir nun Kopfschmerzen bereitet, ist die
> Aufgabe bei der ich zeigen soll, dass der
> Minimierungsalgorithmus nicht auf NEAs angewendet werden
> kann. Wie soll ich das machen? Einfach den Algorithmus auf
> den NEA anwenden und man sieht dann irgendwann, dass das
> einfach nicht geht?
Wende einfach euren Minimierungsalgorithmus auf beide Automaten an und schaue, was passiert!
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:35 Sa 04.05.2013 | | Autor: | bandchef |
Der NEA stimmt abgesehen davon, dass du fälschlicherweise einen Zustand [mm] $\emptyset$ [/mm] vorgesehen hast. [mm] $\delta((q,a))=\emptyset$ [/mm] bedeutet, dass keine Übergänge von $q$ mit Verarbeitung von $a$ ausgehen. Wenn von $q$ aus mit Verarbeitung von $a$ ein Übergang zu einem Zustand [mm] $\emptyset$ [/mm] vorgesehen wäre, so müsste es [mm] $\delta((q,a))=\{\emptyset\}$ [/mm] heißen.
Ist dann der NEA richtig, oder nicht? Ehrlich gesagt verstehe ich nicht, was ich da jetzt falsch gemacht habe. In der Übergangstabelle komm ich mit einer 0 von [mm] q_2 [/mm] aus zur leeren Menge...; quasi ein toter Zustand. Von dem geht's nie wieder weg... Muss ich dafür dann nicht auch einen solchen Zustand einführen?
Ich hab dann mal die überflüssige Schleife im DEA weggemacht. Ich denke, die ist nur zusätzlich irgendwie drangekommen und das nachträgliche wegmachen macht keine Auswirkung auf den DEA. Hier nochmal ein neues Bild mit dem Minimierungsalgo. auf den DEA angewendet soweit der minimierte DEA.
Bild: http://s7.directupload.net/file/d/3245/vsj3suxj_png.htm
Stimmt das nun so?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:02 Sa 04.05.2013 | | Autor: | tobit09 |
> Der NEA stimmt abgesehen davon, dass du fälschlicherweise
> einen Zustand [mm]\emptyset[/mm] vorgesehen hast.
> [mm]\delta((q,a))=\emptyset[/mm] bedeutet, dass keine Übergänge
> von [mm]q[/mm] mit Verarbeitung von [mm]a[/mm] ausgehen. Wenn von [mm]q[/mm] aus mit
> Verarbeitung von [mm]a[/mm] ein Übergang zu einem Zustand [mm]\emptyset[/mm]
> vorgesehen wäre, so müsste es [mm]\delta((q,a))=\{\emptyset\}[/mm]
> heißen.
>
> Ist dann der NEA richtig, oder nicht?
Nein, er gibt die Tabelle nicht ganz korrekt wieder.
> Ehrlich gesagt
> verstehe ich nicht, was ich da jetzt falsch gemacht habe.
> In der Übergangstabelle komm ich mit einer 0 von [mm]q_2[/mm] aus
> zur leeren Menge...;
Nein, du kommst mit einer 0 von [mm] $q_2$ [/mm] aus nirgendwohin, auch nicht zu einem Zustand, der die leere Menge ist.
In der Tabelle stehen zwischen den Mengenklammern jeweils die Zustände, zu denen du hinkommst. Und zwischen den Mengenklammern an der zu [mm] $q_2$ [/mm] und $0$ gehörigen stelle stehen zwischen den Mengenklammern eben keine Zustände, auch nicht ein Zustand [mm] $\emptyset$.
[/mm]
> quasi ein toter Zustand. Von dem
> geht's nie wieder weg... Muss ich dafür dann nicht auch
> einen solchen Zustand einführen?
Im Übrigen ist die Zustandsmenge [mm] $Q=\{q_0,q_1,q_2\}$ [/mm] vorgegeben. Da taucht nirgendwo ein Zustand [mm] $\emptyset$ [/mm] auf.
> Ich hab dann mal die überflüssige Schleife im DEA
> weggemacht. Ich denke, die ist nur zusätzlich irgendwie
> drangekommen und das nachträgliche wegmachen macht keine
> Auswirkung auf den DEA. Hier nochmal ein neues Bild mit dem
> Minimierungsalgo. auf den DEA angewendet soweit der
> minimierte DEA.
>
> Bild:
> http://s7.directupload.net/file/d/3245/vsj3suxj_png.htm
>
> Stimmt das nun so?
Ja, alles folgerichtig.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:20 Sa 04.05.2013 | | Autor: | bandchef |
So, jetzt weiß ich was ich falsch gemacht habe. Wenn da das leere Menge Zeichen steht, dann passiert einfach nix. Hier nun die neue Lösung: http://s1.directupload.net/file/d/3245/yi9epopw_jpg.htm
Passts jetzt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:32 Sa 04.05.2013 | | Autor: | tobit09 |
> So, jetzt weiß ich was ich falsch gemacht habe. Wenn da
> das leere Menge Zeichen steht, dann passiert einfach nix.
> Hier nun die neue Lösung:
> http://s1.directupload.net/file/d/3245/yi9epopw_jpg.htm
>
> Passts jetzt?
NEA: ![[ok]](/images/smileys/ok.gif "[ok]")
DEA: Stimmt bis auf den mit $0$ beschrifteten Pfeil, der vom Zustand [mm] $\{q_0,q_2\}$ [/mm] ausgeht.
Minimalautomat: Folgerichtig.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:45 Sa 04.05.2013 | | Autor: | bandchef |
So, jetzt aber: http://s14.directupload.net/file/d/3245/8j9qx8md_png.htm
PS: Diese 3 die da so verloren steht, hat da nix zu suchen und keine Bedeutung. Auf meinem Zettel hab ich sie durchgestrichen!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:59 So 05.05.2013 | | Autor: | tobit09 |
> So, jetzt aber:
> http://s14.directupload.net/file/d/3245/8j9qx8md_png.htm
|
|
|
|
