Module Handbook

  • Dynamischer Default-Fachbereich geändert auf INF

Module INF-02-04-M-2

Formal Languages and Computability (M, 6.0 LP)

Module Identification

Module Number Module Name CP (Effort)
INF-02-04-M-2 Formal Languages and Computability 6.0 CP (180 h)

Basedata

CP, Effort 6.0 CP = 180 h
Position of the semester 1 Sem. in SuSe
Level [2] Bachelor (Fundamentals)
Language [DE] German
Module Manager
Zweig, Katharina, Prof. Dr. (PROF | DEPT: INF)
Lecturers
Zweig, Katharina, Prof. Dr. (PROF | DEPT: INF)
Area of study [INF-PFL] Mandatory Modules
Reference course of study [INF-82.79-SG] B.Sc. Computer Science
Livecycle-State [NORM] Active

Courses

Type/SWS Course Number Title Choice in
Module-Part 		Presence-Time /
Self-Study 		SL SL is
required for exa. 		PL CP Sem.
3V+2U INF-02-04-K-2
Formal Languages and Computability
P 70 h 110 h
U-Schein
ja PL1 6.0 SuSe
  • 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.


Contents

From [INF-02-04-K-2] Formal Languages and Computability:
  • 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

Competencies / intended learning achievements

The students
  • 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.

Literature

From [INF-02-04-K-2] Formal Languages and Computability:
  • 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 (informal)

Modules:

Requirements for attendance (formal)

None

References to Module / Module Number [INF-02-04-M-2]

Course of Study Section Choice/Obligation
[INF-82.79-SG] B.Sc. Computer Science Theoretical Foundations [P] Compulsory
[MAT-82.105-SG] B.Sc. Mathematics Subsidiary Subject (Minor) [WP] Compulsory Elective