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.
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 |
