Aufgabe:
Wir betrachten “fast” korrekt geklammerte Wörter. Ein Wort w uber Σ = {(, ), [, ]} ist “fast” korrekt geklammert, wenn die beiden Wörter w_1 und w_2, welche durch Entfernen von allen Klammern ( und ) bzw. allen Klammern [ und ] aus w entstehen, korrekt geklammert sind.
Zum Beispiel ist ([)[]] fast korrekt geklammert, da sowohl w_1 = [[]] als auch w_2 = () korrekt geklammert sind.
a) Geben Sie für die Sprache aller fast korrekt geklammerten Wörter eine kontextsensitive Grammatik an.
b) Beweisen Sie, dass eben diese Sprache nicht kontextfrei ist.
Problem/Ansatz:
Könnte mir vielleicht jemand helfen?
