Q3 – Theoretische Informatik

In diesem Halbjahr steht die folgende Frage im Mittelpunkt: Was können Computer und was können sie nicht?

Erklär-Videos

• Video 1: Formale Sprachen
• Video 2: Reguläre und kontextfreie Sprachen
• Video 3: Syntaxdiagramme
• Video 4: Endliche Automaten
• Video 5: Endliche Automaten und reguläre Sprachen
• Video 6: Mealy-Automaten und reale Automaten
• Video 7: Reguläre Ausdrücke
• Video 8: Berechenbarkeit
• Video 9: Hypothese von Church und universelle Turingmaschine

Übungsaufgaben

• AB 1: Formale Sprachen und Grammatiken
• AB 2: Syntaxdiagramme, reguläre und kontextfreie Sprachen
• AB 3: Endliche Automaten
• AB 4: Reguläre Ausdrücke
• AB 5: Turingmaschinen
• AB 6: Berechenbarkeit
• AB 7: Komplexitätstheorie
• AB 8: Abschluss

Nützliche Programme

• Automat-Simulator: Simuliert endliche Automaten und Kellerautomaten
• Turing-Maschinen-Simulator: Simuliert Turing-Maschinen
• RegExp-Tester: Dient zum Testen regulärer Ausdrücke.
• Railroad-Diagram-Generator: Generiert Syntax-Diagramme.

Downloads

• Textdateien für die Aufgaben zu den regulären Ausdrücken:
  • functionsTK.mp
  • aufgaben.js