Hallo!

Nur mal zur Info: Die offiziellen Musterlösungen zu Blatt 12 sind zwar noch nicht da (warum dauert das eigentlich immer so lange?), aber die Lösung für Aufgabe 12.2, die die Übungsgruppenleiter hatten, lautete:
[img]http://mokrates.de/cgi-bin/texstring?P_3%20%3D%20P_1%20%5Ccup%20P_2%20%5Ccup%20%5C%7BS%20%5Clongrightarrow%20S_1S_2%5C%7D[/img] mit S als neuem Startsymbol.
Das ist natürlich falsch, da in einer kontextsensitiven Grammatik nur die Epsilonproduktion vom Startsymbol aus erlaubt ist, aber [img]http://mokrates.de/cgi-bin/texstring?(S_2%20%5Clongrightarrow%20%5Cepsilon)%20%5Cin%20P_2[/img].

Eine richtige Lösung wäre:
[img]http://mokrates.de/cgi-bin/texstring?P_3%20%3D%20%5C%7BS%20%5Clongrightarrow%20acS%5C%20%7C%5C%20ac%5C%20%7C%5C%20aS_2%5C%20%7C%5C%20a%3B%20S_2%20%5Clongrightarrow%20bS_2a%5C%20%7C%5C%20ba%20%5C%7D[/img]

Da hast du recht. Neben den Epsilon-Produktionen muss
man beim Zusammensetzen von kontextsensitiven Grammatiken
aber auch darauf achten, dass mögliche Kontexte nicht über
die Wortgrenze hinausragen. Die erste angegebene Produktionen-
menge erlaubt nämlich zudem noch die Ableitung
[img]http://mokrates.de/cgi-bin/texstring?S%5CRightarrow%20S_1S_2%5CRightarrow%20aBS_2A%20%5CRightarrow%20aCS_2A[/img]
[img]http://mokrates.de/cgi-bin/texstring?%5CRightarrow%20acS_2A%5CRightarrow%20acBS_2AA%20%5CRightarrow%20acbaa[/img]
und das ist offensichtlich unerwünscht. Das kann man
reparieren, indem man die Terminale, die in Kontexten
auftauchen, durch Nonterminale simuliert und
dann die beiden Nonterminalmengen disjunkt macht. Wenn
man dann noch an die Epsilon-Elimination denkt, kann man
fast die obige Konstruktion verwenden [img]http://www.fb18.de/gfx/28.gif[/img]

Das Formulieren einer korrekten allgemeinen Konstruktion
ist sicher eine gute Übung! [img]http://www.fb18.de/gfx/23.gif[/img]

(Aber deine konkrete Lösung sieht gut aus.)

Da hast du recht. Neben den Epsilon-Produktionen muss
man beim Zusammensetzen von kontextsensitiven Grammatiken
aber auch darauf achten, dass mögliche Kontexte nicht über
die Wortgrenze hinausragen.

Ich musste zwar erstmal das Beispiel lesen, um zu verstehen, was Du meinst, aber das stimmt. Das hatte ich noch gar nicht bemerkt. Vielleicht wird das ja mal wichtig.
Außerdem macht das die vorläufige Musterlösung noch verkehrter - ich bin mal gespannt, wie die offizielle Musterlösung dann aussieht.

Das kann man reparieren, indem man […]

Jo, so würde das gehen. Aber ich glaube, so lange ich das selbst machen muss und nicht ein Programm dafür schreibe, gehe ich lieber den Weg über die Sprache - überlegen, wie die ursprünglichen Sprachen aussehen (Mengendarstellung), das dann korrekt konkatenieren und daraus wieder eine Grammatik basteln. Zumindest bei so überschaubaren Sprachen wie in der Aufgabe.

Das war ich.
(Vom Laptop draußen auf den Desktop drinnen gewechselt - da erkennt er mich immer nicht wieder.)

Das kann man reparieren, indem man […]

Jo, so würde das gehen. Aber ich glaube, so lange ich das selbst machen muss und nicht ein Programm dafür schreibe, gehe ich lieber den Weg über die Sprache - überlegen, wie die ursprünglichen Sprachen aussehen (Mengendarstellung), das dann korrekt konkatenieren und daraus wieder eine Grammatik basteln. Zumindest bei so überschaubaren Sprachen wie in der Aufgabe.

Solche allgemeinen Konstruktionen sind vor allem interessant,
weil sie die Abgeschlossenheit (in diesem Fall gegenüber
Konkatenation) beweisen und man, wenn man das einmal gezeigt
hat, solche Grammatiken garnicht mehr hinschreiben muss
(außer vielleicht in Klausuren und Übungsaufgaben…) [img]http://www.fb18.de/gfx/28.gif[/img]