---

Geschrieben von nenam am 26.06.2016 um 00:39:

  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.

---

Geschrieben von ed209 am 26.06.2016 um 08:03:

 

Hi

Woran hakt es? Kannst du mit eigenen Worten informell wiedergeben aus was fuer Woertern L besteht?

Gruss,
ED

---

Geschrieben von nenam am 26.06.2016 um 14:03:

 

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.

---

Geschrieben von nenam am 27.06.2016 um 19:31:

 

(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?

---

Geschrieben von Lisa97 am 28.05.2018 um 01:11:

  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