Pushdown-Automaten - Lauf < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Wir betrachten den Pushdown-Automaten
$P = [mm] (\{s, 0, 1, 2\}, \{a, b\}, \{A,B, \perp \}, \delta [/mm] , s, [mm] \{0, 1, 2\})$
[/mm]
an, mit:
[mm] $\delta [/mm] = [mm] \{ (s,\lambda ,\perp, 0,A\perp), (0, a, A, 0,AA), (0,\lambda , A, 1,B), (1, a,B, 1,BBB),
(1, b,B, 1,\lambda ), (1, b,B, 2,\lambda ), (2, a,B, 2,\lambda ), (2, a, A, 2, \lambda), (2,\lambda ,\perp, 2,\lambda ) \}$
[/mm]
[Der Automat startet mit der Kellerinschrift [mm] \perp.]
[/mm]
1. Geben Sie einen Lauf von P auf dem Wort w = aaaabbbbaaa an. |
Hallo,
zum Lauf habe ich mir bis jetzt folgende Gedanken gemacht:
$(s, aaaabbbbaaa, [mm] \perp)$ \vdash
[/mm]
$(0, aaaabbbbaaa, [mm] A\perp)$ \vdash
[/mm]
$(0, aaabbbbaaa, [mm] AA\perp)$ \vdash
[/mm]
$(0, aabbbbaaa, [mm] AAA\perp)$ \vdash
[/mm]
Ab jetzt hab ich ein Problem und zwar würde ich hier mit der Übergangsrelation [mm] $(0,\lambda [/mm] , A, 1,B)$ arbeiten und dann würde die nächste Konfiguration so bei mir aussehen:
$(1, aabbbbaaa, [mm] BAAA\perp)$ \vdash
[/mm]
Ich weiß nicht genau ob, das richtig ist; kann es sein, dass ein A verschwinden muss, weil als Symbol auf dem Keller ein A ausgewiesen ist?
Ich hoffe die Frage war verständlich formuliert.^^
Danke schonmal!
Grüße
Kalia
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:07 Fr 16.03.2012 | | Autor: | sandp |
hey,
du kannst natürlich auch Symbole vom Keller wieder weglesen, aber geb mir mal die formale Definition von deinem [mm] \lambda [/mm] dann kann ich dir eine ausführliche Antwort geben.
Gruß sandp
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 So 18.03.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
