Kellerautomaten und reguläre Sprachen |
nenam
Grünschnabel
Dabei seit: 26.06.2016
Beiträge: 3
|
|
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.
|
|
26.06.2016 00:39 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
Hi
Woran hakt es? Kannst du mit eigenen Worten informell wiedergeben aus was fuer Woertern L besteht?
Gruss,
ED
|
|
26.06.2016 08:03 |
|
|
nenam
Grünschnabel
Dabei seit: 26.06.2016
Beiträge: 3
|
|
(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?
|
|
27.06.2016 19:31 |
|
|
Lisa97 unregistriert
|
|
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
|
|
28.05.2018 01:11 |
|
|
|