Kontextfreie Grammatik erstellen?
Hey, ich habe folgende Aufgabe:
Aufgabe a habe ich hinbekommen, aber bei Aufgabe b bin ich planlos.
Kann mir da jemand helfen?
1 Antwort
Vom Beitragsersteller als hilfreich ausgezeichnet
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
IT, Informatik, Theoretische Informatik
Als BNF:
S -> aSd | aXc | bYd | bZc | <epsilon>;
X -> aXc | bZc | <epsilon>;
Y -> bYd | bZc | <epsilon>;
Z -> bZc | <epsilon>;
Eventuell kann man das noch vereinfachen.
Dass gilt
m + n = p + q;
Sollte ersichtlich sein dadurch, dass wir immer einmal links und einmal rechts etwas hinzufügen.
Dass die Reihenfolge der Buchstaben gewährleistet wird sollte auch ersichtlich sein, da wir jedes Mal, wenn wir da etwas machen würden, was zu einem invaliden Zustand führen könnten, den Zustand wechseln.
Die Sprache sollte zudem kontextfrei sein, da wir sie in der BNF darstellen konnten.