Automaten, Formale Sprachen und Berechenbarkeit (WS 2004/05)

Prof. Dr. Markus Holzer

Bereich:
4 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Wahlpflichtvorlesung im Gebiet syntaktische und operationelle Beschreibungen

Zeit und Ort:
Mittwoch, 8.30-10.00 Uhr, Hörsaal MI 00.04.011
Freitag, 10.15-11.45 Uhr, Hörsaal MI 00.04.011
Beginn: Freitag 22.10.2004

Die Vorlesung entfält am Freitag 4. Februar.

Klausur: Eine Anmeldung ist nicht erforderlich.
Mittwoch, den 16. Februar 2005, 12.00-14.00 Uhr, Hörsaal MI HS 1
Hilfsmittel sind keine erlaubt.

Übung:
2 SWS Übung zur Vorlesung
Übungsleiter: Dr. Stefan Katzenbeisser
Dienstag, 16.00-18.00, Raum 00.07.011
Beginn: Dienstag 2.11.2004
1. Übungsblatt
2. Übungsblatt
3. Übungsblatt
4. Übungsblatt
5. Übungsblatt
6. Übungsblatt
7. Übungsblatt
8. Übungsblatt
9. Übungsblatt
10. Übungsblatt
11. Übungsblatt
12. Übungsblatt

Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik

Voraussetzungen:
Stoff des Informatik-Grundstudiums, insbesondere TGI und die Vorlesung Informatik IV

Inhalt: [PS],[PDF]

• Berechenbarkeit
  • Allgemeines zu Automaten und formale Sprachen, Berechenbarkeit, einige Beispiele.
  • Grundlagen: Mengen, Relationen, Bild und Urbild, Abbildungen (injektiv, surjektiv, bijektiv), Kardinalit"atsgleichheit von Mengen, Abz"ahlbarkeit und "Uberabz"ahlbarkeit, Satz von Schr"oder-Bernstein, Kardinalit"atsargumente (nat. Zahlen, reelle Zahlen, offenes Einheitsintervall), Satz von Cantor, Diagonalisierung.
  • While-Programme: Syntax, Sematik, Marko-Anweisungen, Definition von effektiv berechenbar, Church-Turing These, andere M"oglichkeiten der Formalisierung.
  • Standardtechniken: G"odelsierung, Standardaufz"ahlung von Funktionen, nicht Berechenbarkeit des Halteproblems, universelle Funktion, Enumerationstheorem, s-m-n Theorem.
  • Unentscheidbare Probleme: Definition von Entscheidbarkeit, Halteproblem, Totalit"atsproblem---es gibt totale Funktionen die nicht berechenbar sind, allgemeines Halteproblem, Identit"atsproblem, "Aquivalenzproblem.
  • Rekursionstheorem und Eigenschaften von Aufz"ahlungen: Rekursionstheorem, Beispiele mit einfachen Programmtransformationsfunktionen, Anzahl der Fixpunkte, Selbstreferenzierung und Programme die ihren eigenen Quellcode ausgeben, akzeptable Programmiersysteme, Rogers Isomorphie Theorem f"ur akzeptable Programmiersysteme.
  • LOOP-Programme: Syntax, Semantik, Makro-Anweisungen, Definition loop-berechenbar, Totalit"at von loop-berechenbaren Funktionen, Definition busy-beaver Funktion f"ur loop-Programme, busy-beaver Funktion ist nicht loop-berechenbar, Hinweis zur busy-beaver Funktion f"ur while-Programme, Definition Ackermannfunktion, intuitiver Aufbau der Ackermannfunktion, Wachstumsargument f"ur loop-Programme, Ackermannfunktion ist nicht loop-berechenbar, es gibt keine loop-universellen loop-Programme.
  • Berechnbare Eigenschaften von Mengen: Definition Entscheidbarkeit, einfache Eigenschaften von entscheidbaren Mengen, Definition rekursive Aufz"ahlbarkeit, Beziehungen von entscheidbare und rekursiv aufz"ahlbaren Mengen, einfache Beispiele entscheidbarer und rekursiv aufz"ahlbarer Mengen, Entscheidbarkeit entspricht rekursiver Aufz"ahlbarkeit und co-Aufz"ahlbarkeit, Entscheidbarkeit entspricht rekursiver Aufz"ahlbakeit in aufsteigender Reihenfolge, alternative Charakterisierungen von rekursiver Aufz"ahlbarkeit durch Bild- und Urbildbereich von Funktionen, Standardaufz"ahlung von rekursiv aufz"ahlbaren Mengen, einfache Operationen auf rekursiv aufz"ahlbaren Mengen.
  • Die S"atze von Rice: Definition Indexmenge die Funktionen respektiert, Satz von Rice, einfache Beispiele, Satz von Rice---Variante I und II bzgl. rekursiver Aufz"ahlbarkeit, Definition many-one Reduktion, einfache Eigenschaften von many-one Reduktionen, Definition Turing Reduktion, einfache Eigenschaften von Turing Reduktionen, Vollst"andigkeit der Menge K (Menge der Indizes so, da\ss~$i$ auf Programm~$i$ terminiert).
  • Alternative Modelle der Berechenbarkeit: Definition primitiv rekursiver Funktionen, primitiv rekursiv entspricht loop-berechenbar. Definition $\mu$-rekursive Funktionen, $\mu$-rekursiv entspricht while-berechenbar, Definition Turingmaschine, Variationen der Speicherstruktur, Definition Postsches Korrespondenz Problem (PCP), Unentscheidbarkeit des PCP, Anwendung des PCP auf Schnittproblem und Mehrdeutigkeitsproblem f"ur kontextfreie Sprachen.
• Automaten und formale Sprachen
  • Allgemeines zu Automaten und formale Sprachen, Berechenbarkeit, einige Beispiele.
  • Grundlagen: Alphabet, Wort, leeres Wort, Konkatenation, Monoid, freies Monoid, Kleenesche H"ulle.
  • Grammatiken: Definition Chomsky-Grammatik, Ableitungsrelation, erzeugte Sprache, Definition Grammatik-Typen (Unterscheidung von kontext-sensitiv und monoton), Sprachhierarchie (Inklusionsstruktur und "Aquivalenz von kontext-senstiv und monoton), Trennung der Klassen der Sprachhierarchie---Wortproblem und Ogdens Lemma, Spezialfall von Ogdens Lemma ist das $uvwxy$-Theorem, Beispiel zu Ogdens Lemma, Pumping Lemma f"ur regul"are Sprachen, Maschinenmodelle f"ur die Chomsky-Hiearchie und Determinismus-Nichtdeterminismus Problem, Abschlu\ss{}eigenschaften der Klassen der Chmosky-Hierarchie (Vereinigung, Konkatenation, Kleensche H"ulle, Reversal, Schnitt, Komplement, Schnitt mit regul"aren Mengen, Homomorphismen, inverse Homomorphismen, Quotient mit regul"aren Mengen).
  • Endliche Automaten: Definition deterministischer (DFA) und nichtdeterministischer (NFA) endlicher Automat, Potenzautomatenkonstruktion, Myhill-nerode "Aquivalenzrelation, Satz von Myhill-Nerode, "Aquivalenzrelation "uber Automaten, Beziehung der beiden "Aquivalenzrelationen, Minimalautomat, Eigenschaften des Minimalautomaten bzgl.\ der Myhill-Nerode "Aquivalenzrelation, Zustandexplosion bei Umwandlung NFA nach DFA, Minimierungsalgorithmus und Beispiel.
  • Alternative Darstellung regul"arer Mengen:
    • Syntaxdiagramme oder beschriftete Myhill-Graphen: Definition lokale Menge, Definition Myhill-Graph, Wegemengen, jede lokale Menge ist regul"are aber nicht umgekehrt, jede regul"are Menge ist homomorphes Bild einer lokalen Menge,
    • Regul"are Ausdrucke: Definition regul"arer Ausdruck, "Aquivalenz von regul"aren Ausdr"ucken und NFA's (Richtung NFA nach regul"aren Ausdruck mit Hilfe eines graphischen Verfahrens).
    • Erkennbarkeit: Definition von Erkennbarkeit, Beziehung zu endlichen Monoiden, Transitionsmonoid des DFA's, syntaktische Relation und Monoid, Erkennbarkeit und syntaktisches Monoid, Beziehung syntaktisches Monoid und Transitionsmonoid.
    • Rechnen mit regul"aren Ausdr"ucken und Gleichungssystem: Leerworteigenschaft, Axiomensystem nach Salomaa, Rechenregeln (Kongruenz, Symmetrie, Transitivit"at und Gleichungsaufl"osung), Gleichungssystem eines endlichen Automaten, Matrizendarstellung, Bestimmung der L"osung durch Iteration.
  • Endliche Automaten "uber unendlichen W"ortern: Grundlagen zu unendlichen W"ortern, Mengen, Definition $\omega$-regul"aren Mengen, Darstellung als endliche Vereinigung.
    • B"uchi Automaten (BA): Definition, periodische W"orter, B"uchi akzeptierbar gleich $\omega$-regul"ar, Verh"altnis Determinismus und Nichtdeterminismus, Pfeiloperation, Beispiele zur Pfeiloperation, DBA's und die Pfeiloperation, DBA Sprachen sind iechte Teilmenge der $\omega$-regul"aren Sprachen, Abschlu\ss{}eigenschaften von DBA Sprachen (nicht unter Komplementbildung, Abschlu\ss\ unter Schnitt und Vereinigung).
    • Muller Automaten (MA): Definition, (D)MA Sprachen sind $\omega$-regul"ar, Aschlu\ss{}eigenschaften von DMA Sprachen (Vereinigung, Schnitt, Komplementbildung), Darstellung von DMA Sprachen als endliche Vereinigung von Differenzen von DBA Sprachen.
    • Rabin Automaten (RA): Definition, "Aquivalenz von DRA Sprachen und DMA Sprachen, BA Sprachen sind auch DRA Sprachen, hierzu verallgemeinerte Potenzautomatenkonstruktion nach Safra, Speicherung der Mengen in B"aumen, Endlichkeit dieser B"aume, gro\ss{}es Beispiel, Beweisskizze f"ur die Korrektheit, Zustandsexplosion, BA Sprachen sind unter Komplementbildung abgeschlossen.
  • Abschlie\ss{}ende "Ubersicht.

Literatur: (in alphabetischer Reihenfolge)

• Berechenbarkeit
• Engeler und Läuchli, Berechnungstheorie für Informatiker, Teubner, 1992.
• Hopcroft und Ullman. Introduction to Automata Theory, Languages, and Computations, Addison-Wesley, 1979.
• Kfoury, Moll and Arbib. A Programming Approach to Computability, Springer, 1982.
• Schöning. Theoretische Informatik -- kurz gefasst, Spektrum, 2001.
• Automaten und Formale Sprachen
• Asteroth und Baier. Theoretische Informatik, Pearson, 2002.
• Harrison. Introduction to Formal Language Theory, Addison-Wesley, 1978.
• Hopcroft und Ullman. Introduction to Automata Theory, Languages, and Computations, Addison-Wesley, 1979.
• Perrin und Pin. Infinite Words -- Automata, Semigroups, Logic and Games, Elsevier, 2004.
• Schöning. Theoretische Informatik -- kurz gefasst, Spektrum, 2001.

Sprechstunde:
nach Vereinbarung