Wortproblem

Dieser Beitrag wird derzeit noch bearbeitet. Der Text ist deshalb unvollständig und kann Fehler oder ungeprüfte Aussagen enthalten.

Das Wortproblem befaßt sich damit, ob ein Wort in einer Sprache ist oder anders gesagt, läßt sich das Wort durch die der Sprache zugrunde liegende Grammatik erzeugen.

Dafür formen wir die Grammatik in Chomsky Normalform um, sofern die Grammatik nicht schon in Chomsky Normalform vorliegt. Dann wenden wir den CYK-Algorithmus an. Dieser ist wie folgt definiert: