The aim of this course “Introduction to Automata Theory, Languages and Computation” is to give a detailed working explanation regarding each Mathematical model, its corresponding languages, and their provable equivalence. “Theory of Computation” has three major subdivisions namely

1) Automata Theory

2) Computability Theory

3) Complexity Theory

The automata theory deals with some Mathematical models that perform some operations automatically like programming machines. There are four main Mathematical models namely, Finite Automata(FA), Push Down Automata(PDA), Linear Bound Automata(LBA), and Turing Machine(TM). Each Mathematical model differs based on its memory units as FA has no external memory unit, PDA has stack as a memory unit, LBA has finite length tape as a memory unit and TM has infinite tape as a memory unit.

Based on the limitations in the memory unit each model solves a limited set of problems only. The set of problems solved by each model is grouped as languages accepted by the model. The problems solved by Finite Automata are called Regular Language and its corresponding language representation is called Regular Grammar. The language accepted by Push Down Automata is called Context Free Language, the language accepted by Linear Bound Automata is called Context Sensitive Language, and the language accepted by Turing Machine is called Un-Restricted language since Turing machines have unlimited memory and random access to the memory unit.

Turing machines can be equated to modern computers, it can solve any problem that is solvable by computers. Computability theory deals with verifying whether the problem is solvable or not and If it is solvable complexity theory deals with the algorithmic complexity of problems that are solvable by Turing Machine.

This course mainly deals with automata theory (Mathematical Models) and its languages.