Vorlesung: Lecture: Automata Theory and Formal Languages - Details

Vorlesung: Lecture: Automata Theory and Formal Languages - Details

Nachrichtenbox schließen
Sie sind nicht in Stud.IP angemeldet.

Allgemeine Informationen

Veranstaltungsname Vorlesung: Lecture: Automata Theory and Formal Languages
Untertitel Module: Automata Theory and Formal Languages
Veranstaltungsnummer 36429_S20
Semester SoSe 20
Aktuelle Anzahl der Teilnehmenden 211
Heimat-Einrichtung E-5 Biomedizinische Bildgebung
Veranstaltungstyp Vorlesung in der Kategorie Lehre
Erster Termin Freitag, 24.04.2020 09:45 - 11:15, Ort: (https://zoom.us/s/92823425892 Meeting ID: 928 2342 5892 Password: Turing)
Voraussetzungen Participating students should be able to
- specify algorithms for simple data structures (such as, e.g., arrays) to solve computational problems 
- apply propositional logic and predicate logic for specifying and understanding mathematical proofs
- apply the knowledge and skills taught in the module Discrete Algebraic Structures
Leistungsnachweis Written exam
ECTS-Punkte 4

Räume und Zeiten

(https://zoom.us/s/93272881696 Meeting ID: 932 7288 1696 Password: Turing)
Donnerstag: 09:45 - 11:15, wöchentlich (11x)
Donnerstag: 11:30 - 13:00, wöchentlich (11x)
(https://zoom.us/j/94977477769 Meeting ID: 949 7747 7769 Password: Turing)
Donnerstag: 09:45 - 11:15, wöchentlich (11x)
Donnerstag: 11:30 - 13:00, wöchentlich (11x)
(https://zoom.us/s/92823425892 Meeting ID: 928 2342 5892 Password: Turing)
Freitag: 09:45 - 11:15, wöchentlich (11x)

Kommentar/Beschreibung

<p>- Propositional logic, Boolean algebra, propositional resolution, SAT-2KNF<br />- Predicate logic, unification, predicate logic resolution<br />- Temporal Logics (LTL, CTL)<br />- Deterministic finite automata, definition and construction<br />- Regular languages, closure properties, word problem, string matching<br /><br /> - Nondeterministic automata: <br />Rabin-Scott transformation of nondeterministic into deterministic automata<br /> - Epsilon automata, minimization of automata,<br />elimination of e-edges, uniqueness of the minimal automaton (modulo renaming of states)<br /> - Myhill-Nerode Theorem: <br />Correctness of the minimization procedure, equivalence classes of strings induced by automata<br /><br /> - Pumping Lemma for regular languages:<br />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<br /><br /> - Regular expressions vs. finite automata:<br />Equivalence of formalisms, systematic transformation of representations, reductions<br /><br /> - Pushdown automata and context-free grammars:<br />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)<br />- Chomsky normal form<br />- CYK algorithm for deciding the word problem for context-free grammrs<br />- Deterministic pushdown automata<br /><br /> - Deterministic vs. nondeterministic pushdown automata:<br />Application for parsing, LL(k) or LR(k) grammars and parsers vs. deterministic pushdown automata, compiler compiler<br />- Regular grammars<br />- Outlook: Turing machines and linear bounded automata vs general and context-sensitive grammars<br />- Chomsky hierarchy<br /><br /> - Mealy- and Moore automata:<br />Automata with output (w/o accepting states), infinite state sequences, automata networks<br /> - 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)<br /><br /> - LTL safety conditions and model checking with Büchi automata, relationships between automata and logic<br />- Fixed points, propositional mu-calculus<br /><br /> - Characterization of regular languages by monadic second-order logic (MSO)</p><p>- Logik für Informatiker Uwe Schöning, Spektrum, 5. Aufl.<br /><br /> - Logik für Informatiker Martin Kreuzer, Stefan Kühling, Pearson Studium, 2006<br />- Grundkurs Theoretische Informatik, Gottfried Vossen, Kurt-Ulrich Witt, Vieweg-Verlag, 2010.<br />- Principles of Model Checking, Christel Baier, Joost-Pieter Katoen, The MIT Press, 2007<br /></p>

Anmelderegeln

Diese Veranstaltung gehört zum Anmeldeset "Anmeldung gesperrt (global)".
Erzeugt durch Migration 128 13:45:31 03.09.2014
Folgende Regeln gelten für die Anmeldung:
  • Die Anmeldung ist gesperrt.