Inf13 - Lernbereich 3: Formale Sprachen und Automaten (ca. 24 Std.)

Kompetenzerwartungen: Die Schülerinnen und Schüler ...

untersuchen formale Sprachen aus ihrem Alltag (z. B. Autokennzeichen, E-Mail-Adressen, Gleitkommazahlen) und formulieren Regeln, nach denen die Menge der Wörter der jeweiligen Sprache gebildet wird.
definieren Grammatiken zur Erzeugung formaler Sprachen. Für geeignete Grammatiken verwenden sie zur Notation der Produktionsregeln insbesondere die Erweiterte Backus-Naur-Form (EBNF) und Syntaxdiagramme.
entwerfen zum Erkennen regulärer Sprachen endliche Automaten.
implementieren deterministische endliche Automaten zur automatisierten Überprüfung der Zugehörigkeit von Wörtern zu einer regulären Sprache.
erläutern das Konzept des Nichtdeterminismus bei Automaten anhand geeigneter Beispiele.
erläutern anhand von Beispielen wie beliebig tief geschachtelten Klammerausdrücken, dass es Sprachen gibt, die nicht regulär sind. Damit wird ihnen bewusst, dass für die automatisierte Verarbeitung von nicht regulären Sprachen, wie z. B. höheren Programmiersprachen, das Modell des endlichen Automaten nicht ausreicht.
beschreiben das Modell der Turingmaschine und erläutern anhand von Beispielen ihre Funktionsweise bei der Erkennung von Sprachen.
entwerfen Turingmaschinen für einfache Beispiele Turing-erkennbarer Sprachen.

Inhalte zu den Kompetenzen:

formale Sprache als Menge von Wörtern über einem Alphabet: Zeichen, Alphabet (Zeichenvorrat), Wort (Zeichenkette), Syntax, Semantik
Grammatik: Terminal, Nichtterminal, Produktionsregel, Startsymbol
Notation formaler Sprachen: u. a. Syntaxdiagramm und Erweiterte Backus-Naur-Form (EBNF)
Ableitung eines Wortes einer formalen Sprache als Folge von Regelanwendungen; Ableitungsbaum
endlicher Automat: Zustandsmenge, Eingabealphabet, Zustandsübergang, Startzustand, Endzustand, Fehlerzustand (Fangzustand); reguläre Sprache
Automat: deterministisch, nichtdeterministisch
Turingmaschine: Zustandsmenge, Eingabealphabet, Bandalphabet, Zustandsübergang, Konfiguration; Turing-erkennbare Sprache

Ergänzendes Unterrichtsmaterial