Beispiel 4.5

[manül]

Bin beim Nachdenken auf 2 mögliche Lösungen gestoßen, also nicht wundern:

\{ a^{3n-4}b^{2k}a^{2n} | n \gt 1, k \ge 2\} \Leftrightarrow \{ a^{3n-1}b^{2k}a^{2n+2} | n \ge 1, k \ge 2\}

a) S \rightarrow a^2Aa^4, A \rightarrow a^3Aa^2, A \rightarrow b^2B, B \rightarrow b^2B, B \rightarrow b^2

Linksableitungen für n \gt 1, k \ge 2:
S \Rightarrow a^2Aa^4 \Rightarrow^{n-2} a^2a^{3(n-2)}Aa^4a^{2(n-2)} \Rightarrow a^{3n-4}b^2Ba^{2n} \Rightarrow^{k-2} a^{3n-4}b^2b^{2(k-2)}Ba^{2n} \Rightarrow a^{3n-4}b^{2k}a^{2n}

Linksableitungen für n \ge 1, k \ge 2:
S \Rightarrow a^2Aa^4 \Rightarrow^{n-1} a^2a^{3(n-1)}Aa^4a^{2(n-1)} \Rightarrow a^{3n-1}b^2Ba^{2n+2} \Rightarrow^{k-2} a^{3n-1}b^2b^{2(k-2)}Ba^{2n+2} \Rightarrow a^{3n-1}b^{2k}a^{2n+2}

gsm (S = Sigma):
- wähle l=m=0
S(q0, a) = (q0, \eps)
S(q0, b) = (q0, \eps)

oder: l=3, m=2
S(q0, a) = (q1, 0^2)
S(q1, a) = (q1, 0)
S(q1, b) = (q2, \eps)
S(q2, b) = (q2, \eps)
S(q2, a) = (q3, \eps)
S(q3, a) = (q4, \eps)
S(q4, a) = (q4, 1)

Mein allgemeiner gsm (ist nicht gefragt):
Update (S = Sigma):
S(q0, a) = (q1, \eps)
S(q1, a) = (q2, l)
S(q2, a) = (q2, l/3)
S(q2, b) = (q3, \eps)
S(q3, b) = (q3, \eps)
S(qi, a) = (qi+1, \eps) für 3 <= i <= 6
S(q7, a) = (q8, m)
S(q8, a) = (q8, m/2)

Update: 4n/2n-Bug gefixed + simpler gsm :)
- 2B/4B fixed + Linksableitungen auch endlich korrekt...

und jetzt stimmts definitiv...

[jperl]

a) A \rightarrow b^2B



sollte imho

A \rightarrow b^4B

sein.

außerdem ist die linksableitungen ein wenig schnell gemacht und enthält kleine fehler und unstimmigkeiten.

zb wird aus b^2(k-1) auf einmal 2^k.

jperl

zum rest kann ich nichts sagen, den habe ich selber noch nicht. ^^

[manül]

sollte imho A \rightarrow b^4B sein.
Ja, sorry. Hast recht. Werds gleich ausbessern. ich hab bei dem Bsp viel rum probiert und sinnlos umgeformt. So ist auch der Abschreibfehler zustande gekommen :sudern:
<Hier stand viel Blödsinn>

außerdem ist die linksableitungen ein wenig schnell gemacht und enthält kleine fehler und unstimmigkeiten.

zb wird aus b^2(k-1) auf einmal 2^k.
Höchstens Tippfehler, aber b^2(k-1) wird b^2k, wenn man b^2 durch eine Produktion dazu zählt.

[jperl]

also ich versteh nicht ganz genau was du da machst.

die b^4 kannst du ja nur ganz am anfang einmal nehmen.
und dann musst du ja nochmal k-2 mal das b^2 nehmen.
sprich 2*(k-2) = 2k -4
mit den 4 bs von vorhin sind das dann ganz genau 2k.

jperl

[schrankk]

mit deiner Lösung kannst du aber ausschlieslich b^6 erzeugen, oder??

bei mir liegt der Unterschied darin: A-> b^2 * B, B -> b^2 * B, B -> b^2

[manül]

die b^4 kannst du ja nur ganz am anfang einmal nehmen.
Ohje. Dass es da bei der 3. Ableitung von A auf B geht, hab ich gar nicht gesehen. Stimmt natürlich, danke.
Interessant ist aber, auf was für wirre Gedanken ich da gekommen bin, nur um irgendwie auf die Ursprungsform zu kommen :p
Werd mal alles editieren/löschen.

[Fresh Prince]

Bin beim Nachdenken auf 2 mögliche Lösungen gestoßen, also nicht wundern:

\{ a^{3n-4}b^{2k}a^{2n} | n \gt 1, k \ge 2\} \Leftrightarrow \{ a^{3n-1}b^{2k}a^{2n+2} | n \ge 1, k \ge 2\}

a) S \rightarrow a^2Aa^4, A \rightarrow a^3Aa^2, A \rightarrow b^2B, B \rightarrow b^2B, B \rightarrow b^2

Linksableitungen für n \gt 1, k \ge 2:
S \Rightarrow a^2Aa^4 \Rightarrow^{n-2} a^2a^{3(n-2)}Aa^4a^{2(n-2)} \Rightarrow a^{3n-4}b^2Ba^{2n} \Rightarrow^{k-2} a^{3n-4}b^2b^{2(k-2)}Ba^{2n} \Rightarrow a^{3n-4}b^{2k}a^{2n}

Linksableitungen für n \ge 1, k \ge 2:
S \Rightarrow a^2Aa^4 \Rightarrow^{n-1} a^2a^{3(n-1)}Aa^4a^{2(n-1)} \Rightarrow a^{3n-1}b^2Ba^{2n+2} \Rightarrow^{k-2} a^{3n-1}b^2b^{2(k-2)}Ba^{2n+2} \Rightarrow a^{3n-1}b^{2k}a^{2n+2}

gsm (S = Sigma):
- wähle l=m=0
S(q0, a) = (q0, \eps)
S(q0, b) = (q0, \eps)

oder: l=3, m=2
S(q0, a) = (q1, 0^2)
S(q1, a) = (q1, 0)
S(q1, b) = (q2, \eps)
S(q2, b) = (q2, \eps)
S(q2, a) = (q3, \eps)
S(q3, a) = (q4, \eps)
S(q4, a) = (q4, 1)

Mein allgemeiner gsm (ist nicht gefragt):
Update (S = Sigma):
S(q0, a) = (q1, \eps)
S(q1, a) = (q2, l)
S(q2, a) = (q2, l/3)
S(q2, b) = (q3, \eps)
S(q3, b) = (q3, \eps)
S(qi, a) = (qi+1, \eps) für 3 <= i <= 10
S(q10, a) = (q11, m)
S(q11, a) = (q11, m/4)

Update: 4n/2n-Bug gefixed + simpler gsm :)
- 2B/4B fixed + Linksableitungen auch endlich korrekt...

und jetzt stimmts definitiv...

Ich habe ebenfalls fälschlicherweise eine allgemeine GSM entworfen, hab das mit deterministisch gerade jetzt bemerkt. Wie kommt man von der normalen GSM auf die deterministische. Wie bist du hier vorgegangen, ich habe nur ein einfaches Beispiel in den Folien(133) gefunden, aber es ist viel zu einfach und hat sehr wenig Ähnlichkeit mit dem was du hast.

lg

[manül]

Ich habe ebenfalls fälschlicherweise eine allgemeine GSM entworfen, hab das mit deterministisch gerade jetzt bemerkt. Wie kommt man von der normalen GSM auf die deterministische. Wie bist du hier vorgegangen, ich habe nur ein einfaches Beispiel in den Folien(133) gefunden, aber es ist viel zu einfach und hat sehr wenig Ähnlichkeit mit dem was du hast.
Hab grad gesehen, dass der Allgemeine noch den 4n/2n-Fehler hatte. Hab die Zustände also entsprechend reduziert.

Ich hab mir den direkt deterministisch überlegt. Ist imho auch einfacher. Vorher eventuell ein paar Produktion anschreiben, wenn man was visuelles benötigt.

Meine Denkweise für den Allgemeinen war:
- Bei den a zu Beginn kommen nach der ersten Produktion immer 3a dazu. Daher die Schleife mit l/3. Bleiben mir noch die 2a zu Beginn übrig. Wegen n>=1 brauche ich ein l, "lösche" also eines und für das andere gebe ich l aus.
- Die b "lösch" ich alle.
- Die a am Ende sind zu Beginn 4a, danach immer +2a. Also m/2 für die Schleife. Und analog zum ersten Gedanken, "lösche" ich 3a und geb 1xm aus.
Aber ich bin mir nicht sicher ob man überhaupt l/3,m/2 schreiben dürfte, denn so muss ja l durch 3 und m durch 2 ganzzahlig teilbar sein. Besser sind die anderen 2, mit konkreten Werten.