Kompetenzerwartungen
Die Schülerinnen und Schüler ...
- entwickeln formale Sprachen zu Beispielen aus dem Alltag (z. B. Autokennzeichen, E-Mail-Adressen oder Gleitkommazahlen), um ein Verständnis für die Notwendigkeit von klaren Regeln bei der Definition dieser Sprachen zu gewinnen und damit Mehrdeutigkeiten, wie sie in natürlichen Sprachen vorkommen, zu vermeiden.
- definieren formale Sprachen durch Grammatiken und verwenden zur Darstellung der Produktionsregeln insbesondere die Erweiterte Backus-Naur-Form (EBNF) und Syntaxdiagramme.
- entwerfen zur formalen Beschreibung von regulären Sprachen endliche erkennende Automaten.
- implementieren mithilfe einer objektorientierten Programmiersprache fachgerecht deterministische endliche Automaten und nutzen diese zur automatisierten Überprüfung der Zugehörigkeit von Wörtern zu einer regulären Sprache.
- erläutern an selbst gewählten Beispielen, dass es Sprachen gibt, die nicht regulär sind, und erkennen daran, dass es weitere Sprachkategorien in der Informatik gibt. Damit wird den Schülerinnen und Schülern 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 und weitere Modellkonzepte notwendig sind.
Inhalte zu den Kompetenzen:
- Formale Sprache als Menge von Zeichenketten über einem Alphabet: Zeichen, Zeichenvorrat (Alphabet), Wort (Zeichenkette), Syntax, Semantik
- Grammatik: Terminal, Nichtterminal, Produktionsregel, Startsymbol
- Notation formaler Sprachen: Syntaxdiagramm und Erweiterte Backus-Naur-Form (EBNF)
- Ableitung eines Wortes einer formalen Sprache als Folge von Regelanwendungen, Ableitungsbaum
- erkennender endlicher Automat: Zustandsmenge, Eingabealphabet, Zustandsübergang, Startzustand, Endzustand, Fangzustand (Fehlerzustand); reguläre Sprache
- Fachbegriffe: formale Sprache, Alphabet, Grammatik, Terminal, Nichtterminal, Produktionsregel, Startsymbol, Syntaxdiagramm, reguläre Sprache, Ableitung, Ableitungsbaum, Erweiterte Backus-Naur-Form (EBNF), erkennender endlicher Automat, deterministischer endlicher Automat, Eingabealphabet, Startzustand, Endzustand, Fangzustand (Fehlerzustand), Zustandsübergang, Syntax, Semantik