CS8501 Theory of Computation

Dr.G.Rajiv Suresh Kumar

Professor, CSE- JCTCET

CS8501 ToC JCT CET - Dept. of CSE 1

 Introduction
• Automata theory is the study of computing devices or
machines.
• What is computation?
• Computation is the step-by-step solution to a problem.
• For Example, To multiply the two numbers, how do we
multiplying them. Using known methods, and known
algorithms multiply two numbers to get their product.
This is an example of computation.

CS8501 ToC JCT CET - Dept. of CSE 2

• a step-by-step method or what is known as an algorithm
that helps us answer the question.
• For computational problems, what model or what kind of
computational devices are used to compute solution or
on what computational devices run the algorithm.
• A computer is a very popular example.For example,
multiply two numbers can be solved using a calculator or
cell phone or a computer, also can do it on pen and
paper. So pen and paper also is a computational device,
because these can be used to solve a certain
computational problems.

CS8501 ToC JCT CET - Dept. of CSE 3

• The first kind of computational devices are known as
finite automata.
• Finite automata is a computational model which has in
some sense a finite amount of memory, more
specifically the finite automata has states and the
number of states in such a model is a finite number, it
does not depend on the size of the input that is given to
it.
• An automaton (Automata in plural) is an abstract self-
propelled computing device which follows a
predetermined sequence of operations automatically.
•

CS8501 ToC JCT CET - Dept. of CSE 4

•An automaton with a finite number of states is called a Finite Automaton
(FA) or Finite State Machine (FSM).
•An electric switch is an example of finite automata.
•what an electric switch is, how many states does the electric switch have or
at any given point of time, what can be the position of an electric switch.
•An electric switch is either in the on position or in the off position at any
given point of time.
•These are the states of the electric switch, so it can either be at the off state
in which case whatever electrical device that is connected to it is not working
or not getting electric supply, or it can be in the on state in which case the
device is getting electric supply.

CS8501 ToC
5
JCT CET - Dept. of CSE
• So, for example, if I give you a sequence of
the following operations let say CC AC C A
which state will be landed. Ans:(2)
• Now let us look at a slightly more
mathematical example. Consider binary
strings that is strings consisting of zeros
and ones.
• And we look at the following set of strings,
which we call L,

CS8501 ToC JCT CET - Dept. of CSE 7

• x is, a set of strings , such that x is a
binary string divisible by 4.
• So let us look at some strings which are in
L and some strings which are may not in L.
• So, if I take the string 1 0 0, it is the
decimal equivalent of this string is 4.
• Check the binary strings belongs to the
language L or not, or belongs to set L or
not. So 4, of course, is divisible by 4,
hence it belongs to the set L.

CS8501 ToC JCT CET - Dept. of CSE 8

•What about 1 1 0? So, the decimal equivalent of 1 1 0
is 6; and 6 is not divisible by 4,hence it does not
belong to the set L.

• If you look at 1 1 0 0, what is the corresponding

decimal string, is 12; and 12 is divisible by 4, hence it
lies in the language and so on.

•So, if you just spend a little time, and if you just try to
work it out, you will realize that the set of strings in the
line or in this set L is exactly those strings which end
with two zeros.

CS8501 ToC
9
JCT CET - Dept. of CSE
• Start state is in this case is 0 0;
• Our Accept state in this case is also the state 0 0.
• If the string is 1 1 0, initially start at the state 0 0;
• If 1 is given by this automata, it goes to the state 0 1.
• On the next 1, it goes to the state 1 1;
• And on the next 0, it goes to the state 1 0.
• Hence the string 1 1 0 is not accepted by the automata,
hence it can not end up at the accept state.

CS8501 ToC JCT CET - Dept. of CSE 12

• Another example, So let us look at another string1 1 0 0.
• So from 0 0 on 1, we go to 0 1;
• from 0 1 on a 1, we go to 1 1;
• from 1 1 on a 0, we go 1 0.
• And from 1 0 on a 0, we go to 0 0.
• Hence the string 1 1 0 0 is acceptable.

CS8501 ToC JCT CET - Dept. of CSE 14

• A regular expression is a method used in programming
for pattern matching.

• Regular expressions provide a flexible and concise

means to match strings of text. For example, a regular
expression could be used to search through large
volumes of text and change all occurrences of "cat" to "
dog".

CS8501 ToC JCT CET - Dept. of CSE 15

Context-Free Grammars
• A context-free grammar (CFG) is a set of recursive
rewriting rules (or productions) used to generate
patterns of strings.

A CFG consists of the following components:

• A set of terminal symbols, which are the characters of

the alphabet that appear in the strings generated by the
grammar.

CS8501 ToC JCT CET - Dept. of CSE 16

• A set of nonterminal symbols, which are placeholders for
patterns of terminal symbols that can be generated by
the nonterminal symbols.

• A set of productions, which are rules for replacing (or

rewriting) nonterminal symbols (on the left side of the
production) in a string with other nonterminal or terminal
symbols (on the right side of the production).

CS8501 ToC JCT CET - Dept. of CSE 17

A CFG for Arithmetic Expressions
• An example grammar that generates strings representing
arithmetic expressions with the four operators +, -, *, /,
and numbers as operands is:
• <expression> --> number
• <expression> --> ( <expression> )
• <expression> --> <expression> + <expression>
• <expression> --> <expression> - <expression>
• <expression> --> <expression> * <expression>
• <expression> --> <expression> / <expression>

CS8501 ToC JCT CET - Dept. of CSE 18

• The only Non Terminal Symbol in this grammar is
<expression>, which is also the Start Symbol. The
Terminal Symbols are {+,-,*,/,(,),number}. (We will
interpret "number" to represent any valid number.)
• The first rule (or production) states that an <expression>
can be rewritten as (or replaced by) a number. In other
words, a number is a valid expression.
• The second rule says that an <expression> enclosed in
parentheses is also an <expression>.

CS8501 ToC JCT CET - Dept. of CSE 19

• Note that this rule defines an expression
in terms of expressions, an example of the
use of recursion in the definition of
context-free grammars.
• The remaining rules say that the sum,
difference, product, or division of two
<expression>s is also an expression.

CS8501 ToC JCT CET - Dept. of CSE 20

 UNIT I AUTOMATA FUNDAMENTALS
•Introduction to formal proof
•Additional forms of Proof
•Inductive Proofs
•Finite Automata
•Deterministic Finite Automata
•Non-deterministic Finite Automata
•Finite Automata with Epsilon Transitions
TEXT BOOK:J.E.Hopcroft, R.Motwani and J.D Ullman, ―Introduction to
Automata Theory, Languages and Computations‖, Second Edition,
Pearson Education, 2003

CS8501 ToC JCT CET - Dept. of CSE 21

Introduction to Formal Proof

• Formal Proof is a step by step procedure used to solve

the problem.
• Here truth of the program is shown by a detailed
sequence of steps and reasons.
• Testing of the program is important,
• But for the complex program that involves in iteration
and recursion, then code may become incorrect.

CS8501 ToC JCT CET - Dept. of CSE 22

Introduction to Formal Proof ...
• To make the iteration or recursion correct, set up an
inductive hypothesis (Acceptable Assumption) and it is
helpful to reason formally or informally, that the
hypothesis is consistent with the iteration or recursion.
• This process of Analyzing and Working of a correct
program is similar to proving the theorems by inductive
or induction.
• Automata theory is used to cover the methodologies of
formal proof.
• Formal Proof may (1).Deductive Formal Proof and (2).
Inductive Formal Proof.

CS8501 ToC
23
JCT CET - Dept. of CSE
Introduction to Formal Proof ...
• Deductive Formal Proof consists of a sequence of
justified steps.
• Inductive Formal proof is recursive proof of a
parameterized statement that use the statement itself
with lower values of the parameter.
• Methods of formal proof involves,
• (1).Deductive Proof , (2).Reduction to definitions
(3).Other theorem forms , (4).Theorems that appear not to
be If – Then.

CS8501 ToC
24
JCT CET - Dept. of CSE
Deductive Proof
• Deductive Proof consists of a sequence of statements
whose truth is derived from initial statement called
hypothesis.
• Each step in the proof must follow by some accepted
logical principle from the given facts or some of the
previous statements in the deductive proof.
• The hypothesis may be true or false, typically depending
on the values of its parameters.
• Hypothesis consists of independent statements
connected by a logical AND.

CS8501 ToC
25
JCT CET - Dept. of CSE
1.Deductive Proof
• The format is
“If H then C”
The above statement is also expressed as (C is deduced
from H)
Where H  Hypothesis
C  Conclusion.

CS8501 ToC
26
JCT CET - Dept. of CSE
 CS8501 ToC
27
JCT CET - Dept. of CSE
 CS8501 ToC
28
JCT CET - Dept. of CSE
 CS8501 ToC
29
JCT CET - Dept. of CSE
2.Reduction to Definitions

• If you are not sure how to start a proof convert all terms
in the hypothesis to their definitions.
• Here is an example of a theorem that is simple to prove
once we have expressed its statement in elementary
terms. It uses the following two definitions.

CS8501 ToC
30
JCT CET - Dept. of CSE
 CS8501 ToC
31
JCT CET - Dept. of CSE
 CS8501 ToC
32
JCT CET - Dept. of CSE
Theorem1.3 : Let S be a finite sub set of some infinite U. Let T be the
complement of S with respect to U.Then T is infinite.

PROOF : Intuitively this theorem says that if you have an infinite

supply of something (U) , and you take a finite amount away (S)
Then you still have an infinite amount left. Let us begin by restating
the facts of the theorem as in below Fig,

CS8501 ToC
33
JCT CET - Dept. of CSE
3.Other Theorem Forms
• The
if - then, form of theorem is most common in typical areas of
mathematics. However we see other kinds of statements proved as
theorems also,
• Different Ways of Saying If – Then
First there are a number of kinds of theorem statements that look
different from a simple if H then C form, but are in fact saying the
same thing : if hypothesis H is true for a given value of the
parameter (s), then the conclusion C is true for the same value.
Here are some of the other ways in which,
if H then C ,might appear.
1.H implies C
2.H only if C
3.C if H
4.When ever H holds, C follows.

CS8501 ToC JCT CET - Dept. of CSE 34

 CS8501 ToC
35
JCT CET - Dept. of CSE
3a.If and Only If Statements

• Sometimes, we find a statement of the form
”A if and

only if B”, Other forms of this statement are
”A iff B”, “A
is equivalent to B”, or
”A exactly when B”. This statement
is actually two if then statements. “if A then B” and
”if B
then A”. We prove
”A if and only if B” , by proving these
two statement

CS8501 ToC JCT CET - Dept. of CSE 36

1.The if part ,“
if B then A
2. The only if part : “if A then B” , which is
often stated in the equivalent form “A only
if B”.

CS8501 ToC JCT CET - Dept. of CSE 37

CS8501 ToC JCT CET - Dept. of CSE 38
CS8501 ToC JCT CET - Dept. of CSE 39
4.Theorems That Appear Not to Be If
Then
Statements

• Sometimes we encounter a theorem that appears not to

have a hypothesis. An example is the well known fact
from trigonometry.

CS8501 ToC JCT CET - Dept. of CSE 40

CS8501 ToC JCT CET - Dept. of CSE 41
CS8501 ToC JCT CET - Dept. of CSE 42
• Additional Forms of Proof
To Construct Proof
• Proofs about sets.
• Proofs by contradiction
• Proofs by counter example

CS8501 ToC JCT CET - Dept. of CSE 43

Proving Equivalence about Sets

• If E and F are two expressions representing sets the

statement E=F means that the two sets represented are
same.
• That is every element in the set represented by E is in the
set represented by F. an vice versa.
• Therefore the equivalent of sets E=F can be proved in
the following ways,

CS8501 ToC JCT CET - Dept. of CSE 44

CS8501 ToC JCT CET - Dept. of CSE 45
CS8501 ToC JCT CET - Dept. of CSE 46
CS8501 ToC JCT CET - Dept. of CSE 47
CS8501 ToC JCT CET - Dept. of CSE 48
 CS8501 ToC
49
JCT CET - Dept. of CSE
 CS8501 ToC
50
JCT CET - Dept. of CSE
2.Inductive Proof
Definition: A special form of proof deals recursively
defined objects.

• Induction on Integers
• Structural Inductions
• Mutual Induction

CS8501 ToC JCT CET - Dept. of CSE 51

1.Induction on Integers
• Inductions on Integers Suppose we are given a
statement S(n), about an integer n, to prove, One
common approach is to prove two things. (1)The basis
and (2)Induction.
• (1).Basis: Where we show S(i),for a particular integer i,
Usually, i=0 or i=1, but there are examples where we want
to start at some higher i, perhaps because the statement
S is false for a few small integers.
• e.g 1: To print name 3 times
for(i=1;i<=3;i++)
• e.g 2: To print numbers from 5 to 10
for(i=5;i<=10;i++)

CS8501 ToC JCT CET - Dept. of CSE 52

• (2).Iduction: The inductive step, where we assume n≥i,
where i is the basis integer, and we show that if “S(n)
then S(n+1)

CS8501 ToC
53
JCT CET - Dept. of CSE
CS8501 ToC JCT CET - Dept. of CSE 54
CS8501 ToC JCT CET - Dept. of CSE 55
CS8501 ToC JCT CET - Dept. of CSE 56
CS8501 ToC JCT CET - Dept. of CSE 58
CS8501 ToC JCT CET - Dept. of CSE 59
CS8501 ToC JCT CET - Dept. of CSE 60
2.Structural Induction
• In automata theory, there are several recursively defined
structures about which we need to prove statements.
• The familiar notions of trees and expressions are
important examples.
• Like inductions, all recursive definitions have a basis
case, where one or more elementary structures are
defined and an inductive step, where more complex
structures are defined in terms of previously defined
structures.

CS8501 ToC JCT CET - Dept. of CSE 61

• Example :Here is the recursive definition of a tree,
BASIS: A single node is a tree, and that node is the root of
the tree.

INDUCTION:If T1, T2,… Tk are trees, then a new tree can be

formed as
• 1. Begin with a new node N, which is the root of the tree
• 2.Add copies of all the trees T1,T2,…Tk
• 3.Add edges from node N to the roots of each of the
trees T1,T2,…Tk

CS8501 ToC JCT CET - Dept. of CSE 62

CS8501 ToC JCT CET - Dept. of CSE 63
Example 2:
Here is another recursive definition, This time we define
expressions using the arithmetic operators +and *,
without the numbers and variables allowed as operands.
• BASIS:Any number or letter (i.e avariable) is an
expression.
• INDUCTION:If E and F are expressions, then E+F, E*F, and
(E) are expressions.
• For example 2 and E are expressions by the basis.

CS8501 ToC JCT CET - Dept. of CSE 64

• The inductive step tells us x+2,(x+2) and 2*(x+2) all are
expressions.
• Let S(X) be a statement about the structures X that are
defined by some particular recursive definition.
• As a basis prove S(X) for the basis structure (s) X
• For the inductive step take a structure X that the
recursive definition says is formed from Y1,Y2…Yk
• Assume that the statements S(Y1),S(Y2)…S(Yk) holds
and use these to prove S(X)
• Our conclusion is that S(X) is true for all X.

CS8501 ToC JCT CET - Dept. of CSE 65

• Sometimes, we can not prove a single statement by
induction but rather need to prove a group of statements
S1(n),S2(n),…Sk(n). Together by an induction of n.
• We sample the common situation where we need to
explain what an automaton does by proving a group of
statements, one for each state.

CS8501 ToC JCT CET - Dept. of CSE 66

3.Mutual Induction

• When a single statement cannot b proved

by Induction, then group of statements
need to proved.[i.e S1(n),S2(n),…Sk(n)
together by the Induction “n” ]
• Proving the group of statements is similar
to proving the conjunction(logical AND) of
all the statements.
e.g: S1(n),S2(n),…Sk(n) can be given as
S1(n)ANDS2(n)AND,…ANDSk(n)
CS8501 ToC JCT CET - Dept. of CSE 67