1

THEORY OF COMPUTATION
Why Is It Important to Study Automata Theory?
Automata theory is important because it allows scientists to understand how
machines solve problems.
An automaton is any machine that uses a specific, repeatable process to convert
information into different forms. Modern computers are a common example of an
automaton.
1.The importance to study the theory of computation is to better understand the
development of formal mathematical models of computation that reflect the real-
world of computer.
2.To achieve deep understanding about the mathematical properties of computer
hardware and software.
3.Mathematical definitions of the computation and the algorithm.
4.To rectify the limitations of computers and answer what kind of problems can be
computed?
➢If scientists didn’t study automata theory, they would have a much more
difficult time designing systems that could perform repeatable actions based on
specific inputs and outputs.
➢Scientists are able to design systems that can perform specific tasks, such as
personal computer systems, automatic aircraft pilots and many more, by using
automata theory.
➢There are a number of other examples of automatons.
➢These range from basic devices, such as a pendulum clock, to missile guidance
systems and complex telephone networks.
➢If scientists didn’t study automata theory, they would have a much more
difficult time designing systems that could perform repeatable actions based on
specific inputs and outputs.
➢Scientists are able to design systems that can perform specific tasks, such as
personal computer systems, automatic aircraft pilots and many more, by using
automata theory.
➢There are a number of other examples of automatons.
➢These range from basic devices, such as a pendulum clock, to missile guidance
systems and complex telephone networks.
➢Thermostats are a familiar example of an automaton.
➢A thermostat checks the temperature of its surrounding environment at specific
intervals, and then turns on when the temperature reaches a certain level. In
this case, there are only two potential states for the thermostat: on or off.
➢Automatons can be much more complex than a thermostat.
➢Modern computers have a large number of data inputs and potential states.
Automata theory is used to design computers that respond to inputs by
producing reliable outputs.
➢It is a scientific control concerned with the investigation of computing features such
as natural, artificial, and otherwise fictitious. Most importantly, it intends to become
acquainted with the atmosphere of resourceful computation.

➢Theory of Computation is very important as it helps in writing efficient algorithms

that operate on computer devices, research and development of programming
languages and in compiler design and construction that is efficient.
➢The primary goal of creating this theory was to broaden approaches for explaining
and analysing the active performance of discrete systems.

➢The knowledge of Theory of Computation is critical for its applications, which

include the construction of intelligent technology, cognitive psychology, and
philosophy, as well as diverse models of computing such as algorithm, compiler, and
VLSI design, etc.
Definition
Automata Theory is a branch of computer science that deals with designing abstract
self-propelled computing devices that follow a predetermined sequence of operations
automatically. An automaton with a finite number of states is called a Finite
Automaton.
Automata –What is it?
The term "Automata" is derived from the Greek word "αὐτόματα" which means "self-
acting". An automaton (Automata in plural) is an abstract self-propelled computing
device which follows a predetermined sequence of operations automatically.

Theory of Computation is a branch of computer science and Mathematics that focuses

on the logic of computation and how different problems are solved using algorithms
and the efficiency of the solutions.
Definition
What is Theory of computation?
• ‘Theory of Computation’ or ‘Theory of Automata’ is the core area of computer
science and engineering; it is the branch that aims to attempts the deep
understanding of computational processes by means of effectively solving the
problems via mathematical models, tools, and techniques.
• This understanding is important for its applications that include various model
of computation like algorithm, compiler and VLSI design, to the creation of
intelligent technology, cognitive psychology, and philosophy.
 (A pioneer of automata theory)
Alan Turing (1912-1954)
• Father of Modern Computer Science
• English mathematician
• Studied abstract machines called Turing machines
even before computers existed
• Heard of the Turing test?
Alan Turing (1912-1954)
History of Theory of automata:
Before 1930’s: Alan Turing Studied an abstract machine that had all the
capabilities of today’s computers to solve problems. A. Turing’s goal was to
describe precisely that boundary between what a computing machines could do
and what it could not do.

1931’s to 1950’s: Simpler kinds of machines were used which we called ‘Finite
Automata’. These automata originally proposed to model brain function, turned
out to be extremely useful for a variety of other purposes like designing
software’s to checking the behavior of digital circuit used in computers etc..
History of Theory of automata:
Late 1950’s to 1960’s: N. Chomsky began the study of formal ‘grammars’ that are not strictly
belongs to the machines, but these grammars have closer relationships to abstracts automata.
In present world these grammars serves as the basis of some important software components,
including parts of compilers.
After 1960’s: Stephen Cook takes the charge and extended the Turing’s study of what could
and what could not be computed. Finally in 1971 S. Cook was succeed to separate those
problems that can be solved efficiently by computer form those problems that can in principle
be solved, but in practically it take so much time that computers are useless for all but very
small instances of the problem. The latter class of problem is called ‘Intractable’ or well
knows as ‘NP-hard’ problems.
Types of Theory of Computation

This branch is divided into 4 parts, namely:

• Automata Theory
• Formal Language
• Computability theory
• Complexity theory.
1. Automata Theory

Automata Theory is a theoretical branch of Computer Science and mathematics and deals with the study of complex
computational problems and abstract machines. The word Automata is derived from the word “Automaton” which is closely
related to the word “Automation”.

Automata are machines that accept a string as input and process it through a finite number of states before reaching the end
state. The primary objective for creating automata theory was to create tools for describing and analysing the dynamic
behaviour of discrete systems.

The basic terms frequently used in Automata Theory are:

Symbols: These are either individual objects or separate entities. These can be any letter, alphabet or any picture.
Strings: These are a finite collection of symbols from the alphabet, and are denoted by w.
Language: A collection of appropriate strings is called a language. A language can be Finite or Infinite.

An automaton with a finite number of states is called a Finite Automaton (FA) or Finite State Machine (FSM). An elaborate
discussion about Finite Automata is given below
Finite Automata

Finite Automata, also known as the Finite State Machine, is a simple machine that is able to recognize patterns. It
is an abstract machine with five components or tuples. It contains a set of states and rules for going from one
state to the next, but it is dependent on the input symbol used. It is essentially an abstract representation of a
digital computer.

Finite automata has two states: Accept State or Reject State.

Types of Finite Automata

Two types of Finite Automata are there:

Deterministic Finite Automata (DFA): In DFA, the computer only travels to one state for each input character.
Here, the uniqueness of the calculation is referred to as deterministic. The null move is not accepted by DFA.
Non-deterministic Finite Automata (NFA): NFA is used to send any number of states for a certain input. It is
capable of accepting the null move.
2.Formal Language Theory

➢Formal Language Theory is a branch of Computer Science and Mathematics dealing

with representing languages as a collection of operations on an alphabet. Automata is
used to generate and recognize different formal languages, hence they are closely
related.

➢It was first initiated by Noam Chomsky in the 1950s. The field of formal language
studies is concerned with the syntax of languages and their internal structural
patterns. Due to the rise of linguistics in the field of formal language, the syntactic
regularities of natural languages now have a means for comprehension.

➢In computer science, formal languages are used to define the grammar of
programming languages as well as formalised versions of subsets of natural
languages in which the words of the language represent concepts with specific
meanings or semantics.
The Chomsky Hierarchy

A Formal language is a set of sequences or strings over some finite vocabulary

identified with words, morphemes or sounds. There are four types of languages in the
Chomsky Hierarchy:

➢Computably Enumerable Languages: The languages that can be defined by any

formal grammar are known as Computably Enumerable Languages. Any formal or
algorithmic procedure can be expressed by grammar. For eg- derivation of logic,
rules of chess etc. All computably enumerable languages are semi-decidable.
➢Context-Sensitive languages: Grammars where the left hand side of each rule is
longer than the right hand side are called Context-sensitive languages. The
specification of this class of grammars assures that a decision method for the
membership problem is instantly established. Eg- set of all prime numbers, set of all
square numbers etc.
The Chomsky Hierarchy
➢ Context-free languages: These are languages defined by context-free grammar. In this case, the non-terminals
can be read as syntactic category names, and the arrow ‘ ' can be interpreted as ‘consists of.' As a result, the
derivation of a string x in such a language enforces an implicit hierarchical structure of x into ever bigger sub-
strings. For this particular reason, context free languages are often referred to as phrase structure languages.
➢ Regular languages: The languages that are defined by regular grammar are known as regular languages.
Regular grammars are also context-free where the non-terminals can be seen as category symbols and the
arrow as consists of. Non-terminals, according to another natural meaning, are the names of an automaton's
states.
3.Computability Theory

➢Computability theory, also known as Recursion Theory, is a branch of Mathematics

and Computer Science that is primarily concerned with the extent to which an issue
may be solved by a computer.
➢ It originated in the 1930s with the study of computable functions and Turing
degrees.

➢The statement that a Turing computer cannot solve the halting issue is one of the
most significant conclusions in computability theory because it is an example of a
concrete problem that is both straightforward to define and impossible to solve with a
Turing machine.
➢The halting issue result serves as the foundation for most of computability theory.
Turing Computability

➢A set of natural numbers is said to be a computable set if, given a number n, a

Turing machine stops with output 1 if n is in the set and stops with output 0 if n
is not in the set.
➢A function f from natural numbers to natural numbers is a computable or
recursive function if a Turing machine stops and returns output f on input n.
(n).
4.Computational Complexity Theory

Computational Complexity Theory is that branch of Theory of Computation that classifies computational
problems according to their resource usage. These computational problems are solved by different algorithms.

An issue is considered inherently complex if its solution necessitates considerable resources, regardless of the
method utilised. This intuition is formalised by the theory, which introduces mathematical models of computing
to analyse these issues and measure their computational complexity, i.e., the amount of resources required to
solve them, such as time and storage.

There are major aspects of Computational Complexities:

Time Complexity: The amount of time or the number of steps taken by the computation to be performed.
Space Complexity: The amount of memory required to perform the computation.

Computer scientists describe the time or space necessary to solve the issue as a function of the size of the input
problem in order to assess how much time and space a specific method takes.
4.Computational Complexity Theory
To be solving the problems via computers the first question rises in every one mind that is, “What
makes some problems computationally hard and other problems are computationally easy?”.

In a informal way a problem is called “computationally easy”, if it is efficiently solvable. For example of
“easy” problems are as follows;

Sorting a sequence of, say, 1,000,000 numbers,

Searching for a name in a telephone directory, and
Computing the fastest way to drive from Ottawa to Miami etc.
On the other hand, a problem is called “computationally hard”, if it cannot be solved efficiently, or if we
are unable to determine that the problem will solve efficiently. For examples of “computationally hard”
problems are as follows;

Time table scheduling for all courses at Carleton,

Factoring a 300-digit integer into its prime factors, and
Computing a layout for chips in VLSI etc.
Advantages of Theory of Computation

There are many advantages of the Theory of Computation. Some of them are listed below:

➢Theory of Computation deals with how efficiently any algorithm would solve any computational
problem. Also, abstract machines are introduced in the Computational theory, which are defined
mathematically. Hence, the algorithms would not need to change every time any physical hardware
gets enhanced.
➢There is a massive amount of work that has been made possible in the portion of NLP (Natural
Language Processing) that involves the construction of FSMs (Finite State Machines), also known as
FSA (Finite State Automata).
➢Theory of Computation has helped in many fields such as Cryptography, Design and Analysis of
Algorithm, Quantum Calculation, Logic within Computer Science, Computational Difficulty,
Randomness within Calculation and Correcting Errors in Codes
➢A computational model can cope with complexity in ways that verbal arguments cannot, resulting in
satisfactory answers for what would otherwise be ambiguous hand-wavy arguments. Furthermore,
computational models can manage complexity at several levels of analysis, allowing data from
various levels to be integrated and connected.
• Applications of various Automata
The Applications of these Automata are given as follows:
1. Finite Automata (FA)
➢For the designing of lexical analysis of a compiler.
➢For recognizing the pattern using regular expressions.
➢For the designing of the combination and sequential circuits using Mealy and Moore
Machines.
➢Used in text editors.
➢For the implementation of spell checkers.
2. Push Down Automata (PDA)
➢For designing the parsing phase of a compiler (Syntax Analysis).
➢For implementation of stack applications.
➢For evaluating the arithmetic expressions.
➢For solving the Tower of Hanoi Problem.
Applications of various Automata
3. Linear Bounded Automata (LBA)
➢For implementation of genetic programming.
➢For constructing syntactic parse trees for semantic analysis of the compiler.
4. Turing Machine (TM)
➢For solving any recursively enumerable problem.
➢For understanding complexity theory.
➢For implementation of neural networks.
➢For implementation of Robotics Applications.
➢For implementation of artificial intelligence.
Sequential machine: A sequential machine is a mathematical model of a certain
type of simple computational structure. Its behavior represents the working
process of finite Auotmata. Sequential machines have numerous applications, for
example, in asynchronous circuits, coding theory, con- current systems, digital
circuit design, formal language theory, hardware testing, protocol design, and
software and hardware verification.

Vending Machines: A vending machine is an automated machine that dispenses

numerous items such as cold drinks, snacks, beverages, alcohol etc. to sales
automatically, after a buyer inserts currency or credit into the machine. Vending
machine is works on finite state automate to control the functions process.
➢Traffic Lights: The optimization of traffic light controllers in a city is a systematic
representation of handling the instructions of traffic rules. Its process depends on a set of
instruction works in a loop with switching among instruction to control traffic.
➢Video Games: Video games levels represent the states of automata. In which a sequence of
instructions are followed by the players to accomplish the task.
➢Text Parsing: Text parsing is a technique which is used to derive a text string using the
production rules of a grammar to check the acceptability of a string.

➢Regular Expression Matching: It is a technique to checking the two or more regular

expression are similar to each other or not. The finite state machine is useful to checking out
that the expressions are acceptable or not by a machine or not.

➢Speech Recognition: Speech recognition via machine is the technology enhancement that is
capable to identify words and phrases in spoken language and convert them to a machine-
readable format. Receiving words and phrases from real world and then converted it into
machine readable language automatically is effectively solved by using finite state machine.
 Finite State Machine
An automaton with a finite number of states is called a Finite Automaton (FA) or
Finite State Machine (FSM).
• Formal definition of a Finite Automaton
• An automaton can be represented by a 5-tuple (Q, Σ, δ, q0, F),
where:
➢Q is a finite set of states.
➢Σ is a finite set of symbols, called the alphabet of the automaton.
➢δ is the transition function.
➢q0 is the initial state from where any input is processed (q0 ∈ Q).
➢F is a set of final state/states of Q (F ⊆ Q)
Finite State Machine (Prerequisites)
Symbol – A symbol (often also called a character) is the smallest building block,
which can be any alphabet, letter, or picture.Ex: a,b,c, 0,1,2,3…
Alphabets - Alphabets are a set of symbols, which are always finite. Which is denoted
by “∑” (sigma).

Strings- A string is a finite sequence of symbols from some alphabet. Ex:a,b,o,1, aa,
bb,ab,01...
Language - A language is a set of strings.
Ex; Set of all strings with length 2 ..L1= {11,01,10,11}
Set of all strings with length 3 ..L1= {000,001,010,011,100,101,110,111}
 Finite State Machine
Formal Notation used in the representation of Finite Automata
Finite automata can be represented in two ways, which are given below:
1. Transition diagram
The transition diagram is also called a transition graph; it is represented by a diagraph. A transition graph consists
of three things:
➢ Arrow (->): The initial state in the transition diagram is marked with an arrow.
➢ Circle : Each circle represents the state.
➢ Double circle : Double circle indicates the final state or accepting state.
2. Transition Table
➢ It is the tabular representation of the behavior of the transition function that takes two arguments, the first is a
state, and the other is input, and it returns a value, which is the new state of the automata.
➢ It represents all the moves of finite-state function based on the current state and input.
➢ In the transition table, the initial state is represented with an arrow, and the final state is represented by a single
circle.
➢ Formally a transition table is a 2-dimensional array, which consists of rows and columns where:
• The rows in the transition table represent the states.
• The columns contain the state in which the machine will move on the input alphabet.
2. Transition Table

• The rows in the transition table represent the states.

• The columns contain the state in which the machine will move on the input alphabet.
Types of Finite Automata
DFA – Deterministic Finite Automata
In DFA, for each input symbol, one can determine the state to which the machine will move.
Hence, it is called Deterministic Automaton. As it has a finite number of states, the machine
is called Deterministic Finite Machine or Deterministic Finite Automata
• DFA refers to deterministic finite automata. Deterministic refers to the uniqueness of the
computation. The finite automata are called deterministic finite automata if the machine is
read an input string one symbol at a time.
• In DFA, there is only one path for specific input from the current state to the next state.
• DFA does not accept the null move, i.e., the DFFA cannot change state without any input
character.
• DFA can contain multiple final states. It is used in Lexical Analysis in Compiler.
Formal Definition of a DFA
A DFA can be represented by a 5-tuple (Q, ∑, δ, q0, F) where −

Q is a finite set of states.

∑ is a finite set of symbols called the alphabet.

δ is the transition function where δ: Q × ∑ → Q

q0 is the initial state from where any input is processed (q0 ∈ Q).

F is a set of final state/states of Q (F ⊆ Q).

Graphical Representation of a DFA

A DFA is represented by digraphs called state diagram.

•The vertices represent the states.
•The arcs labeled with an input alphabet show the transitions.
•The initial state is denoted by an empty single incoming arc.
•The final state is indicated by double circles.
Example - 1
Construct a DFA which accepts all strings that starts with ‘0’.

Σ ={0}
L = {0,00,00,010,011,0000…….}
Example - 2
Construct a DFA that accepts of all strings over {0,1} of length 2.

Σ ={0,1}
L = {00,01,10,11}
How to figure out what DFA recognizes?

L = {Accepts the string 01 or a string of atleast ‘1’ followed by a ‘0’}

f
Assignment Problems:

Example 1:Draw a DFA for the language accepting strings ending with ‘0’ over input alphabets ∑={0, 1} ?
Example 2: Draw a DFA for the language accepting strings ending with ‘01’ over input alphabets ∑={0, 1} ?
Example 3: Draw a DFA for the language accepting strings ending with ‘00’ over input alphabets ∑={0, 1} ?
Example 4: Draw a DFA for the language accepting strings ending with ‘011’ over input alphabets ∑ = {0, 1} ?
Example 5: Draw a DFA for the language accepting strings ending with ‘0110’ over input alphabets ∑ = {0, 1} ?
Example 6: Construct a DFA that accepts all strings over {a,b} that contain the string aabb in it.
NFA (Non-Deterministic finite automata)
➢ Lots of times we have to make decisions. Sometimes, once we make the decision, we
cannot undo it. Sometimes, we can go back, change our minds, make the other choice. But
even then, we still had to spend the time investigating the false path.

➢ Imagine that when we came to a decision point, we could clone ourselves, follow both
paths, and then just “become” the version that turns out to be the better choice. Wouldn’t
that be a hugely powerful upgrade to our lives?

➢ That gets into some pretty complicated philosophy in real life. But in the world of Finite
Automata, the concept of nondeterminism turns out to be something that we can make
quite concrete.
➢ In this, we study what it means to make an FA nondeterministic, and whether it really even
matters in the end.
NFA (Non-Deterministic finite automata)

➢ NFA stands for non-deterministic finite automata. It is easy to construct an NFA than DFA for a given regular
language.
➢ The finite automata are called NFA when there exist many paths for specific input from the current state to the next
state.
➢ The next state can be choosen by random.
➢ All the next state may be choosen by parallel
➢ Every NFA is not DFA, but each NFA can be translated into DFA.
➢ NFA is defined in the same way as DFA but with the following two exceptions, it contains multiple next states, and it
contains ε transition.
Formal Definition - NFA

Formally, an NFA is a 5-tuple (Q, Σ, q0 , T, δ) where as before:

• Q is finite set of states;

• Σ is alphabet of input symbols;

• q0 is start state;

• T is subset of Q giving the accept states; and

• δ is the transition function.

Now the transition function specifies a set of states rather than a state: it maps Q × Σ to { subsets of Q }

NFA also has five states same as DFA, but with different transition function, as shown follows: δ: Q x ∑ →2Q
Graphical Representation of an NFA
An NFA can be represented by digraphs called state diagram.
In which:

1.The state is represented by vertices.

2.The arc labeled with an input character show the transitions.

3.The initial state is marked with an arrow.

4.The final state is denoted by the double circle.

➢ In NFA, given the current state,
there could me multiple next
states.
➢ The next state may be chosen at
random
➢ All the next states may be chosen
in parallel

Figure: Non-Deterministic Finite Automata

If there is any way to run the machine that ends in any set of states out of which atleast one state is a final state, then the
NFA accepts.
 Difference between DFA and NFA
Basis of Difference DFA NFA
Reaction to symbols For each symbolic representation of the alphabet, only a No specifications are needed from the user with respect to
singular state transition can be attained in DFA. how certain symbols impact the NFA.
Empty string transition DFA is not capable of using an Empty String transition. NFA can use an empty String transition.

Structure DFA can be best described and understood as one NFA is like multiple small machines that are performing
machine. computational activities at the same time.
Rejection of string DFA rejects the string in case it terminates in a state that NFA rejects the string in the event of all branches dying or
is different from the accepting state. refusing the string.
Backtracking It is possible to use backtracking in DFA. It is not possible to use backtracking at all times in the case
of NFA.
Ease of construction Given its complex nature, it is tougher to construct DFA. NFA is more easily constructed in comparison to DFA.

Supremacy All DFAs are derived from NFAs. All NFAs are not DFAs.
Transition functions The number related to the next state is one. The number related to the next state/ states is either zero or
one.
Complexities of time The total time required for running any input string in The total time required for running any input string in NFA is
DFA is less than what it is in NFA. larger than that in comparison to DFA.
Full form The full form of DFA is Deterministic Finite Automata. The full form of NFA is Nondeterministic Finite Automata
(NFA).
Space requirement More space allocation needed. Less space needed.
The setting of the next possible set The next possible state is clearly set in DFA. In NFA, every single pair of input symbols and states may
contain many possible next states.
Conversion from NFA to DFA

L ={ Set of all strings over (0,1) that starts with ‘0’}