Languages and Automata

The course is not on the list Without time-table

Code	Completion	Credits	Range	Language
01JAA	ZK	2	2+0	Czech

Course guarantor:

Lecturer:

Tutor:

Supervisor:

Department of Mathematics

Synopsis:

Various types of generative grammars and corresponding automata. Closure and algorithmic problems.

Requirements:

Syllabus of lectures:

Generative grammars, Chomsky classification, type 0 languages and Turing machines, context-sensitive languages and linear bounded automata, context-free languages and pushdown storage automata, type 3 languages, finite automata, and regular languages, closure properties and algorithmic properties.

Syllabus of tutorials:

Study Objective:

To acquaint the students with classical results of the theory of formal languages, generative grammars, and automata-acceptors.

Study materials:

Povinná

Lewis H.R., Papadimitriou C.H.: Elements of the Theory of Computation. PrenticeHall, Englewood Cliffs, New Jersey, 1981.

Doporučená

Salomaa A.: Formal Languages. Academic Press, New York,1973.

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans: