Institut für Abwasserwirtschaft und Gewässerschutz

Menu

Lehrveranstaltungen am Institut

Automata Theory and Formal Languages (VL)
Untertitel:This course is part of the module: Automata Theory and Formal Languages
DozentIn:Prof. Dr. Matthias Mnich, M. Sc., Dr. Ebrahim Ghorbani
Veranstaltungstyp:Vorlesung (Lehre)
Beschreibung:
  1. Propositional logic, Boolean algebra, propositional resolution, SAT-2KNF
  2. Predicate logic, unification, predicate logic resolution
  3. Temporal Logics (LTL, CTL)
  4. Deterministic finite automata, definition and construction
  5. Regular languages, closure properties, word problem, string matching
  6. Nondeterministic automata: 
    Rabin-Scott transformation of nondeterministic into deterministic automata
  7. Epsilon automata, minimization of automata,
    elimination of e-edges, uniqueness of the minimal automaton (modulo renaming of states)
  8. Myhill-Nerode Theorem: 
    Correctness of the minimization procedure, equivalence classes of strings induced by automata
  9. Pumping Lemma for regular languages:
    provision of a tool which, in some cases, can be used to show that a finite automaton principally cannot be expressive enough to solve a word problem for some given language
  10. Regular expressions vs. finite automata:
    Equivalence of formalisms, systematic transformation of representations, reductions
  11. Pushdown automata and context-free grammars:
    Definition of pushdown automata, definition of context-free grammars, derivations, parse trees, ambiguities, pumping lemma for context-free grammars, transformation of formalisms (from pushdown automata to context-free grammars and back)
  12. Chomsky normal form
  13. CYK algorithm for deciding the word problem for context-free grammrs
  14. Deterministic pushdown automata
  15. Deterministic vs. nondeterministic pushdown automata:
    Application for parsing, LL(k) or LR(k) grammars and parsers vs. deterministic pushdown automata, compiler compiler
  16. Regular grammars
  17. Outlook: Turing machines and linear bounded automata vs general and context-sensitive grammars
  18. Chomsky hierarchy
  19. Mealy- and Moore automata:
    Automata with output (w/o accepting states), infinite state sequences, automata networks
  20. Omega automata: Automata for infinite input words, Büchi automata, representation of state transition systems, verification w.r.t. temporal logic specifications (in particular LTL)
  21. LTL safety conditions and model checking with Büchi automata, relationships between automata and logic
  22. Fixed points, propositional mu-calculus
  23. Characterization of regular languages by monadic second-order logic (MSO)
Ort:nicht angegeben
Semester:SoSe 24
Zeiten:Di. 13:15 - 14:45 (zweiwöchentlich, ab 16.04.2024) - Lecture Automata Theory and Formal Languages, Mi. 08:00 - 09:30 (wöchentlich) - Lecture Automata Theory and Formal Languages
Erster Termin:Mittwoch, 03.04.2024 08:00 - 09:30
Veranstaltungsnummer:lv332_s24
ECTS-Kreditpunkte:4
Weitere Informationen:
Heimatinstitut: Institut für Algorithmen und Komplexität (E-11)
In Stud.IP angemeldete Teilnehmer: 394
Anzahl der Postings im Stud.IP-Forum: 36
Anzahl der Dokumente im Stud.IP-Downloadbereich: 21
Anmelden in Stud.IP