Languages, Automata and Grammars

Course guarantor:

Lecturer:

Tutor:

Supervisor:

Department of Mathematics

Synopsis:

Finite automata. Nerod theorem and its applications. Nondeterministic

automata. Regular expressions nad Kleene theorem. Grammars and their

classification. Cotnext-free grammars. Chomsky hierarchy. CYK

algorithm for context-free grammars. Turing machines, decision

problem. Algorithmically nonsolvable problems.

Requirements:

Syllabus of lectures:

Syllabus of tutorials:

Study Objective:

Study materials:

1. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 2001.

Note:

Further information:

http://math.feld.cvut.cz/demlova/teaching/tja.htm

No time-table has been prepared for this course

The course is a part of the following study plans:

• Doctoral studies, daily studies (compulsory elective course)
• Doctoral studies, combined studies (compulsory elective course)
• Doctoral studies, structured daily studies (compulsory elective course)
• Doctoral studies, structured combined studies (compulsory elective course)