Kontextfreie Grammatik für {a^n b^m c^s d^t | n + m = s + t}?
Ich komme da nicht weiter...
Mein bisheriger Ansatz:
S -> X Y | ε
X -> aaXY | aXbY | XbbY | aa | bb | ab
Y -> XccY | XcYd | XYdd | cc | dd | cd
Dadurch ist aber z.B. X S Y -> bb ε XccY -> bb ε aa cc dd möglich, wobei bb vor aa kommt und das ja nicht geht.
Ich muss ja wegen n+m = s+t das ganze von der Mitte her aufbauen, aber dann schaff ichs nicht, die Reihenfolge und Gleichheit der Anzahl zu halten. (Jetzt passt die Anzahl, weil in der X "Schleife" auch ein Y dazu kommt, aber das zerstört die Reihenfolge. Lass ich das weg, passt die Reihenfolge, aber nicht die Anzahl)
Hat jemand nen Tipp für mich, bitte keine ganze Lösung? :)
1 Antwort
Baue X = b^x c^x für x=min(m,s)
dann Y = a^y X c^y (für y=s–x, falls m<s)
oder Z = b^z X d^z (für z=m–x, falls m>s)
und zum Schluss kannst Du um X, Y und Z noch beliebig viele a und d außen drankleben.
