Go to menu

Information System of Masaryk University

Course Information

česky | in English

I005 Formal Languages and Automata I

Faculty of Informatics
Spring 2000

Extent and Intensity

3/2. 5 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Alternate Types of Completion: k (colloquium), z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer), prof. RNDr. Ivana Černá, CSc. (deputy)
prof. RNDr. Ivana Černá, CSc. (seminar tutor)

Supervisor

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science - Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.

Prerequisites

I000 Induction and Recursion && ( M005 Foundations of mathematics || M036 Introduction to Discrete Mathematics )
I000 Induction and Recursion and M005 Foundations of mathematics required

Course Enrollment Limitations

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

Fields of study the course is directly associated with

Informatics (programme FI, B-IN)
Information Technology (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)

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.

Literature

I.Černá, M.Křetínský, A.Kučera: FJA I, interní materiál FI MU
GRUSKA, Jozef. Foundations of computing. London: International Thompson Computer Press, 1997. xv, 716 s. ISBN 1-85032-243-0. info
HOPCROFT, John E. and Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Reading: Addison-Wesley Publishing Company, 1979. 418 s., ob. ISBN 0-201-02988-. info
CHYTIL, Michal. Automaty a gramatiky. 1. vyd. Praha: SNTL - Nakladatelství technické literatury, 1984. 331 s. info
KOZEN, Dexter C. Automata and computability. New York: Springer, 1997. xiii, 400. ISBN 0-387-94907-0. info

Assessment methods (in Czech)