Zum Hauptinhalt springen

Sprachen und Automaten

Formale Sprachen sind Grundlage der Kommunikation mit Automaten und kommen in vielfältigen Anwendungsszenarien in Informatiksystemen zum Einsatz. Im Unterschied zu natürlichen Sprachen haben formale Sprachen eine eindeutig definierte Syntax, die durch Grammatiken, Syntaxdiagramme oder Sprachbeschreibungen dargestellt werden kann. Nach der Form der Produktionen einer Grammatik lassen sich verschiedene Sprachtypen unterscheiden.

Automaten sind zustandsbasierte Systeme, die eine Eingabe zeichenweise lesen und verarbeiten. Automatentypen lassen sich nach der Konzeption ihres Speichers und damit nach ihren prinzipiellen Möglichkeiten und Grenzen unterscheiden. Den Automatentypen sind entsprechende Sprachtypen zugeordnet.
 

Grundlegendes und erhöhtes Anforderungsniveau

Die Schülerinnen und Schüler

  • vergleichen formale mit natürlichen Sprachen,
  • untersuchen den Zusammenhang zwischen einer Grammatik und ihrer Sprache, leiten Wörter einer Sprache ab und stellen Ableitungsbäume dar,
  • verwenden Sprachdefinitionen (z. B. Grammatiken, Syntaxdiagramme) zur Analyse, Beschreibung und Entwicklung formaler Sprachen,
  • überführen Grammatiken in endliche Automaten und umgekehrt.
     

Erhöhtes Anforderungsniveau

Die Schülerinnen und Schüler

  • erläutern den Zusammenhang zwischen Grammatiken, Sprachen und Automaten,
  • analysieren und implementieren Programme zu Problemstellungen auf Kellerautomaten, Turingmaschinen oder Registermaschinen,
  • erläutern prinzipielle und praktische Grenzen der Berechenbarkeit.