 Thema: Kellerautomaten und reguläre Sprachen |
|
|
(c) Geben Sie einen Kellerautomaten M an, und zwar als Rewrite-
System M = (V; Q; T u {c} ;R;A)), der L akzeptiert, wobei
V = {c; p; q; r;Z0;Z2} u T, Q = {p; q; r}, A = {(Z0p;Z2)}
Ich habe versucht den Kellerautomaten zu erstellen. Hier ist meine Lösung:
X wird als Kellersymbol verwendet.
p,x,Z0 -> q,XZ0
p,x,X -> q,XX
p,c,X -> r,X
q,c,X -> p,X
r,x,X -> r, Leerwort
r,Z2,Epsilon -> r,Z0
r,Z2,Z0 -> Lambda
Ich würde gerne wissen, ob das so passt?
|
|
| Thema: Kellerautomaten und reguläre Sprachen |
|
|
Die Angabe wurde allgemein erfasst. Ich habe es so verstanden:
c ist der Trennwort. Da Homomorphismus gegeben ist und auf dem reverse angewendet wird, habe ich es so an einem Bsp angewendet:
Beispielwort: wort
tcrcocwc cwort wäre die Ausgabe.
Grammatik:
Produktion mit Greibachnormalform:
G(L) = (N u T u {c} ; T u {c} ; P; S)
P = {S -> xCSX; S ->c; C -> c; X->x |x ist element T}
Bei mir hängt es besonders an dem Verständnis. Bei d) habe ich überhaupt keinen Ansatz.
|
|
| Thema: Kellerautomaten und reguläre Sprachen |
|
|
Hallo,
ich bin sehr verzweifelt und hänge an einem Übungsbeispiel, die 100% so ähnlich zur Klausur nächste Woche kommen wird. Ich hoffe ihr könnt mir helfen.
Sei L eine kontextfreie formale Sprache über dem Alphabet T u {c} mit
c kein Element von T wie folgt definiert:
L = {h(w)^R cw| w element aus T*};
wobei gilt, dass h(x) = cx für alle x element aus T .
(c) Geben Sie einen Kellerautomaten M an, und zwar als Rewrite-
System M = (V; Q; T u {c} ;R;A)), der L akzeptiert, wobei
V = {c; p; q; r;Z0;Z2} u T, Q = {p; q; r}, A = {(Z0p;Z2)}.
(d) Die Famile der regulären Sprachen ist gegenüber beliebigen gsm-
Abbildungen abgeschlossen. Zeigen Sie unter Verwendung dieser
Abschlusseigenschaft, dass L nicht regulär sein kann, indem Sie eine
geeignete gsm M mit maximal 4 Zuständen (der vierte Zustand ist
der Endzustand) konstruieren, die L auf die bekannte nicht-reguläre
Sprache {a^nb^n|n <=0} abbildet. Geben Sie die gsm M sowohl
graphisch als auch mit einer formalen Beschreibung (beachten Sie,
dass in diesem Fall nur drei Zustände erforderlich sind) an.
|
|
|
