Theory of Computation

This course is organized into four different modules. It starts with reviewing some necessary topics of discrete mathematics in module 1. In module 2, the course introduces a simple model of computation, finite state machine/automaton and its solving capabilities/limitations. Then, the course teaches an improved model of computation, context-free grammar and pushdown automaton in module 3. Module 4 covers a powerful model of computation, called Turing machine, decidability by Turing machines and computations by Turing machines. Although the Turing machine is a powerful model, it has some fundamental limitations. In fact, this course will demonstrate that Turing machines cannot solve many computational problems.

Occasionally, several computational problems arise in computer science and mathematics. The very first question is whether all computational problems are solvable by existing computers, and which problems can be solved efficiently. This course addresses these questions. The theory of computation encompasses two main areas: automata theory and computability theory. The course begins with automata theory, introducing a simple model of computation called a finite automaton, followed by enhanced models known as pushdown automata and context-free grammar. As part of computability theory, the course explores an advanced model of computation called the Turing machine. It demonstrates that there are computational problems beyond the capabilities of Turing machines. Automata theory finds applications such as compiler construction, program analysis, and natural language processing.

By the end of this course, each student will have the opportunity to:

• Understand different computational models, such as the Turing machine, and their limitations.
• Apply the concepts of finite automata and context-free grammars to other areas, like natural language processing and compiler construction.
• Understand why only a tiny fraction of all computational problems are solvable by existing machines.

After completing this course, students should be able to:

• Explain the basic computation models, finite automata, pushdown automata, context-free grammars and Turing machines. | Know/Knowledge Outcome
• Design a computational model for a given problem and formally validate the correctness of the model | Comprehend Outcome
• Find some applications of regular expressions and context-free grammars| Apply Outcome
• Explain difference between decidable and undecidable languages. | Comprehend Outcome
• Demonstrate some fundamental limitations of the existing computing devices using examples. | Comprehend Outcome

• Introduction to Theory of Computation by Michael Sipser.
• Elements of the Theory of Computation by Harry Lewis and Christos Papadimitriou.

• Introduction to Automata Theory, Languages, and Computation by Hopcroft H.E. and Ullman J. D.