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.
- 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.
|Sets, Relations, and Functions|
|Basic Proof Techniques, Closures|
Deterministic and Nondeterministic Finite Automata
|The Chomsky Hierarchy|
|NP versus P|