CENG 213
Theory of Computation
Abstract automata, especially finite state machines; push-down automata; and Turing machines. Formal languages, especially context-free languages. The relationship between automata and languages. Computability and solvability.
Course Objectives
To teach mathematical proof making.
To teach the concepts of automata, formal languages, and Turing machines.
By giving the theoretical grounds in the construction of computers, to ensure the apprehension of the limitations of computing machines.
Recommended or Required Reading
Lewis, H. R., & Papadimitriou, C. H. (1998). Elements of the Theory of Computation. ACM SIGACT News, 29(3), 62-78.
Sipser, M. (1996). Introduction to the Theory of Computation. ACM Sigact News, 27(1), 27-29.
Learning Outcomes
- To be able to classify language definitions.
- To be able to analyze problems and provide appropriate representations for them.
- To be able to show abstraction ability.
- To be able to identify some difficult problems in computer science.
| Topics |
| Introduction |
| Sets, Relations, and Functions |
| Basic Proof Techniques, Closures |
| Languages |
|
Deterministic and Nondeterministic Finite Automata
|
| Regular Expressions |
| Context-Free Grammars |
| Pushdown Automata |
| Turing Machines |
| Decidability |
| The Chomsky Hierarchy |
| Computational Complexity |
| NP-Completeness |
| NP versus P |
Grading
Midterm 35%
Final 45%
Homework 20%
