Homepage
N a v i g a t i o n
  Start & News
  Studies
 
  Seminars (4)
  Other Texts (1)
  Computers
 
  XML, ... (2)
  About me (1)
A protocol of the lecture "Theoretische Informatik 2".

This is a protocol of the lecture "Theoretische Informatik 2" held by Prof. Dr. Wotschke. The topics of it include an introduction to automata theory, DFA, NFA, context free grammars, ...

The paper is written in german. Other formats, including Word, are available from www.stormzone.de, the university site by Fabian Wleklinski and Martin Klossek.

The text is the fruit of a common effort achieved by Fabian Wleklinski, Martin Klossek, Frank Bergmann and me.

Table of Contents

  1   Inhaltsverzeichnis
  2   Vorlesung vom 11. April 2000
 
  2.1   Mengen, Mengenoperationen und Relationen
 
  2.1.1   Funktion, Umkehrfunktionen und Abbildungen
  2.1.2   Injektivität, Surjektivität und Bijektivität
  2.1.3   Relationen
  2.1.4   Äquivalenzrelationen
  2.1.5   Äquivalenzklassen
  2.1.6   Kollektionen
  2.1.7   Partitionen
  2.2   Algebraische Strukturen
 
  2.2.1   Die algebraische Struktur
  2.2.2   Die Halbgruppe
  2.2.3   Das Monoid
  2.2.4   Das freie Erzeugendensystem, das freie Monoid
  2.2.5   Der Homomorphismus
  2.2.6   Der Isomorphismus
  2.2.7   Abzählbarkeit
  2.2.8   Konkatenation
  2.3   Sprachen
  2.4   Grammatiken
  2.5   Klassifizierung von Sprachen
  3   Vorlesung vom 13. April 2000
 
  3.1   Abzählbarkeit von Mengen, Diagonalisierung
 
  3.1.1   Mächtigkeit von Mengen
  3.1.2   one-to-one-Mapping
  3.1.3   Abzählbarkeit rationaler Zahlen
  3.1.4   Überabzählbarkeit reeller Zahlen
  3.2   Transitive und reflexive Hülle
 
  3.2.1   Definitionen
  3.2.2   Beispiele
  3.3   Endliche Automaten (FSM, DFA)
 
  3.3.1   Veranschaulichung und Darstellung
  3.3.2   Definition
  3.3.3   Erweiterung
  3.3.4   Beispiel eines endlichen Automaten
  4   Vorlesung vom 18. April 2000
 
  4.1   Beweis eines DFA (deterministischer endlicher Automat)
  4.2   Vorgehensweise
 
  4.2.1   Beweis des Beispiels
  4.2.2   Induktionsbehauptungen
  4.2.3   Induktionsverankerung
  4.2.4   Induktionsschritt (n -> n+1)
  4.2.5   Beweis der Sprachäquivalenz
  4.3   Nichtdeterministischer endlicher Automat (NFA)
 
  4.3.1   Formale Definition
  4.3.2   Erweiterung von delta des NFA
  4.3.3   Die vom NFA erkannte Sprache
  4.3.4   Beispiel eines NFA
  5   Vorlesung vom 20. April 2000
 
  5.1   Über die Äquivalenz von NFA und DFA
 
  5.1.1   Theorem
  5.1.2   Beweis des Buches
  5.1.3   Beweis der Vorlesung
  5.1.4   Beispiel 1 (Konstruktion eines DFA aus einem NFA)
  5.1.5   Beispiel 2 (Konstruktion eines DFA aus einem NFA)
  5.2   Satz über die Minimierung von Zuständen
  6   Vorlesung vom 25. April 2000
 
  6.1   Nachtrag zur vorherigen Vorlesung
  6.2   Mathematischer Hintergrund
 
  6.2.1   Erweiterung des Begriffs Äquivalenzrelation
  6.2.2   Rechts-Invarianz
  6.2.3   Links-Invarianz
  6.2.4   Konqruenzrelation
  6.2.5   Quotientenmenge
  6.2.6   Quotientenmonoid
  6.3   Reguläre Ausdrücke
 
  6.3.1   Kleenesche Hülle
  6.3.2   Reguläre Ausdrücke
  6.3.3   Reguläre Ausdrücke vs. endliche Automaten
  6.4   Nerode Automat
 
  6.4.1   Definition
  6.4.2   Repräsentantenunabhängigkeit
  6.4.3   Regularität
  6.4.4   Minimalität
  6.4.5   Eindeutigkeit
  7   Vorlesung vom 27.April 2000
 
  7.1   Nerode Automat
 
  7.1.1   Homomorphismus und Isomorphismus
  7.1.2   Minimalität und Eindeutigkeit des Nerode Automaten
  7.2   Minimierung von endlichen Automaten
 
  7.2.1   Rekursion der k Relationen
  7.2.2   Verfeinerung von Äquivalenzrelationen
  7.2.3   Anwendnung auf k Relationen zur Zustandsreduktion
  8   Vorlesung vom 2. Mai 2000
 
  8.1   Minimierung mittels Nerode-Automaten
 
  8.1.1   Satz über die Gleichwertigkeit von Relationen
  8.1.2   Konstruktion eines minimalen Automaten
  8.2   "Praktische" Minimierung von deterministischen endlichen Automaten
 
  8.2.1   Der "Algorithmus"
  8.2.2   Beispiel
  9   Vorlesung vom 4. Mai 2000 (Abschlusseigenschaften)
 
  9.1   Motivation
  9.2   Sammlung von Abschlusseigenschaften
 
  9.2.1   Beweise Vereinigung, Konkatenation, Kleenesche Hülle
  9.2.2   Komplementbildung
  9.2.3   Schnitt
  9.2.4   Substitution
  9.2.5   Homomorphismus
  9.2.6   Inverser Homomorphismus
  10   Vorlesung vom 9. Mai 2000
 
  10.1   Beispiele zur Nutzung der Abschlusseigenschaften
 
  10.1.1   Einleitung
  10.1.2   Beispiel 1
  10.1.3   Beispiel 2
  10.1.4   Beispiel 3
  10.1.5   Beispiel 4
  10.1.6   Beispiel 5
  10.2   Automaten mit Epsilon-Bewegungen
 
  10.2.1   Einleitung
  10.2.2   Epsilon-Hülle
  10.2.3   Formale Unterschiede zum gewöhnlichen NFA
  10.2.4   Äquivalenz vom NFA mit und ohne Epsilon-Bewegungen
  11   Vorlesung vom 11. Mai 2000
 
  11.1   Äquivalenz von endlichen Automaten und regulären Ausdrücken
 
  11.1.1   Von regulären Ausdrücken zu endlichen Automaten
  11.1.2   Vereinigung zweier regulärer Ausdrücke als NFAs
  11.1.3   Schnitt zweier regulärer Ausdrücke als NFAs
  11.1.4   Kleenesche Hülle eines regulären Ausdrucks als NFA
  11.1.5   Beispiel: Konstruktion eines NFA mit Epsilon-Übergängen für einen regulären Ausdruck
  11.1.6   Vom endlichen Automaten zu regulären Ausdrücken
  12   Vorlesung vom 16. Mai 2000
 
  12.1   Wiederholung der letzten Vorlesung
 
  12.1.1   Abschlusseigenschaften
  12.2   Beispiele
  12.3   Endliche 2-Wege Automaten
  13   Vorlesung vom 23. Mai 2000
 
  13.1   Grammatiken
 
  13.1.1   Beispiele zu Grammatiken
  13.2   Die Äquivalenz von regulären Grammatiken und endlichen Automaten
  13.3   Die Sprache a^nb^n
  13.4   Das Pumping-Lemma
  13.5   Entscheidbarkeit
 
  13.5.1   Prädikate
  13.5.2   Definition der Entscheidbarkeit
  13.5.3   Beispiel: Entscheidbarkeit der leeren Sprache
  13.5.4   Beispiel: Entscheidbarkeit der unendlichen Sprache
  13.5.5   Beispiel: Entscheidbarkeit der endlichen Sprache
  13.5.6   Beispiel: Entscheidbarkeit der Schnittmenge
  13.5.7   Beispiel: Entscheidbarkeit der Teilmenge
  13.5.8   Beispiel: Entscheidbarkeit der Äquivalenz
  13.6   Kontextfreie Grammatiken
 
  13.6.1   Beispiel zur Kontextfreien Grammatik
  14   Vorlesung vom 25. Mai 2000
 
  14.1   Ableitungen von Wörtern in kontextfreien Grammatiken
 
  14.1.1   Ableitungen
  14.1.2   Ableitungsbäume
  14.1.3   Beispiel für einen Ableitungsbaum
  14.1.4   Die Beziehung zwischen Ableitungsbäumen und Grammatiken
  14.1.5   Linksableitung
  14.1.6   Eindeutigkeit
  14.2   Vereinfachung kontextfreier Grammatiken
 
  14.2.1   Epsilon-Produktionen
  15   Vorlesung vom 30. Mai 2000
 
  15.1   Reduktion von Grammatiken
 
  15.1.1   Definition Brauchbarkeit von Nichtterminalsymbolen
  15.1.2   Das Problem der Ausführung der beiden Schritte
  15.1.3   Zyklische Produktionen
  15.1.4   Zusammenfassung
  16   Vorlesung vom 6. Juni 2000
 
  16.1   Chomsky-Normalform
  16.2   Pushdown-Automaten
 
  16.2.1   Einführung
  16.2.2   Formale Definition, Konfiguration, Akzeptierung
  16.2.3   Äquivalenz von PDA und kontextfreier Grammatik
  17   Vorlesung vom 8. Juni 2000
 
  17.1   Für jede CFL existiert ein PDA
 
  17.1.1   Fortsetzung des Beweises
  18   Vorlesung vom 15. Juni 2000
 
  18.1   Greibach Normalform (GNF)
 
  18.1.1   Vorbemerkung
  18.1.2   Umwandlung einer linksrekursiven in eine rechtrekursive Produktion
  18.1.3   Kontextfreie Grammatiken in GNF
  18.1.4   Beispiel 1
  18.1.5   Beispiel 2
  19   Vorlesung vom 20. Juni 2000
 
  19.1   Ogden's Lemma
 
  19.1.1   Beispiele für Kontextfreiheit und Nichtkontextfreiheit
  20   Vorlesung vom 27. Juni 2000
 
  20.1   Deterministische PDA
 
  20.1.1   Beispiele
  20.1.2   kfS und dkfS
  20.2   Turingmaschinen und Entscheidbarkeit
 
  20.2.1   Problem, Algorithmus, Entscheidbarkeit
  20.2.2   Modelle für Algorithmen
  20.2.3   Churchsche These
  20.2.4   Turingmaschine
  20.2.5   Universelle Turingmaschine
  20.2.6   Arbeitsweise der universellen Turingmaschine
  20.2.7   Halteproblem für Turingmaschinen
  20.2.8   Rekursive Mengen
  21   Abbildungsverzeichnis
  22   Index

Further information & ressources
Protocol

For displaying Postscript-Files, I recommend Ghostview.

up