| INFB Formale Sprachen / Automatentheorie | SG | INF | |
|---|---|---|---|
| Dozent : |
Prof. Dr. Matthias Homeister
eMail
|
Semester | 2 |
| Einordnung : | Bachelor Informatik | SWS | 4 |
| Sprache : | Deutsch/Englisch | Art | VÜ |
| Prüfungsart : | PL | Credits | 5 |
| Prüfungsform : | Klausur 120 min | ||
| Voraussetzungen : |
Informatik und Logik
Mathematik I |
||
| Querverweise : | |||
| Vorkenntnisse : | Mathematik I Programmierung I | ||
| Hilfsmittel und Besonderheiten : | Studien- und Prüfungsleistungen: Semesterbegleitende Leistungen können in die Bewertung einbezogen werden. | ||
| Lehrziele : | Die Studierenden sind mit der Denkweise der theoretischen Informatik vertraut (Abstraktion, Präzision, logisches Schlussfolgern und Argumentieren). Sie können Sachverhalte in unterschiedlichen Darstellungen (grafische Darstellung / Tabellendarstellung von Automaten) formulieren und von einer Darstellung in die andere übersetzen. Sie sind in der Lage, endl. Automaten zu konstruieren, zu analysieren und einzusetzen. Sie sind in der Lage, reguläre Ausdrücke zu konstruieren, zu analysieren und einzusetzen. Sie sind in der Lage, Transformationen zwischen Automaten durchzuführen (Minimierung, NEA zu DEA, reg. Ausdruck zu NEA) und zu beweisen, ob eine Sprache regulär ist oder nicht. Sie sind in der Lage, kontextfreie Grammatiken zu konstruieren, zu analysieren und einzusetzen. Sie können die Chomsky-Normalform erzeugen und verstehen den CYK-Algorithmus. Sie können feststellen, ob eine Sprache kontextfrei ist oder nicht. Sie verstehen den Zusammenhang von Automaten und Grammatiken, kennen kontextsensitive Grammatiken und können formale Sprachen in die Chomsky-Hierarchie einordnen. Sie verstehen die Bedeutung von formalen Sprachen, Automaten und Grammatiken im Kontext des Compilerbaus. | ||
| Lehrinhalte : | Reguläre Sprachen: deterministische und nichtdeterministische endliche Automaten, Transformationen (Minimierung, NEA in DEA, reg. Ausdruck in NEA), reguläre Ausdrücke, lexikalische Analyse, Pumpinglemma. | ||
| Literatur : | Sipser: Introduction to the Theory of Computation, Cengage Learning, 3rd edition, 2013 Socher R.: Theoretische Grundlagen der Informatik. 3. Aufl. München: Hanser Verlag 2008 Wagenknecht, Hielscher: Formale Sprachen, abstrakte Automaten und Compiler. 2. Auflage, Wiesbaden, Springer-Vieweg, 2015 Vossen G., Witt K.-U.: Grundkurs theoretische Informatik. 6. Aufl. Wiesbaden: Springer-Vieweg, 2016 Böckenhauer, Hromkovic.: Formale Sprachen. Wiesbaden, Springer-Vieweg, 2012 | ||