Wortproblem

Aus Byte-Welt Wiki
Version vom 14. Juli 2017, 12:28 Uhr von L-ectron-X (Diskussion | Beiträge)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Zur Navigation springenZur Suche springen


Baustelle.png 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: