- Definitions of language and different forms of representation of languages: Automata and machine models
- Hierarchy of the languages generated/recognized by them and their power
- Pumping lemmas
- Computability models: simulation as a principle of comparison between computability models. The thesis of Church-Turing.
- Holding problem
- Functional programming languages (primitive and partially recursive functions)
- Diagonalization technique, structural induction and reduction technique
Formal Languages and Computability (M, 6.0 LP)
|Module Number||Module Name||CP (Effort)|
|INF-02-04-M-2||Formal Languages and Computability||6.0 CP (180 h)|
|CP, Effort||6.0 CP = 180 h|
|Position of the semester||1 Sem. in SuSe|
|Level|| Bachelor (Fundamentals)|
|Area of study||[INF-PFL] Mandatory Modules|
|Reference course of study||[INF-82.79-SG] B.Sc. Computer Science|
|Type/SWS||Course Number||Title||Choice in |
|SL||SL is |
required for exa.
Formal Languages and Computability
|P||70 h||110 h||
- About [INF-02-04-K-2]: Title: "Formal Languages and Computability"; Presence-Time: 70 h; Self-Study: 110 h
- About [INF-02-04-K-2]:
The study achievement "[U-Schein] proof of successful participation in the exercise classes (ungraded)" must be obtained.
- It is a prerequisite for the examination for PL1.
Examination achievement PL1
- Form of examination: written exam (Klausur) (90-120 Min.)
- Examination Frequency: each summer semester
- Examination number: 60204 ("Formal Languages and Computability")
Evaluation of grades
The grade of the module examination is also the module grade.
Competencies / intended learning achievements
- have an understanding of basic questions of computer science,
- can formalize intuitive statements and analyze the models quantitatively and qualitatively,
- know the classification of formal languages,
- can apply mathematical principles and are proficient in formalisation methods,
- understand the difference of Turing machines as computing machines and recognizers of languages,
- have an understanding of formalizations of predictability and their implications: modelling and analysis techniques.
- Sperschneider, Hammer: Theoretische Informatik — Eine problemorientierte Einführung, Springer, 1996.
- Hopcroft, Motwani, Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Addison Wesley, Pearson Studium, 2002.
Requirements for attendance of the module (informal)
- [INF-02-01-M-2] Foundations of Programming (M, 10.0 LP)
- [MAT-02-11-M-1] Mathematics for Computer Science Students: Algebraic Structures (M, 8.0 LP)