Intended learning outcomes *
The overall aim of the course is to provide students with a profound understanding of computation and effective computability through the abstract notion of automata and the language classes they recognize.
Along with this, the students will get acquainted with the important notions of state, nondeterminism and minimization.
After the course, the successful student will be able to perform the following constructions:
1. Determinize and minimize automata;
2. Construct an automaton for a given regular expression;
3. Construct a pushdown automaton for a given context-free language;
4. Construct a Turing machine deciding a given problem,
5. Prove whether a language is or isn't regular or context-free by using the Pumping Lemma;
6. Prove that a given context-free grammar generates a given context-free language;
7. Prove undecidability of a given problem by reducing from a known undecidable problem,
8. Apply the fundamental theorems of the course: Myhill-Nerode, Chomsky-Schützenberger, and Rice's theorems.
For passing the course, a student has to be proficient at problems of type 1-5; for the highest grade he/she has to be equally proficient at the remaining types of problems.