Languages, Automata and Grammars

Lecturer:

Marie Demlová

Tutor:

Marie Demlová

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:

Time-table for winter semester 2011/2012:

Time-table is not available yet

Time-table for summer semester 2011/2012:

Time-table is not available yet

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)