Kleines Nachschlagewerk Informatik
Formale Sprachen
Was muss man wissen?
Man muss wissen, was eine formale Sprache ist und wie sie sich von einer natürlichen Sprache unterscheidet.

Man muss die regulären Sprachen als Sonderfall formaler Sprachen kennen. Man muss darüber hinaus wissen, das reguläre Sprachen mit endlichen Automaten erkennbar sind.

Man muss wissen, was linksreguläre und rechtsreguläre Sprachen sind.

Man muss wissen, dass reguläre Ausdrücke immer durch Verkettung, Wiederholung und Alternative darstellbar sind.

Man muss wissen, wie Grammatikregeln dargestellt werden (BNF). Somit muss man wissen, was Terminal- und Nichtterminalsymbole sind.

Man muss Syntaxdiagramme als graphische Darstellung von Grammatikregeln kennen.

Man muss die Sprachenklassen nach Chomsky kennen und Beispiele (zumindest für Typ1-3) parat haben.
Was muss man können?
Man muss die Grammatik einer Sprache angeben, also in Regeln fassen können. Die Angabe muss sowohl formal (Ableitungsregeln, BNF) als auch graphisch (Syntaxdiagramme) erfolgen können.

Man muss aus Anforderungen eine Sprache erstellen können.

Man muss mit Ableitungsbäumen Worte auf Zugehörigkeit testen können.

Man muss mit Produktionsregeln Worte (auch zufällige) erstellen können.
Weitere Fragen