Chomsky-Hierarchie < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Ich habe die Aufgabe bekommen, das Schema eines Automaten als Grammatik der Sprache aufzuschreiben. Ich hab dieses Schema skizziert: [Dateianhang nicht öffentlich].
Mein Lösungsvorschlag lautet: [mm] A=(\{a,b\},\{Z_{0};Z_{1}\},\{Z_{0}\to aZ_{1}; Z_{1}\to aZ_{2}\};Z_{0})
[/mm]
Ich kenne mich damit aber nicht so aus, da wir damit nur angefangen haben. Überprüft bitte, ich bin euch sehr dankbar im vorraus
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
| |
|
Hallo webspacer,
> Ich habe die Aufgabe bekommen, das Schema eines Automaten
> als Grammatik der Sprache aufzuschreiben. Ich hab dieses
> Schema skizziert: [Dateianhang nicht öffentlich].
> Mein Lösungsvorschlag lautet:
> [mm]A=(\{a,b\},\{Z_{0};Z_{1}\},\{Z_{0}\to aZ_{1}; Z_{1}\to aZ_{2}\};Z_{0})[/mm]
>
Falls dein Automat nicht sofort bei [mm]Z_0[/mm] stehen bleibt (leere Eingabe [mm]\epsilon[/mm] oder [mm]\lambda[/mm]), führt offenbar nur der Zustand [mm]Z_1[/mm] zu dem 2ten Endzustand [mm]Z_2[/mm]. Zu [mm]Z_1[/mm] gelangst du aber nur, wenn du vorher genau ein a einliest. Und zu [mm]Z_2[/mm] gelangt man nur über das Einlesen von genau einem b. Alle anderen Zeichen z.B. aa.. oder bb... u.s.w. führen dich zu [mm]Z_3[/mm], wo du nicht mehr herauskommst (ein "schwarzes Loch" sozusagen). Bei [mm]Z_2[/mm] hättest du also bereits ab eingelesen. Jetzt kann nur noch ein weiteres a kommen, damit der Automat nicht stoppt und somit die Eingabe verwirft. Und danach bräuchtest du wieder ein b. Der Automat akzeptiert also die Sprache
(ab)*. Deine Grammatik ist deswegen falsch, denn sie generiert keine b's. Folgendes müßte aber gehen:
[mm]A \rightarrow \lambda[/mm]
[mm]A \rightarrow aB[/mm]
[mm]B \rightarrow bA[/mm]
wobei A der Anfangszustand wäre. Das wäre dann:
[mm]A \equiv aB \equiv abA \equiv \dotsm[/mm] u.s.w.
Viele Grüße
Karl
|
|
|
|
