DFA und NFA bestimmen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Geben Sie für jede der folgenden Sprachen über dem Alphabet [mm] \summe_{}^{} [/mm] = {0, 1} jeweils
einen DFA und NFA mit möglichst wenigen Zuständen an:
L1 = {w | w enthält zwei aufeinanderfolgende Nullen},
L2 =Nicht L1 = [mm] \summe_{}^{}* [/mm] \ L1,
L3 = {w | |w| [mm] \ge [/mm] 2 und das zweitletzte Zeichen von w ist eine Eins}. |
Ich habe denke ich das Prinzip Verstanden,aber Trotzdem würde ich gerne wissen ob ich L1 und L2 richtig gelöst habe.Bei L3 bräuchte ich etwas hilfe,da komme ich gar nicht klar mit
Dateianhänge:
Anhang Nr. 1 (Typ: jpeg) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:08 Mi 30.10.2013 | | Autor: | tobit09 |
Hallo nurderfcb!
> Geben Sie für jede der folgenden Sprachen über dem
> Alphabet [mm]\summe_{}^{}[/mm] = {0, 1} jeweils
> einen DFA und NFA mit möglichst wenigen Zuständen an:
> L1 = {w | w enthält zwei aufeinanderfolgende Nullen},
> L2 =Nicht L1 = [mm]\summe_{}^{}*[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
\ L1,
> L3 = $\{$w | |w| [mm]\ge[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
2 und das zweitletzte Zeichen von w ist
> eine Eins$\}$.
> Ich habe denke ich das Prinzip Verstanden,aber Trotzdem
> würde ich gerne wissen ob ich L1 und L2 richtig gelöst
> habe.
Dein NFA für [mm]L_1[/mm] akzeptiert genau die Wörter, die auf zwei 0en enden. ![[notok]](/images/smileys/notok.gif "[notok]")
Dein DFA für [mm]L_1[/mm] ist gar kein DFA.
Bei einem DFA geht von jedem Zustand zu jedem Symbol [mm]a[/mm] des Eingabealphabetes [mm]\Sigma[/mm] genau ein mit [mm]a[/mm] beschrifteter Pfeil aus.
Bei dir geht aber von [mm]Z_0[/mm] und [mm]Z_1[/mm] kein mit 1 beschrifteter Pfeil aus.
Von [mm]Z_1[/mm] gehen zwei mit [mm]0[/mm] beschriftete Pfeile aus.
Von [mm]Z_2[/mm] geht kein mit [mm]0[/mm] beschrifteter Pfeil aus.
(Auch wenn ich deinen DFA als NFA auffasse, akzeptiert er nicht die richtigen Wörter.)
Dein NFA für [mm]L_2[/mm] akzeptiert nur das Wort [mm]01[/mm].
Dein DFA für [mm]L_2[/mm] ist wieder kein DFA und akzeptiert selbst als NFA aufgefasst nicht alle Wörter aus [mm]L_2[/mm].
> Bei L3 bräuchte ich etwas hilfe,da komme ich gar
> nicht klar mit
Diesem (zumindest im Falle des DFA schwierigsten) Teil können wir uns widmen, wenn die ersten beiden Teile gelöst sind.
Viele Grüße
Tobias
|
|
|
|
