| Die letzten 5 Beiträge |
| Lisa97 |
RE: Kellerautomaten und reguläre Sprachen
Hallo nenam,
hast du die Aufgabe letztendlich gelöst und hast du noch die Lösungen? Ich habe ein sehr ähnliches Beispiel und habe auch Schwierigkeiten
|
| nenam |
(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? |
| nenam |
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. |
| ed209 |
Hi
Woran hakt es? Kannst du mit eigenen Worten informell wiedergeben aus was fuer Woertern L besteht?
Gruss,
ED |
| nenam |
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. |
|
|
