Beispiel 5.3

[schrankk]

Einfach indirekter Beweis mittels folgende Homomorphismus: h(a)=a^3; h(b)=Eps; h(c)=b^2; h(d)=c^3. Oder?!

vlg

[snax]

Ich habe es auch mittels Homomorphismus bewiesen... bin so vorgegangen:

h(a) = a
h(b) = eps
h(c) = b
h(d) = c

L' = {a^kn b^ln c^mn | n >= 1 } <=> L' = {a^2n b^3n c^2n | n >= 1} k=m=2, l= 3

oder muss man es so anschreiben wie schrankk? Bitte um Feedback...

Lg Stefan

[schrankk]

Ich habe es auch mittels Homomorphismus bewiesen... bin so vorgegangen:

h(a) = a
h(b) = eps
h(c) = b
h(d) = c

L' = {a^kn b^ln c^mn | n >= 1 } <=> L' = {a^2n b^3n c^2n | n >= 1} k=m=2, l= 3

oder muss man es so anschreiben wie schrankk? Bitte um Feedback...

Lg Stefan
in diesem Beispiel ist aber nicht gegeben, dass {a^kn b^ln c^mn | n >= 1 } kontextfrei ist!! :rolleyes: Es ist zwar in Skriptum bewiesn, aber halt mittels P.L., die wir in diesem Beispiel nicht verwenden dürfen (nur in vorigem)! Aber deine Lösung ist natürlich auch richtig!!

[snax]

Crap! ;-) in dem Fall ignoriert meinen oberen Post *g*

[Bianconeri]

Habe genau den gleichen Homomorphismus wie schrankk. Ist dadurch, dass ja in der Angabe steht auf was wir kommen sollen irgendwie bisschen einfach gewesen. Hoffe wir ham da das richtige gemacht ;)

[Lumpaci]

ich hab auch hier eine gsm angewandt. in dieser werden die ersten a und b symbole zu eps, die folgenden c,b,d zu entsprechend vielen a,b,c (sodass diese jeweils hoch 6n werden).

sollte doch auch funktionieren, oder?

[Fresh Prince]

Ich hab das Beispiel ebenfalls mit Homorphismus gelöst(Beweis indirekt)
Angenommen die Sprache L1= kontextfrei
h(a)=a³
h(b)=E
h(c)= b²
h(d)= c³

Hoffe das stimmt so!

[Krackmoe]

Habs genauso Fresh.

[Fl@sh]

ich hab mal eine gsm entworfen
bitte um (konstruktive) kritik

sorry, wenn ich eure homomorphismen durcheinander werfe...

lg Edi :)

[schrankk]

ich hab mal eine gsm entworfen
bitte um (konstruktive) kritik

sorry, wenn ich eure homomorphismen durcheinander werfe...

lg Edi :)

da reicht nur ein Zustand mit 4 Pfeilen!! ;)

[Fl@sh]

hmm... kannst du das vielleicht genauer erklären bitte?
is meine gsm total falsch oder wie soll das mit einem zustand gehen?!?

bin etwas verwirrt...

[schrankk]

hmm... kannst du das vielleicht genauer erklären bitte?
is meine gsm total falsch oder wie soll das mit einem zustand gehen?!?

bin etwas verwirrt...
Verwächsle GSM nicht mit DEA (NEA), der bestimmte Sprache akzeptieren soll, und andere nicht... GSM ist eine einfache Abbildung!! Deswegen egal welche Symbol in unserem Fall vorkommt, wir bleiben in Startzustand (der auch Endzustand ist), nur die Ausgabe für verschiedene Symbole wird verschieden... und da es 4 verschiedene Symbole gibt, wird es 4 Pfeilen zu sich selbst mit 4 verschiedenen Beschriftungen geben...

vlg

P.S.
wenn ich mich nicht irre, ist jede Homomorphismus einen GSM mit einem Zustand!! Da in Homomorphismus hängt die Ausgabe von gegebenem Symbol ab, und in einem GSM noch von derzeitigem Zustand