Regular languages, finite automata, transition graphs, Kleene's theorem. Finite automata with output. Context-free languages, derivation trees, normal form grammars, pumping lemma, pushdown automata, determinism. Decidability. Recursively enumerable languages, Turing machines, the halting problem. Prerequisites: CSI2101 or MAT2143.
Professor
-
Dr. Amy Felty
SITE 5-068
afelty@uottawa.ca
Textbook
- Introduction to Computer Theory, Daniel Cohen, Wiley, 2nd edition.
Course Outline
Details will be filled in as the term progresses.
| Topic | Reading |
|---|---|
| Introduction, Languages, Recursive Definitions | Chapters 1, 2, 3 |
| Regular Expressions | Chapter 4 |
| Finite Automata, Transition Graphs | Chapters 5, 6 |
| Kleene's Theorem, Nondeterministic Finite Automata | Chapter 7 |
| Finite Automata with Output, Regular Languages | Chapters 8, 9 |
| Nonregular Languages, Decidability | Chapters 10 (pages 187-196), 11 |
| Context-Free Grammars, Grammatical Format | Chapters 12, 13 |
| Pushdown Automata, Context-Free Grammars = Pushdown Automata | Chapters 14, 15 (pages 318-327) |
| Non-Context-Free Languages, Context-Free Languages | Chapters 16, 17 |
| Decidability, Parsing, Turing Machines | Chapters 18 (pages 402-410 and 415-423), 19 |
| Recursively Enumerable Languages | Chapter 23 |
