Introduction to Theory of Computation
Channel: Dr Lakshmi D
Date: 2021-07-11

Why should we study this subject?
Theory of Computation (TOC) or Formal Languages and Automata Theory is a foundational subject for understanding Compilers and Interpreters. But it is not limited to it.
TOC is widely used in Artificial Intelligence, Natural Language Processing, Information Security, System Software, Neural Networks and many more.
History:  “Theory of Computation”?
Typically, people are so excited by the wonders of computing  technology we need  to wonder about the theory underlying it. Let us try to understand the intellectual contents of the Theory of Computing.

Entscheidungsproblem: A decision problem, of finding a way to decide whether a formula is true or provable within a given system.
TOC teaches you about the elementary ways in which a computer can be made to think.
Any algorithm can be expressed in the form of a finite state machine and can serve as a helpful visual representation of the same.
Computability theory is concerned with the classification of problems that can and cannot be solved by computer programs.
Theory of computation lays a strong foundation for abstract/conceptual/theoretical areas in computer science.
It gives you the answer to “How is a computer made to think”?
Automata tells you whether a given problem is solvable or not.
Stephan Wolfram who is a leader in automata applications, states that the entire universe has a set of states and rules and single conditions.
 Purpose and motivation
This course is on the Theory of Computation, which tries to answer the following questions:
What are the mathematical properties of computer hardware and software?
What is a computation and what is an algorithm?
What are the limitations of computers? Can “everything” be computed? (As we will see, the answer to this question is “no”.)
Nowadays, the Theory of Computation can be divided into the following three areas: Complexity Theory, Computability Theory, and Automata Theory.
Purpose of the “Theory of Computation”: Develop formal mathematical models of computation that reflect real-world computers.
The theory of computation is the branch of computer science that deals with whether and how efficiently problems can be solved on a computer. The field is divided into two major branches: computability theory and complexity theory, but both branches deal with formal models of computation.
There are several models of computation in use, but the most commonly examined is the Turing machine. A Turing machine can be thought of as a desktop PC with an infinite memory capacity, though it can only access this memory in small discrete chunks. While the infinite memory capacity might be considered an unphysical attribute, for any problem actually solved by a Turing machine the memory used will always be finite, so any problem that can be solved on a Turing machine could be solved on a desktop PC which has enough memory installed.
Examples of such models are:
 
Finite Automata (FA): These are used in text processing, compilers, and hardware design.
Push Down Automata (PDA): These are used to define programming languages and in Artificial Intelligence.
Linear Bounded Automata (LBA): A linear bounded automaton is a multi-track non-deterministic Turing machine with a tape of some bounded finite length.
Turing Machines (TM): These form a simple abstract model of a “real” computer, such as your PC or laptop. 
Note: This subject is one of the major considerations in the GATE examination. To crack the GATE exam you need to have a deeper understanding of the subject. 
Automatons are applied in fields including:
1) Design and Analysis of Algorithms 
2) Web search: theory of pattern matching 
3) Sequential circuits: theory of finite state automata 
4) Compilers: theory of context free grammars 
5) Cryptography: theory of computational complexity 
6) Data compression: theory of information
7) Fluid Flow
8) Snowflake and crystal formation
9) Chaos theory
10) Cosmology
11) Financial analysis
12) Natural Language Processing
13) Text Editor
14) Command Interpreter
15) Digital Circuit Design
Automata theory
Automata Theory deals with definitions and properties of different types of “computation models”, its equivalent grammar and its structure.

Automata and Complexity

The power of computation and the time complexity of the computation increases from Type 3 grammar to Type 0 grammar. 
A language is Decidable or Recursive if a Turing machine can be constructed to accept the strings which are part of a language and reject others. e.g.; ‘A number is prime or not’ is a decidable problem.
A language is Semi–Decidable or Recursively Enumerable if a Turing machine can be constructed to accept strings which are part of language and it may loop forever for strings which are not part of language.
A problem is undecidable or unsolvable if we can’t construct an algorithm and Turing machine which can give a yes or no answer. e.g.; Whether a CFG is ambiguous or not is undecidable.