Metadaten

Endliche Automaten

• • mithilfe ihrer Definition interpretieren
  • eine Simulation zum Analysieren, Visualisieren und Implementieren nutzen
  • Aufbau und Arbeitsweise anhand eines anschaulichen Modells beschreiben

Formale Sprache

• • verbal, durch Angabe eines Musters oder aller Wörter beschreiben
  • mathematische Darstellungen einer Sprache interpretieren
  • aus einem Syntaxdiagramm ableiten
  • die von einem Automaten akzeptierte Sprache bestimmen

Mealy-Automat MA = (X, Y, Z, δ, λ, z0)

• • Überführungs- und Ausgabefunktion tabellarisch und grafisch darstellen
  • einen Mealy-Automaten modellieren

Akzeptor A = (X, Z, δ, z0, ZE)

• • Überführungsfunktion tabellarisch und grafisch darstellen
  • einen Akzeptor anhand einer gegebenen Sprache modellieren
  • eine Grenze von Akzeptoren erläutern

Turingmaschine TM = (X, Z, Γ, δ, z0, $, ZE)

• • den Wert des Modells anhand der Church-Turing-These begründen
  • die Grenzen einer Turingmaschine anhand des Halteproblems erklären

zusätzlich für den Leistungskurs

Kellerautomat KA = (X, Z, Γ, δ, z0, k0, ZE)

• • das Prinzip eines Kellerspeichers und die Kelleroperationen push, pop und nop erläutern
  • einen Kellerautomaten anhand einer gegebenen Sprache modellieren
  • Prinzip des Nichtdeterminismus anhand der Erkennung von Palindromen erläutern
  • eine Grenze von Kellerautomaten erläutern

Turingmaschine

• • eine Turingmaschine anhand einer gegebenen Sprache modellieren

ausschließlich für den Leistungskurs

Grammatik G = (T, N, P, S)

• • mithilfe der Definition beschreiben
  • Wörter nachvollziehbar ableiten
  • die Ableitbarkeit von Wörtern untersuchen
  • die erzeugte Sprache bestimmen
  • zu einer gegebenen regulären Sprache eine Grammatik entwickeln

Chomsky-Hierarchie

• • den Typ einer Grammatik bestimmen
  • den Zusammenhang zwischen Grammatik, Sprache und Automat mithilfe der Chomsky-Hierarchie beschreiben
  • für eine aus einer regulären oder kontext-freien Grammatik erzeugte Sprache einen erkennenden Automaten angeben