Short Description

An introduction to formal models of computation: finite automata, pushdown automata, Turing machines, and the corresponding classes of formal languages (regular, context-free, semi-decidable). You will learn how to design algorithms for concrete computational problems within these models of computation, and the dichotomy between deterministic and non-deterministic computation will be introduced.

You will gain an appreciation of the limits of computation, including methods of proving undecidability and specific examples of undecidable problems. The concept of computational complexity and complexity classes will be introduced.

You’ll learn to:

• Demonstrate an understanding of the fundamental models of computation and the corresponding classes of formal grammars and languages
• Design algorithms for specific computational problems as automata of appropriate types
• Demonstrate the practical application of grammars and language within the context of parsing algorithms
• Prove mathematically that some computational problems are undecidable within a particular class of computational models
• Put theory into practice by creating a parser for a specific language