CNF und CYK

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche

Druckversion

Farm-Fresh brain.png   Vorwissen

Bevor du hier loslegst, solltest du die folgenden Bausteine zuvor durchgearbeitet haben:

Farm-Fresh pencil add.png   Aufgabe

Überführe die folgende kontextfreie Grammatik (nur die Produktionsregeln sind angegeben) in Chomsky-Normalform. Teste anschließend mit dem CYK-Algorithmus, ob die Wörter bbbabab und abbaba in der von der Grammatik erzeugten Sprache sind.

  • S\rightarrow aB|Ab
  • A\rightarrow BBa
  • B\rightarrow bA|b
Farm-Fresh pencil add.png   Aufgabe

Überführe die folgende kontextfreie Grammatik (nur die Produktionsregeln sind angegeben) in Chomsky-Normalform. Teste anschließend mit dem CYK-Algorithmus, ob die Wörter aaabbcc und abbbccc in der von der Grammatik erzeugten Sprache sind.

  • S\rightarrow ABC
  • A\rightarrow aA|AB|aa
  • B\rightarrow bB|BC|b
  • C\rightarrow cC|c