Automata and Formal Languages - Interactive curriculae of TU Ilmenau

Sicherheit im Umgang mit mathematischen Begriffen (vgl. z. B. Modul "Grundlagen und diskrete Strukturen")

Grundkenntnisse zu Algorithmen (vgl. z. B. Modul "Algorithmen und Programmierung für IN und II" oder "Algorithmen und Datenstrukturen 1"

Fachkompetenz: Die Studierenden kennen die Grundzüge der Theorie der Formalen Sprachen und der Automaten (siehe Inhaltsangabe). Diese Kenntnisse haben sie vorangig in der Vorlesung und im Selbstudium erworben.

Methodenkompetenz: Die Studierenden sind in der Lage, die behandelten Algorithmen und Konstruktionsverfahren an Beispieleingaben auszuführen (Automaten-, Grammatiktransformationen). Sie können Nicht-Regularitätsbeweise und Nicht-Kontextfreiheitsbeweise an Beispielen durchführen. Sie können für vorgegebene Sprachen / Probleme Automaten und/oder Grammatiken konstruieren. Sie können Entscheidungsverfahren und Transformationsverfahren für Automaten und Grammatiken anwenden. Diese Fähigkeiten haben sie vorangig in der Übung und im Selbstudium erworben.

Sozialkompetenz: Die Studierenden können kritische Fragen zum behandelten Stoff, Probleme bei der Erarbeitung des Wissens bzw. bei der Lösung der Aufgaben klar formulieren und in Diskussionen mit Kommilitonen und Lehrenden vertreten.

• deterministische endliche Automaten
  
• reguläre Sprachen, lexikalische Analyse
• Nichtdeterministische endliche Automaten
• Reguläre Ausdrücke
• Äquivalenzbeweise
• Erkennen von Nichtregularität
• Minimierung endlicher Automaten
• Chomsky-Grammatiken
• Kontextfreie Grammatiken und kontextfreie Sprachen
• Normalformen, insbesondere Chomsky-Normalform
• Ableitungsbäume und Ableitungen
• Kellerautomaten, Äquivalenz
• Parsing
  

Folien und Übungsblätter

• Schöning, "Theoretische Informatik kurzgefasst"
• Hopcroft, Motwani, Ullman, "Einführung in die Automatentheorie, Formale Sprachen und Komplexität"
• Asteroth, Baier, "Theoretische Informatik"
• Wegener, "Theoretische Informatik"