Theory of Computation

CSE322
4

The course gives an overview over basic formal grammars and abstract machine models used in Computer Science. In particular, finite automata, pushdown automata, context-free grammars and Turing machines are studied with respect to their properties and limits. Based on Turing machines the concepts of decidability and recursive enumerability are introduced.

1. The student is able to describethe basic computational models FAs, PDAs, grammars and Turing machines.
2. The student is able to formally model a given computational problem and prove its correctness.
3. The student can explain the concepts of undecidability and recursive enumerability and is able to give examples of respective problems.
Winter

Course Offering