FI:I005 Formal Languages and Automata - Course Information

I005 Formal Languages and Automata I

Extent and Intensity

3/2. 5 credit(s). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)

Guaranteed by

Contact Person: prof. RNDr. Mojmír Křetínský, CSc.

Prerequisites

Recommended I000 Induction and Recursion and M005 Foundations of mathematics

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.

fields of study / plans the course is directly associated with

• Informatics (programme FI, B-IN)
• Informatics (programme FI, M-IN)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-IN)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-SS)
• Information Technology (programme FI, B-IN)

Syllabus

• Languages and grammars. Chomsky hierarchy.
• Finite automata and regular grammars.
• Properties of regular languages.
• Context-free grammars and pushdown automata.
• Properties of context-free languages.
• Deterministic pushdown automata.
• Turing machines. Computable languages and functions.
• Undecidability, (semi)decidability. Halting problem for TM.
• Post's correspondence problem. Undecidable CFL problems.

Language of instruction

Czech

• Enrolment Statistics (Spring 1998, recent)
  
• Permalink: https://is.muni.cz/course/fi/spring1998/I005