Winter 2022

(3 hours of lecture per week, 3 credits)

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.

ProfessorDr. Amy Felty

SITE 5-068

afelty@uottawa.ca

Textbook

Introduction to Computer Theory, Daniel Cohen, Wiley, 2nd edition.

Course OutlineDetails 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