Lecture 
Topic 
Description 
1 
1.1 
Mathematical preliminaries 
2 
1.2, 2.1, 2.2, 2.3 
Basic concepts of languages, grammars and
automata  DFAs  NDFAs and equivalence 
3 
3.1, 3.2, 3.3 
Regulars expressions, regular grammars 
4 
4.1, 4.2, 4.3 
Basic properties of regular languages 
5 
5.1, 5.2, 5.3 
ContextFree (CTF) languages. Parsing and
Ambiguity. Programming languages 
6 
6.1, 6.2, 7.1 
Simplification of CTF grammars. Normal forms. 
7 
7.2, 7.3, 7.4 
Pushdown automata (PA). Nondeterministic &
deterministic PA. PA and CTF languages. 

Midterm Examination 
8 
8.1, 8.2 
Discuss exam. Properties of CTF languages.
Pumping lemmas. Properties. 
9 
9.1, 9.2, 9.3 
Turing Machines (TM). Standard TMs, Turing
Thesis. 
10 
10.1, 10.2, 10.4, 10.5 
Models of TMs (option stay, Semiinfinite tape,
offline, Multitape, Multidimensional, Nondeterministic, universal).
Linear bounded Automata. 
11 
11.1, 11.2, 11.3, 11.4 
Hierarchy of formal languages and Automata.
Recursive and Recursively Enumerable Languages. 
12 
12.1, 12.2, 13.1 
Limits of Algorithmic Computation. Problems that
cannot be solved by TMs. Undecidable Problems for Recursively Enumerable
Languages. Other Models of computation 

Final Examination 
