Beispiel 5.2

[schrankk]

Einfach indirekter Beweis mittels folgende gsm-Abbildung:

F(q0, a) = (q0, 0)
F(q0, b) = (q1, Eps)
F(q1, b) = (q1, Eps)
F(q1, c) = (q2, 1)
F(q2, c) = (q2, 1)
F(q2, b) = (q3, 2)
F(q3, b) = (q3, 2)

Stimmt so? :)

Bemerkung: mit F bezeichne ich hier eine Übergangsfunktion!

EDIT: Variant2 (mit deutlich weniger Zustände)
F(q0, a) = (q0, 0)
F(q0, b) = (q0, Eps)
F(q0, c) = (q1, 1)
F(q1, c) = (q1, 1)
F(q1, b) = (q1, 2)

EDIT2: letzte Übergang natürlich in q1, nicht q2

[snax]

Habe ein paar Fragen...
1) Warum jetzt GSM und nicht Homomorphismus? Der Abwechslung wegen? =)
2) Wenn man b -> eps setzt sind dann nicht beide b eps und ich kriege etwas in der Form von: {0^kn 1^ln | n >=1} ??

Deiner GSM nach wäre ja {0^kn 1^ln 2^mn | n >=1} das hieße das du nur das erste b auf eps abbildest?

Danke im Voraus!

[schrankk]

Habe ein paar Fragen...
1) Warum jetzt GSM und nicht Homomorphismus? Der Abwechslung wegen? =)
2) Wenn man b -> eps setzt sind dann nicht beide b eps und ich kriege etwas in der Form von: {0^kn 1^ln | n >=1} ??

Deiner GSM nach wäre ja {0^kn 1^ln 2^mn | n >=1} das hieße das du nur das erste b auf eps abbildest?

Danke im Voraus!
1) also genau in solchen Beispielen, wo es ein Symbol auf verschiedene abgebildet werden muss, verwendet man GSM, und nicht Homomorphismen! Da in GSM hängt die Ausgabe von Eingabesymbol und derzeitigem Zustand ab.

2) b->Eps, wenn Automat in Zustand q0 sich befindet. b->2, wenn in q1

vlg

[Fresh Prince]

Also ich glaube nicht, dass deine GSM stimmt!

Hier mein Vorschlag:
S(q0,a)=(q1,0)
S(q0,b)=(q1,E)
S(q1,b)=(q1,E)
S(q1,c)=(q2,1)
S(q2,c)=(q2,1)
S(q2,b)=(q3,2)
S(q3,b)=(q3,2)

Das Beispiel kann man auf jeden Fall auch mit Homomorphismen lösen.

[bsoykal]

Ich hab eine Frage :

die Sprache {a^mn b^sn // n>=1 } ist nicht kontextfrei oder ?

[Krackmoe]

Fresh Prince...

Ich glaub das deins richtig ist.

Bis auf: S(q0,a)=(q1,0³)
und du brauchst nur einmal nen Epsilon Übergang zu machen, finde ich...

Du brauchst da ned 0³ machen oder 1²... weil es ja eh hoch^kn ....
also bis auf die Hochzahlen und den Epsilon Übergang stimmts meiner Meinung nach.

[bsoykal]

kann jemand die gsm Abbildung einbisschen erklaeren :) danke

Ich weiss nur, dass
S(q0,a)=(q1,1)

bei der Übergang von q0 zu q1 les a aber schreib 1
bedeutet.
Aber wie bekommt man die Übergaenge ?
Zeichnen wir erst einen Automat für die gegebene Sprache oder ?

danke !!

[bsoykal]

wo sind alle ?

[schrankk]

to bsoykal: ich weiß nicht genau, was bei gsm du nicht verstehst? Wenn alles, kaum jemand hilft dir! Und hast du Homomorphismen gut verstanden? Die hängen wirklich zusammen!

Es geht also darum, die Symbole von einem Alphabet auf die Symbole von anderem abzubilden! In Homomorphismen auf welche Symbol abgebildet wird hängt nur davon ab, welche Symbol gegeben ist. Also z. B. immer a auf 1. Bei gsm ist noch dazu wichtig, in welchem Zustand man sich gerade befindet! Also z.B. in q1 wird a auf 1 abgebildet, aber schon in q2 wird a auf 3 abgebildet...

[bsoykal]

Naja das versteh ich schon aber wenn ich an deiner Lösung nachschaue, kann ich so ein Automat zeichnen.(attached)

Und mit dieser Automat kann man auch nur ein 1 er bekommen---->(c/1).

Aber bei der Angabe steht 0^kn 1^ln 2^mn und wenn n>=1 ist

dann muss man mindestens ein 0er, 1er und 2er bekommen.

Das war genau meine Frage,

bei der Erstellung der gsm Abb. woran soll ich genau beachten?

:confused::confused:
danke

[bsoykal]

du brauchst nur einmal nen Epsilon Übergang zu machen, finde ich...


was meinst du damit ?

[3M@2mv]

einbisschen minimalistisch aber :wave2:

mein Versuch mit gsm :

F(q0, a) = (q0, 0)
F(q0, b) = (q0, Eps)
F(q0, c) = (q1, 1)
F(q1, c) = (q1, 1)
F(q1, b) = (q1, 2)

sollte meiner Meinung nach stimmen ;)

[3M@2mv]

sorrrrrrrrry habe die zweite Variante von schrankk's Lösung gerade gesehen :shiner:

er hat ja genau dasselbe wie ich, bitte um Verzeihung :engel:

[bsoykal]

Ist deiner gsm deterministisch ?

[3M@2mv]

Ist deiner gsm deterministisch ?

nein ist es nicht, aber es steht im Skriptum

"Die Familie kontextfreier Sprachen ist gegenüber beliebigen gsm-Abbildungen abgeschlossen."

Es muss das gsm nicht unbedingt deterministisch sein meiner Meinung nach

[schrankk]

wenn ich an deiner Lösung nachschaue, kann ich so ein Automat zeichnen.(attached)

Und mit dieser Automat kann man auch nur ein 1 er bekommen---->(c/1).

Aber bei der Angabe steht 0^kn 1^ln 2^mn und wenn n>=1 ist

dann muss man mindestens ein 0er, 1er und 2er bekommen.

Das war genau meine Frage,

bei der Erstellung der gsm Abb. woran soll ich genau beachten?

:confused::confused:
danke
ich denke, da verwächseln viele Leute einen DEA (NEA) mit GSM, da letzte keine Sprache erzeugt, sondern einfach bestimmte Sprache L1 auf eine andere L2 Abbildet... Also wenn es nun in L1 mindestens ein Symbol c vorkommen sollte, so kommt es in L2 mindestens ein 1

[Fresh Prince]

Fresh Prince...

Ich glaub das deins richtig ist.

Bis auf: S(q0,a)=(q1,0³)
und du brauchst nur einmal nen Epsilon Übergang zu machen, finde ich...

Du brauchst da ned 0³ machen oder 1²... weil es ja eh hoch^kn ....
also bis auf die Hochzahlen und den Epsilon Übergang stimmts meiner Meinung nach.

Ja hast recht den ersten Zustand kann ich gleich als Übergang hinschreiben bzw. akzeptieren.
Edit: oben ausgebessert.