Formale Sprachen

[anonym123]

Hallo zusammen,
ich hab ein Problem mit meiner Aufgabe. Ich weiß nicht wie ich dies machen soll und mit was ich üebrhaupt beginnen soll. Eure Hilfe wär echt super! Die Aufgabe lautet:
Die Grammatik hat die Terminale a, b und c, sowie die Nichtterminale A, B und C. Das Startsymbol ist A und die Ableitungsregeln lauten wie folgt: A → aA, A → aB, A → bbB, A → c, B → cbA, B → cC, B → b, C → A, C → bB.
Dazu soll man ein Programm schreiben, welches einen String einliest und entscheidet, ob es ein Wort dieser Grammatik ist.
Eingabe:
Die Eingabe besteht aus einem einzigen String s, der ausschließlich die Zeichen a, b oder c enthält und nicht mehr als 30 Zeichen lang ist.
Ausgabe:
true, falls s ein Wort der Grammatik ist, ansonsten false.

 

[JCODA]

Mhhh, also so richtig zufrieden bin ich mit folgender Antwort nicht, vielleicht weiß jemand was besseres:
1. Möglichkeit: CYK-Algorithmus (https://de.wikipedia.org/wiki/Cocke-Younger-Kasami-Algorithmus). Hierfür braucht man die Grammatik in Chomsky-NF: (https://de.wikipedia.org/wiki/Chomsky-Normalform)
2. Möglichkeit: Backtracking. Das liefert zwar irgendwann eine Lösung, kann aber doch sehr ineffizient sein.
3. Möglichkeit: Eine Art Brute-Force?, indem man alle Wörter erzeugt, die die Länge des Eingabewortes besitzen, und schaut, ob das eingegebene Wort darin vorkommt. Das scheint allerdings viel zu ineffizient zu sein, Speicherverbrauch, Laufzeit ...

Beste Variante scheint CYK-Algo zu sein. Naja, er ist ja genau dafür gemacht

EDIT: Eine andere "Möglichkeit" wäre, einen regulären Ausdruck zu finden, sodass man gar keine Grammatik mehr benötigt. Allerdings geht das ja nicht immer, denn nicht jede Grammatik ist regulär.