Navigation
Index
weiter
|
Theoretische Grundlagen der Informatik 1.0 Dokumentation
»
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
¶
Endliche Automaten
Grammatiken
Berechenbarkeit
Entscheidbarkeit
Komplexität
Inhalt
Theoretische Grundlagen der Informatik
Vorlesungsverzeichnis:
Definitionsverzeichnis:
Gliederung der Vorlesungen
Nächstes Thema
Vorlesungen
Schnellsuche
Geben Sie Suchbegriffe oder einen Modul-, Klassen- oder Funktionsnamen ein.
Navigation
Index
weiter
|
Theoretische Grundlagen der Informatik 1.0 Dokumentation
»