Languages and Automata
- Department of Mathematics
Various types of generative grammars and corresponding automata. Closure and algorithmic problems.
- 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:
Lewis H.R., Papadimitriou C.H.: Elements of the Theory of Computation. PrenticeHall, Englewood Cliffs, New Jersey, 1981.
Salomaa A.: Formal Languages. Academic Press, New York,1973.
- Further information:
- No time-table has been prepared for this course
- The course is a part of the following study plans: