| 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 |
Context-Free (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, Semi-infinite tape,
off-line, 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 |
|