Theory of Computation

A fundamental question in computer science is whether all computational problems are solvable by existing computers, and which among them can be solved efficiently. This course addresses both. The theory of computation spans two main areas: automata theory and computability theory. The course begins with automata theory, introducing finite automata as a simple model of computation, followed by enhanced models including pushdown automata and context-free grammars. In computability theory, the course introduces the Turing machine as an advanced model of computation and demonstrates that certain problems lie beyond even its capabilities. Automata theory finds applications in compiler construction, program analysis, and natural language processing.

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. Course Rationale and Organization. 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. By the end of this course the students will be able to:

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

Info not available

Info not available

• 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
• Introduction to Theory of Computation by Michael Sipser.
• Elements of the Theory of Computation by Harry Lewis and Christos Papadimitriou.

Info not available