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