Formale Sprachen, Automatentheorie, Berechenbarkeit, Entscheidbarkeit

• Inhaltsverzeichnis
• Formale Sprachen, Grammatiken
• Endliche Automaten, reguläre Sprachen
• Kellerautomaten
• Turing-Maschine
• Beispiel einer Turingmaschine (für die Nachfolger-Funktion)
• Mehrband-Turing-Maschine
• Komposition und Rückkopplung
• Simulation von Turing-Maschinen durch GOTO-Programme
• Übersetzung von Turing-Maschinen in Grammatiken
• Linear beschränkter Automat
• LOOP - WHILE -GOTO-Programme
• Syntaxdiagramm von LOOP
• Primitiv rekursive Funktionen
• Ackermannfunktion
• Entscheidbarkeit, Semi-Entscheidbarkeit, rekursiv aufzählbar
• Halteproblem, naiv
• Codierung von Turing-Maschinen, Halteprobleme
  
• Postsches Korrespondenzproblem (PKP)
• Reduktion des Halteproblems auf das PKP

Aktuelle Vorlesungsfolien (pdf-Format)

Anhang (ergänzendes Material)

• Mathematische Grundlagen 
• Übersicht zum Teil Formale Sprachen
  
• Zusammenhänge Formale Sprachen
• Bestandteile von Grammatiken
• Erkennende Automaten
• Übersicht zum Teil Reguläre Sprachen
  
• Übersicht zum Teil Kontextfreie Sprachen
  
• Übersicht zum Teil Kontextsensitive Sprachen