endlicher automat < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:06 Sa 31.01.2009 | | Autor: | tugba |
| Aufgabe 1 | Sei die Sprache L definiert wie folgt
[mm] L:={w\in\{ a,b \}^{\*}| w=a^{\*} oder
|w|_{b} mod 3=1}. [/mm] Geben sie einen deterministischen endlichen Automaten M an, für die gilt L(M)=L |
| Aufgabe 2 | | Ist die Sprache L auch vom Typ2? Wenn Ja, geben Sie eine kontexfreie Grammatik an, die L erzeugt. falls nein, warum ist sie nicht kontexfrei? |
Hallo,
Ich habe soweit die Aufgaben gelöst, und möchte wissen ob die Antworten auch so richtig sind.
zu Aufgabe1:
M=( Zustände={z0, z1, z2, z3}, Eingabealphabet={a,b},
überführungsfunktion={ [mm] \delta(z0,a)=z0, \delta(z0,b)=z1, [/mm]
[mm] \delta(z1,a)=z1, [/mm]
[mm] \delta(z1,b)=z2, [/mm]
[mm] \delta(z2,a)=z2, [/mm]
[mm] \delta(z2,b)=z3, [/mm]
[mm] \delta(z3,a)=z3,
[/mm]
[mm] \delta(z3,b)=z1 [/mm] }, Satrtzustand={z0}, endzustand={z0,z1})
zu Aufgabe2:
Die Sparche ist kontexfrei, da wir in Aufgabe1 einen endlichen Automaten gezeichnet haben, heißt es, dass die Sprache regulär bzw. vom Typ3 ist und wie wir wissen ist Typ 3 Sprachen echte untermengen vom Typ 2 Sprachen.
Die Garmmatik lautet dann:
G:=({S,A},{a,b},P,S) mit der Regelmenge
P={ [mm] S\to\varepsilon, S\toA, A\to [/mm] aA|aAa|a|b }
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:12 Sa 31.01.2009 | | Autor: | bazzzty |
> Sei die Sprache L definiert wie folgt
> [mm]L:={w\in\{ a,b \}^{\*}| w=a^{\*} oder
|w|_{b} mod 3=1}.[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
> zu Aufgabe1:
> M=( Zustände={z0, z1, z2, z3}, Eingabealphabet={a,b},
>
> überführungsfunktion={ [mm]\delta(z0,a)=z0, \delta(z0,b)=z1,[/mm]
> [mm]\delta(z1,a)=z1,[/mm]
> [mm]\delta(z1,b)=z2,[/mm]
> [mm]\delta(z2,a)=z2,[/mm]
> [mm]\delta(z2,b)=z3,[/mm]
> [mm]\delta(z3,a)=z3,[/mm]
> [mm]\delta(z3,b)=z1[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
}, Satrtzustand={z0},
> endzustand={z0,z1})
Ja, bestens.
> zu Aufgabe2:
> Die Sparche ist kontexfrei, da wir in Aufgabe1 einen
> endlichen Automaten gezeichnet haben, heißt es, dass die
> Sprache regulär bzw. vom Typ3 ist und wie wir wissen ist
> Typ 3 Sprachen echte untermengen vom Typ 2 Sprachen.
Ja, schöne Begründung.
> Die Garmmatik lautet dann:
> G:=({S,A},{a,b},P,S) mit der Regelmenge
> P={ [mm]S\to\varepsilon, S\toA, A\to[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
aA|aAa|a|b }
Ich verstehe nicht, wie Du auf so eine Lösung kommst. Diese Grammatik läßt nur Wörter mit genau einem [mm]b[/mm] zu, aber zum Beispiel nicht [mm]bbbb[/mm].
Mein Tipp: Wenn Du schon weißt, dass die Sprache regulär ist, dann schreib doch eine reguläre Grammatik! Auch wenn das noch nicht explizit dran war: Du kannst aus den Zuständen und Übergängen des Automaten ablesen, wie der etwa aussehen muss!
|
|
|
|
