Theoretische Grundlagen der Informatik

Vorlesungsverzeichnis:

• Vorlesungen
  • 1. Vorlesung
    • Bedingungen zur Klausurzulassung
    • Organisation
    • Einführende Definitionen
    • Durchschnittt zweier Sprachen
  • 2. Vorlesung
    • Lemma: \(L(a_1 X a_2) = L(a_1) \cap L(a_2)\)
    • Satz: Zu jedem NEA a mit Worttransitionen gibt es einen äquivalenten NEA a’.
    • Verfahren zur Entscheidung ob \(\varepsilon\)-NEA \(a: p \rightarrow q\) mit Pfad \(\Pi\)
    • Wie berechnet man \(c_{ij}^{(r)}\)?
  • 3. Vorlesung
    • Satz: Potenzmengenkonstruktion
    • Identifizierung äquivalenter Zustände
  • 4. Vorlesung
    • Allgemein zum Bestimmen von äuqivalenten Zuständen
    • Satz von Nerode
  • 5. und 6. Vorlesung
    • Angabe von nicht-regulären Sprachen
    • Pumping-Lemma
    • Satz von Kleene
    • Ziel: Elegantes Verfahren für die Konstruktion von regulären Ausdrücken
    • Satz: Das zum NEA gehörige Gleichungssystem ist eindeutig lösbar

Definitionsverzeichnis:

• Definitionen
  • Bezeichnungen
  • Transitionssysteme, endl. Automaten
  • Produktautomat
  • NEA mit Worttransitionen
  • Deterministisch endlicher Automat (DEA)
  • Fortsetzung
  • \(\delta^*(p,w) = q \Longleftrightarrow a: p \rightarrow^w q\)
  • Regulär
  • Lemma: Ist \(L \subset \varSigma^*\) von DEA erkennbar, so auch \(\varSigma \backslash L\)
  • Beschränkung auf erreichbare Zuständen
  • Äquivalenzklassen
  • Reduzierter DEA

Gliederung der Vorlesungen

1. Endliche Automaten
2. Grammatiken
3. Berechenbarkeit
4. Entscheidbarkeit
5. Komplexität