Course

FSA - Formal Languages and Automata Theory

PDF Course Catalog Deutsche Version: FSA

Version: 1 | Last Change: 03.09.2019 11:28 | Draft: 0 | Status: vom verantwortlichen Dozent freigegeben

Long name Formal Languages and Automata Theory
Approving CModule FSA_BaTIN
Responsible
Prof. Dr. Hans Nissen
Professor Fakultät IME
Level Bachelor
Semester in the year summer semester
Duration Semester
Hours in self-study 78
ECTS 5
Professors
Prof. Dr. Hans Nissen
Professor Fakultät IME
Requirements no requirements
Language German
Separate final exam Yes
Literature
Uwe Schöning: Theoretische Informatik - kurzgefasst, Spektrum Akademischer Verlag, 5. Auflage, 2008
Rolf Socher: Theoretische Grundlagen der Informatik Carl Hanser Verlag, 2007
Gottfried Vossen, Kurt-Ulrich Witt: Grundkurs Theoretische Informatik 4. Auflage, Vieweg Verlag, 2006
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie 3. Auflage, Pearson Studium, 2011
Final exam
Details
The written exam ensures that each student has individually achieved the goals of the Learning Outcomes,
through tasks of the following types:
Formalize and analyze systems from an abstract perspective,
formalize given formal languages,
Specify grammar for given language,
identify accepting machines for given languages,
transform a description of a formal language into another, equivalent descriptive form
prove or disprove that a language belongs to a particular language class.
Minimum standard
At least 50% of the total number of points.
Exam Type
The written exam ensures that each student has individually achieved the goals of the Learning Outcomes,
through tasks of the following types:
Formalize and analyze systems from an abstract perspective,
formalize given formal languages,
Specify grammar for given language,
identify accepting machines for given languages,
transform a description of a formal language into another, equivalent descriptive form
prove or disprove that a language belongs to a particular language class.

Learning goals
Knowledge
formal languages and Chomsky hierarchy
formalization of grammars
formalization of abstract machine models
finite automata
pushdown automata
turing machine
regular expressions
properties of formal languages
closure
decidability
Pumping Lemma
Skills
specify chomsky level of formal languages
specification of formal languages
develop grammr for given formal language
develop automata for given grammar
develop automata fpr given grammar
transform formal specifications
formale Beweise zu formalen Sprachen, Grammatiken und Automaten durchführen
formalize real world problems
develop abstract automata for real problems
Expenditure classroom teaching
Type Attendance (h/Wk.)
Lecture 2
Exercises (whole course) 0
Exercises (shared course) 2
Tutorial (voluntary) 0
Special literature
keine/none
Special requirements
keine
Accompanying material
electronic presentation slides for the lecture
electronic worksheets for exercises
Separate exam
none

Impressum
Datenschutzhinweis
Haftungshinweis
Bei Fehlern, bitte Mitteilung an die
Webredaktion der Fakultät IME

© 2022 Technische Hochschule Köln