Worksheet

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

Druckversion

Chomsky-Normalform

Definiere Chomsky-Normalform.











Gib die Regeln an, mit denen man eine beliebige kontextfreie Grammatik in die Chomsky-Normalform überführen kann.































Überführe eine kontextfreie Grammatik deiner Wahl nach diesen Regeln in Chomsky-Normalform. Lasse deine Lösung von einem Kommilitonen überprüfen.



















Begründe, warum Syntaxbäume zu einer CNF-Grammatik immer Binarbäume sind.











Backus-Naur-Form (BNF)

Gib die alternative Beschreibungsform BNF an.



















Gib eine BNF-Grammatik für einfache arithmetische Ausdrücke an.

























Syntaxdiagramme

Gib ein Syntaxdiagramm für einfache arithmetische Ausdrücke an.































CYK-Algorithmus

Überführe die im Video von Christian Spannagel vorgestellte kontextfreie Grammatik in Chomsky-Normalform.



















Überprüfe mit dem CYK-Algorithmus, ob das Wort a-a--a in der Sprache ist.




















Überführe die im Video von Benny Neugebauer vorgestellte kontextfreie Grammatik in Chomsky-Normalform.



















Überprüfe mit dem CYK-Algorithmus, ob das Wort "()[[]]" in der Sprache ist.



















Wie hängt der CYK-Algorithmus mit dem Syntaxbaum der Ableitung des Worts zusammen? (Achtung, Syntaxbaum, nicht Syntaxdiagramm!)











Fragen

Hast du noch Fragen? Notiere sie dir hier, damit du sie in deiner Lerngruppe oder in der nächsten Plenumssitzung klären kannst!