Informatiker Board | formale Sprachen | Kellerautomaten und reguläre Sprachen

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Kellerautomaten und reguläre Sprachen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Kellerautomaten und reguläre Sprachen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

nenam
Grünschnabel

Dabei seit: 26.06.2016
Beiträge: 3

Kellerautomaten und reguläre Sprachen

Zitatantwort auf diesen Beitrag erstellen

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

Nehmen Sie nenam in Ihre Freundesliste auf

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

Nehmen Sie ed209 in Ihre Freundesliste auf

nenam
Grünschnabel

Dabei seit: 26.06.2016
Beiträge: 3

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.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von nenam: 26.06.2016 14:09.

26.06.2016 14: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 smile

28.05.2018 01:11

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Kellerautomaten und reguläre Sprachen