Kontextfreie Grammatik -> PDA < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 21:00 Do 03.07.2008 | | Autor: | Wimme |
| Aufgabe | Geben Sie einen PDA (Push Down Automata - Kellerautomat) mit nur einem Zustand für die Sprache an, die durch folgende Grammatik erzeugt wird:
S [mm] \to [/mm] aSa|aSb|$ |
Hi!
Ich habe eine Konstruktion für obiges Problem gefunden, die meines Erachtens aber nicht funktioniert.
Also die Konstruktion geht angeblich so:
Sei G = (N, [mm] \Sigma, [/mm] P, S) gegeben.
Konstruiere den PDA A = (Q, [mm] \Sigma, [/mm] G, q0, Z0, [mm] \Delta) [/mm] wie folgt:
Q = {q0}, G = N [mm] \cup \Sigma, [/mm] Z0 = S
Dann enthält [mm] \Delta [/mm] die folgenden Transitionen:
(q0, [mm] \epsilon, [/mm] X, a, q0) für jede Regel X [mm] \to \alpha [/mm] von G
(q0, a, a, [mm] \epsilon, [/mm] q0) für jedes Terminalsymbol a [mm] \in \Sigma
[/mm]
Ich hoffe ihr seid mit den Bezeichnungen vertraut, bzw. wisst diese zu deuten.
tja, wenn ich das mache, würde ich doch 6 Regeln aufstellen. 3 für S und jeweils eine für a,b,$. Was ich jetzt aber nicht verstehe: Ich tue ja S auf meinen Keller, bekomme diese aber niemals (außer eins an der richtigen Stelle mit $) wieder weg. Wie soll denn das gehen??
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Sa 05.07.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
