Theory of Computation
|
Course Objectives
|
| In this course, the main goal is to define the language classes in terms of grammars and automata. |
|
Course materials
|
- Introduction to Theory of Computation, Anil Maheshwari and Michiel Smid, Carleton University, 2012.
- Introduction to the Theory of Computation, 2nd Edition, Michael Sipser, Thomson Course Technnology, Boston, 2006.
- Introduction to Languages and the Theory of Computation, 4th Edition. John C. Martin, 2011, Mc Graw Hill.
|
|
Assessment
|
|
40% Midterm (exam,tasks,etc.) + 60% Final (exam,tasks,etc.)
|
|
Prerequisites
|
there is no formal prerequisite, to get discrete mathematics course before is recommended.
|
| Week |
Subjects |
| 1. |
Discrete Mathematical Structures review |
| 2. |
Deterministic (DFA) and Non-Deterministic (NFA) Finite Automata |
| 3. |
NFA to DFA, Regular Expressions (RegEx) |
| 4. |
DFA to RegEx, Pumping Lemma for Regular Languages |
| 5. |
Context-Free Grammars, Chomsky Normal Form (CNF) |
| 6. |
Push-Down Automata (PDA), CNF to PDA |
| 7. |
Pumping Lemma for Context-Free Languages |
| 8. |
Midterm exam |
| 9. |
Turing Machines, Church-Turing Thesis |
| 10. |
Non-Deterministic Turing Machines |
| 11. |
Decidable and Undecidable Languages |
| 12. |
Enumerability and Enumarable Languages |
| 13. |
Introduction to Complexity Theory, P & NP classes |
| 14. |
Non-Deterministic algorithms, NP-Complete Languages |
| 15. |
Review for final exam |
| |
Final Exam |
|