Course Code/Title: CS3401/Theory of Computation

UNIT I - AUTOMATA AND REGULAR EXPRESSIONS

Syllabus: Need for automata theory - Introduction to formal proof – Finite Automata (FA) – Deterministic Finite
Automata (DFA) – Non-deterministic Finite Automata (NFA) – Equivalence between NFA and DFA – Finite
Automata with Epsilon transitions – Equivalence of NFA and DFA- Equivalence of NFAs with and without ε-moves-
Conversion of NFA into DFA – Minimization of DFAs.

Need for Automata Theory

• In automata theory and computability the word computability is for the computation in mathematical
modeling. Hence this subject deals with the study of various mathematical models that are required for some
computations.
• In this study, various models, their behavior, properties, kind of languages they accept, their limitations are
studied.
 The theory of computation provides a set of abstract structures that are useful for solving certain
classes of problems. These abstract structures can be implemented on available hardware or software
platform.
• Using these abstract structures the required design efforts can be determined for the actual model.
• Theory of computation plays an important role in compiler design.
• In switching theory, design and analysis of digital circuits automata theory can be applied.
• Many times, to prove the correctness of the program, automata theory is used.
Introduction to Formal Proof
The formal proof can be using deductive proof and inductive proof. The deductive proof consists of
sequence of statements given with logical reasoning in order to prove the first or initial statement.
• The formal proof can be using deductive proof and inductive proof.
• The deductive proof consists of sequence of statements given with logical reasoning in order to prove the
first or initial statement. The initial statement is called hypothesis.
• The inductive proof is a recursive kind of proof which consists of sequence of parameterized statements
that use the statement itself with lower values of its parameter.
• In short, formal proofs are the proofs in which we try to prove that statement B is true because statement A
is true. The statement A is called hypothesis and B is called conclusion statement. In other words, "if A then
B" we say that B is deduced from A.
Additional Forms of Proof
We will discuss additional forms of proofs with the help of some examples. We will discuss
1. Proofs about sets.
2. Proofs by contradiction.
3. Proofs by counter example.
A Proof about Sets

1
Course Code/Title: CS3401/Theory of Computation

The set is a collection of elements or items. By giving proofs about the sets we try to prove certain properties
of the sets.
For example if there are two expressions A and B and we want to prove that both the expressions A and B are
equivalent then we need to show that the set represented by expression A is same as the set represented by
expression B. Let PUQ = QUR if we map expression A with PUQ and expression B with QUR then to prove
A = B we need to prove PUQ = QUP.
This proof is of the kind "if and only if" that means an element x is in A if and only if it is in B. We will
make use of sequence of statements along with logical justification in order to prove this equivalence.
Let us prove PUQ = QUP.

Hence PUQ = QUP. Thus A = B is true as element x is in B if and only if x is in A.

Proof by Contradiction
In this type of proof, for the statement of the form if A then B we start with statement A is not true and thus
by assuming false A we try to get the conclusion of statement B. When it becomes impossible to reach to
statement B we contradict ourself and accept that A is true.
For example -
Prove PUQ = QUP.
Proof
• Initially we assume that PUQ = QUP is not true. That is PUQ ≠ QUP.
• Now consider that x is in Q, or x is in P. Hence we can say x is in PUQ (according to definition of union).
• But this also implies that x is in QUP according to definition of union.
• Hence the assumption which we made initially is false.
• Thus PUQ = QUP is proved.
2
Course Code/Title: CS3401/Theory of Computation

Example 1.3.1 Prove that √2 is not rational.

AU: Dec.-11, Marks 8
Solution:
Proof: We will assume that, √2 is a rational number. That means we can write
√2 = a/b ...(1)
where a and b are integers and a/b is irreducible and can be simplified to lowest term. Squaring on both sides
of equation (1),
2 = a2/b2
i.e. 2b2 = a2
This shows that L.H.S. is even (i.e. multiple of two). Hence R.H.S. is also even. Now if we write a = 2 k
then,
2b2 = (2 k)2 = 4k2
b2 = 2 k2
This means, even b is an even number. This is contradiction our assumption that a/b simplified to lowest
term because a and b are both even. So √2 cannot be rational.

Example 1.3.2 Prove that if n is a positive integer such that n mod 4 is 2 or 3 then n is not a perfect
square. AU: Dec.-12, Marks 6
Solution: The method of contra positive is used. According to method of contra position for proving "If A
then B" we prove if not A then not B.
Here we prove - IF n is a perfect square then n mod (4) must be 0 or 1.
Consider that there exists a positive integer n such that n mod 4 is 0 or 1. Then n is a perfect square i.e. n =
m2, where m is another positive integer. Following are some cases -
1) If m mod 4 = 0 then m = 4i.
For instance - IF i = 1 then m is perfect square
Here i = 1, 4, 9, ...
2) If m mod 4 = 1, then m = 4i + 1.
Here i = 2, 6, 12, 20, ...
3) If m mod 4 = 2, then m = 4i + 2.
Here we fail to identify value of i that will make m as perfect square.
4) If m mod 4 = 3 then m = 4i + 3.
Again there does not exist any value of i which lead to m as perfect square. This proves that n is a positive
integer such that n mod 4 is 2 to 3 and n is not a perfect square.
3
Course Code/Title: CS3401/Theory of Computation

Proof by Counter Example

In order to prove certain statements, we need to see all possible conditions in which that statement remains
true. There are some situations in which the statement can not be true. For example -
There is no such pair of integers such that
a mod b = b mod a
Proof: Consider a = 2 and b = 3. Then clearly
2 mod 3≠ 3 mod 2
Thus the given pair is true for any pair of integers but if a = b then naturally
a mod b = b mod a
Thus we need to change the statement slightly. We can say
a mod b = b mod a, when a = b.
(This type of proof is called counter example. Such proof is true only at some specific condition.
Inductive Proof
AU: May-07,08,12,14,16,17, Dec.-12, Marks 16
Inductive proofs are special proofs based on some observations. It is used to prove recursively defined
objects. This type of proof is also called as proof by mathematical induction.
The proof by mathematical induction can be carried out using following steps
1. Basis: In this step we assume the lowest possible value. This is an initial step in the proof of mathematical
induction.
For example, we can prove that the result is true for n = 0 or n = 1.
2. Induction hypothesis: In this step we assign value of n to some other value k. That mean we will check
whether the result is true for n = k or not.
3. Inductive step: In this step, if n = k is true then we check whether the result is true for n = k + 1 or not. If
we get the same result at n = k + 1 then we can state that given proof is true by principle of mathematical
induction.

Example 1.4.1 Prove by induction on n that Σni=0 i = n(n+1)/2

AU: May-12, Marks 6
Solution: Initially,
1) Basis of induction -
Assume, n = 1. Then,
L.H.S= n, = 1
R.H.S = n(n+1)/2 = 1(1+1)/2 = 2/2 = 1

4
Course Code/Title: CS3401/Theory of Computation

Now,
2) Induction hypothesis -
Now we will assume n = k and will obtain the result for it. The equation then becomes,
1+2+3+ ... + k = (k(k+1)/2
3) Inductive step -
Now we assume that equation is true for n = k. And we will then check if it is also true for n = k + 1 or not.
Consider the equation assuming n = k + 1
L.H.S. = 1+ 2+ 3... + k + k + 1 equation (1)
k(k+1)/2 +k+1
= k(k + 1) + 2(k + 1)/2
= (k+ 1) (k + 2)/2 taking common factor
i.e. = (k + 1) (k + 1 + 1)/2
= R.H.S.

Example 1.4.2 Prove: n!>= 2n-1

Solution: Consider,
1. Basis of induction - Let n = 1 then L.H.S. = 1 R.H.S. = 21 - 1 =20 =1 hence n!>= 2n-1 is proved.
2. Induction hypothesis - Let n = n + 1 then
k! = 2k-1 where k > = 1
then (k + 1)! = (k + 1)k! by definition of n!
= (k+1) 2k -1 = 2 × 2k-1 = 2k

Example 1.4.3 Prove that 12 + 22 + 32 + ... + n2 = Σni=1 i2 = n(n + 1) (2n + 1)/6 using mathematical
induction. AU: May-07, 16, Marks 6, May-14, Marks 8
Solution: We will first prove it by basis of induction and then will consider induction hypothesis.
1. Basis of induction -
Let n = 1
L.H.S. = 12 = 1
R.H.S. = 1(1+1)(2.1+1) /6 = 6/6
R.H.S. = 1
As L.H.S. = R.H.S it is proved for n = 1.
2. Induction hypothesis - Let, n = k.
5
Course Code/Title: CS3401/Theory of Computation

Then
12 + 22 + …….. + k2 = Σki=1 i2 = k(k+1)(2k+1) /6 is true
Now, we will try to prove it for n = k + 1. Hence we will substitute n by k + 1.
12 + 22 + 32 +............+ (k+1)2 = Σk+1i=1 i2 = (k+1)(k+1+1)(2(k+1)+1) /6
L.H.S. = 12 + 22 + 32 +...... + k2 + (k+1)2
We will substitute equation (1) and we will get,
= (k+1) [k(2k+1)+6k+6 /6] = (k+1) [2k2+k+6k+6 /6]
= (k+1) [2k2 +7k+6 /6] = (k+1)(2k2+4k+3k+6) /6
= (k+1)(2k(k+2)+3(k+2)) /6 = (k+1)((2k+3)(k+2)) /6
= (k+1)((k+2)(2k+3)) /6 = = (k+1)(k+1+1)(2(k+1)+1) /6
= R.H.S.
As L.H.S. = R.H.S., it is true that using n = k + 1 the given expression can be proved.

Example 1.4.4 Prove 1+4+ 7+.......+ (3n-2) = n(3n-1)/2 for n > 0

Solution: Consider,
1. Basis of induction -
Let, n = 1,
L.H.S. (3.1-2) = 1
R.H.S. = 1(3.1-1) /2 = 2/2 = 1
As L.H.S. = R.H.S. given expression is true for n = 1.
2. Induction hypothesis - We assume that the given expression is true for n = k.
i.e.
1+4+7+.......+(3k-2) = k(3k-1) is true. …...(1)
Now we will prove it for n = k + 1.
L.H.S. 1+4 +7 +...... + (3k-2)+(3(k+1)-2)
We will substitute R.H.S. of equation (1).
= k(3k-1) /2 +(3(k+1)-2) = k(3k-1)+2[3(k+1)-2] /2
= 3k2-k+6k+2 /2 = 3k2+5k+2 /2
= 3k2+2k+3k+2 /2 = (2k+2)+(3k2 +3k) /2
= 2(k+1)+3k(k+1) /2 = (k+1)(3k+2) /2 = (k+1)(3(k+1)-1) /2
= R.H.S.

6
Course Code/Title: CS3401/Theory of Computation

As L.H.S. = R.H.S. the given expression is true for n = k + 1.

Example 1.4.5 Prove: 2n > n3 where n ≥ 10.
Solution: 1) Basis of induction -
Initially we assume,
n = 10 then
210 > (10)3 is true
2) Induction hypothesis -
Now assume, n = k then
2K > k3
3) Inductive step-
Now we will assume k = k + 1 then the equation becomes
L.H.S. = 2(k+1)
= 2.2k
≥ (1 + 1/10)3.2k
≥ (1 + 1/k)3. 2k
But as 2k > k3 we will replace 2k by k3 then
≥ (1+ 1/k)3. k3
≥ (k+1 /k)3. k3
≥ (k+1)3 /k3. k3
≥ (k+1)3
= R.H.S.
Hence 2k + 1 ≥ (k + 1)3 is also true.
This proves 2n > n3 for n ≥ 10.

Example 1.4.6 Prove: 2n > n using principle of mathematical induction.

Solution:
1) Basis of induction - Assume n = 1 then,
2n > n becomes
21 > 1
2>1
This also implies 2n - n > 0

7
Course Code/Title: CS3401/Theory of Computation

2) Induction hypothesis - Assume n = k is true

i.e. 2k > k
i.e. 2k - k > 0
Thus 2k - k implies a positive number. i.e.
2k - k = t
3) Inductive step - Assume k = k + 1 then
2k+1 - (k + 1)
2k.2 - (k+1)
But from equation (1) 2k = k + t then
(k+t).2 - k - 1
i.e. 2k + 2t - k - 1
k + 2t - 1
> 0 i.e. as positive number.
This implies 2k+1 > k + 1. Hence 2n > n true.

Example 1.4.7 Prove 2n <= n! for all n >= 4.

Solution:
1. Basis of induction - Let n = 4 then
L.H.S. 24 = 16
R.H.S.= n! (4)! (1 x 2 x 3 x 4) = 24
i.e. L.H.S <= R.H.S.
Hence 2 <= n! is proved.
2. Induction hypothesis
We assume n = k and
2k <= k! is also true where k >= 4.
Now we have to consider n = k + 1, then
L.H.S. = 2k+1 = 2k. 21
R.H.S. = (k + 1)!= (k + 1) k!
By induction hypothesis we have
k! > 2k
(k + 1) k! > 2k.21 where k >= 4

8
Course Code/Title: CS3401/Theory of Computation

i.e.
2k+1 <= (k+1)! is true.
As it is true for n = k + 1, the given expression is proved.

Example 1.4.8 Prove that for every integer n≥0 the number 42n+1 + 3n+2 is multiple of 13.
AU: May-08, 14, Marks 10
Solution: We will prove this using method of induction.
Basis - Assume
n=1
P(1) = 42(1)+1+31+2
= 43 + 33
= 91 which is = 13×7
Hence 42n+1 + 3n+2 is multiple of 13 when n = 1.
Inductive step - Assume n = k
P(k) = 42k+1 + 3k+2
P(k) = 13 m
where m is some integer.
Thus we assume that given expression is true for P(k). Now we will prove that is also true for P(k+1).
Let, n = k +1 then
P(k+1) = 42(k+1)+1 + 3(k+1)+2
We can simplify it as -
= 4(2k+1)+2 + 3(k+2)+1
= 42. 42k+1+42. (3k+2 - 3k+2) + 31.3k+2
equal to zero
Taking common factors as 42 and 3k+2 we get
= 42 (42k+1 + 3k+2) + 3k+2 (-42+3)
= 42 (13m) + 3k+2(-13).
equation (1)
P(k + 1) = 13 (42m - 3k+2)
That is multiple of 13, for P(k + 1).
This proves that given integer is multiple of 13.

9
Course Code/Title: CS3401/Theory of Computation

Example 1.4.9 Prove for every n ≥ 1 by mathematical induction Σn i3 = {n(n+1)/2}2.

AU: May-17, Marks 16
Solution:
• Base Case
Assume
n = 1 then
L.H.S. = (1)3 = 1
R.H.S. = [1(1+1) /2]2 = (2/2)2 = 1
As L.H.S. = R.H.S.
Thus the given expression is true for n = 1.
• Inductive Hypothesis
Assume n = k is true
Then 13+23+33 +...+ k3 = [k(k+1) /2]2 is also true, for some k in the set of positive integers.
13+23+33 +...+k3 = [k(k+1) /2]2 …..(1)
• Inductive Step
We will show that if n = k is true then it implies n = k + 1 is also true.
L.H.S. = 13+23+33+ ... + k3+(k+1)3
R.H.S. = [(k+1)(k+2) /2]2
From equation (1)
[k(k+1)3 /2]2 +(k+1)3 = k2(k+1)2 /4 +(k+1)3
= k2(k+1)2 +4(k+1)3 /4
= k2(k2+2k+1)+4(k3 +3k2+3k+1)
= k2(k2 +2k+1)+4k3+12k2 +12k+4 /4
= k4+2k3+k2 +4k3 +12k2 +12k+4
L.H.S. = k4+6k3 +13k2 +12k+4 /4 …..(2)
Now consider R.H.S.
R.H.S. = [(k+1)(k+2) /2]2
= (k+1)2 (k+2)2 /4
= (k2 +2k+1)(k2 +4k+4) /4
= k4+4k3 +4k2 + 2k3 +8k2 +8k+k2 +4k+4 /4

10
Course Code/Title: CS3401/Theory of Computation

R.H.S. = k4 +6k3 +13k2 +12k+4 /4 …..(3)

From equation (2) and equation (3) we get
L.H.S. = R.H.S. is proved for n = k +1
Thus given expression is true.
Finite Automata (FA)
Definition
A finite automata is a collection of 5-tuple (Q, Σ, δ, q0, F) where,
Q is a finite set of states, which is non empty.
Σ is input alphabet, indicates input set.
Q0 is an initial state and q0 is in Q i.e. q0 ϵ Q.
F is a set of final states.
δ is a transition function or a mapping function. Using this function the next state can be determined.
Finite Automata Model
• The finite automata can be represented using
i) Input tape - It is a linear tape having some number of cells. Each input symbol is placed in each cell.
ii) Finite control - The finite control decides the next state on receiving particular input from input tape. The
tape reader reads the cells one by one from left to right and at a time only one input symbol is read. (Refer
Fig. 1.5.1)

• For example: suppose current state is q, and suppose reader is reading the symbol 'a' then it is finite control
which decides what will be the next state at input 'a'. The transition from current state q with input w to next
state q' producing w' will be represented as,
(q, w) Ⱶ (q', w')
If w is a string and M is a finite automata, then w is accepted by the FA
iff (w, s) Ⱶ (q, ε)
with q as final state.

11
Course Code/Title: CS3401/Theory of Computation

• The set of strings accepted by a FA given by M then M is accepted by language L. The acceptance of M by
some language L is denoted by L (M).
• A machine M accepts a language L iff,
L = L (M).
Representation of Finite Automata
The strings and languages can be accepted by a finite automata, when it reaches to a final state. There are
two preferred notations for describing automata :
1. Transition diagram
A transition diagram or transition graph can be defined as collection of –
1) Finite set of states K.
2) Finite set of symbols Σ.
3) A non empty set S of K. It is called start state.

4) A set F K of final states.

5) A transition function K×A →K with K as state and A as input from Σ*

The notations used in transition diagram are -

For example:
The FA can be represented using transition graph. The machine initially is in start state S 0 then on receiving
input 0 it changes to state S1. From S0 receiving input 1 the machine changes its state to S4. The state S2 is a
final state or accept state. When we trace the input for transition diagram and reach to a final state at end of
input string then it is said that the given input is accepted by transition diagram.

12
Course Code/Title: CS3401/Theory of Computation

Another example:

We have drawn a transition diagram for the input aabb.

Note that the start state is S0 and final state is S4. The input set is Σ = {a,b}. The states S1, S2, S3 are all
intermediate states.
2. Transition table
This is a tabular representation of finite automata. For transition table the transition function is used.
For example:

The rows of the table corresponds to states and columns of the table correspond to inputs. Here q0 is start
state, q2 is final state.
Types of Automata

13
Course Code/Title: CS3401/Theory of Computation

There are two types of finite automata -

i) Deterministic Finite Automata.
ii) Non Deterministic Finite Automata.
Deterministic Finite Automata (DFA)
AU: Dec.-07, 10, 11, 13, 16, 19, May-07, 14, Marks 13
The finite automata is called Deterministic Finite Automata if there is only one path for a specific input from
current state to next state. For example, the DFA can be shown in Fig. 1.6.1.

From state S0 for input 'a' there is only one path, going to S2. Similarly from S0 there is only one path for
input b going to S1.
The DFA can be represented by the same 5-tuples described in the definition of FSM.
Definition of DFA
A deterministic finite automation is a collection of following things -
1) The finite set of states which can be denoted by Q.
2) The finite set of input symbols Σ.
3) The start state q0 such that q0 ϵ Q.
4) A set of final states F such that F ϵ Q.
5) The mapping function or transition function denoted by δ. Two parameters are passed to this transition
function: One is current state and other is input symbol. The transition function returns a state which can be
called as next state.
For example, q1 = δ (q0, a) means from current state q0, with input a the next state transition is q1.
In short, the DFA is a five tuple notation denoted as :
A = (Q, Σ, δ, q0, F)
The name of DFA is A which is a collection of above described five elements.

Example 1.6.1 Design a FA which checks whether the given binary number is even.
Solution:

14
Course Code/Title: CS3401/Theory of Computation

• Logic: The binary number is made up of 0's and 1's when any binary number ends with 0 it is always even
and when a binary number ends with 1 it is always odd. For example,
0100 is a even number, it is equal to 4.
0011 is a odd number, it is equal to 3.
• Design: While designing FA we will assume one start state one state ending in 0 and other state for ending
with 1. Since we want to check whether given binary number is even or not, we will make the state for 0, as
the final state. (Refer Fig. 1.6.2)
Simulation: The FA indicates clearly S1 is a state which handles all the 1's and S2 is a state which handles all
the 0's. Let us take some input.

01000 => 0S21000

01S1 000
010S2 00
0100S2 0
01000S2
Another idea to represent FA with the help of transition table.

Example 1.6.2 Design FA which checks whether the given unary number is divisible by 3.
Solution:

15
Course Code/Title: CS3401/Theory of Computation

• Logic :
The unary number is made up of ones. The number 3 can be written in unary form as 111, number 5 can be
written as 11111 and so on.
The unary number which is divisible by 3 can be 111 or 111111 or 111111111 and so on.
• Design

• Simulation
Consider a number 111111 which is equal to 6 i.e. divisible by 3. So after complete scan of this number we
reach to final state q3.
Start 111111
State q0
1q1 11111
11q2 1111
111q3 111
1111q1 11
11111q2 1
111111q3 → Now we are in final state.

Example 1.6.3 Design FA to check whether given decimal number is divisible by three.
Solution:
• Logic :
To determine whether the given decimal number is divisible by three, we need to take the input number digit
by digit.
Also, while considering its divisibility by three, we have to consider that the possible remainders could be 1,
2 or 0. The remainder 0 means, it is divisible by 3. Hence from input set {0, 1, 2, …. 9} (since decimal
number is a input), we will get either remainder 0 or 1 or 2 while testing its divisibility by 3. So we need to
group these digits according to their remainders.

16
Course Code/Title: CS3401/Theory of Computation

The groups are as given below -

remainder 0 group: S0: (0, 3, 6, 9)
remainder 1 group: S1: (1, 4, 7)
remainder 2 group: S2: (2,5,8)
We have named out these states as S0, S1 and S2. The state So will be the final state as it is remainder 0 state.
• Design:

• Simulation:
Let us test the above FA, if the number is 36 then it will proceed by reading the number digit by digit.

Hence the number is divisible 3, isn't it ? Similarly if number is 121 which is not divisible by 3, it will be
processed as
S 121
1 S1 21
17
Course Code/Title: CS3401/Theory of Computation

12 S0 1
121 S1 which is remainder 1 state.

Example 1.6.4 Design FA which checks whether a given binary number is divisible by three.
Solution:
• Logic:
We will consider the input digit by digit.
While considering the divisibility by 3, we should think of three types of states, namely-
remainder 0 i.e. S0 state
remainder 1 i.e. S1 state
remainder 2 i.e. S2 state
• Design:

• Simulation:
Let us take some number 010 which is equivalent to 2. We will scan this number from MSB to LSB.
0 1 0
↑ ↑ ↑
S0 S1 S2
Then we will reach to state S2 which is remainder 2 state. Similarly for input 1001 which is equivalent to 9
we will be in final state after scanning the complete input.
1 0 0 1
↑ ↑ ↑ ↑
S1 S2 S1 S0
Thus the number is really divisible by 3.
We can also represent the simulation in following manner -

18
Course Code/Title: CS3401/Theory of Computation

Consider input 1001

S Ⱶ 001
1 Ⱶ S1 001
10 Ⱶ S2 01
100 Ⱶ S1 1
1001 Ⱶ S0 i.e. ACCEPT state

Example 1.6.5 Consider the finite automata transition table shown below with F = {q0} AU: Dec.-10,
Marks 10

Find the language accepted by the finite automata.

Solution: The transition diagram for the given transition table will be as shown in Fig. 1.6.7.

• The sets accepted by this language are (0011, 00, 11, 1010, 0101, ... }
• This shows that all the strings contain even number of 0's and even number of 1's. Hence the language
accepted by this finite automata contains "all the strings having even number of O's and even number of 1's".

Example 1.6.6 Design FA to accept L, where L = {Strings in which a always appears trippled) over the set Σ
= {a, b}. AU: Dec.-10, Marks 10
Solution:
• Logic: For this particular language the valid strings are aaab, baaaaaa, bbaaab and so on. The a always
appears in a clump of 3.

19
Course Code/Title: CS3401/Theory of Computation

Note that in Fig. 1.6.8 the sequence of tripple a is maintained to reach to the final state.
• Design

Example 1.6.7 Construct a DFA that accepts all the strings on {0, 1} except those containing the substring
101.
AU: May-07, Marks 6, May-14, Marks 8
Solution :
• The simplest method to construct such DFA is to construct DFA for the language containing the substring
101.
• Now just change the non-final states to final states and make final state as non-final state. The DFA then
becomes shown in Fig. 1.6.9.

• is a DFA that does not accept the language containing substring 101.

20
Course Code/Title: CS3401/Theory of Computation

Example 1.6.8 Define DFA. Design a DFA to accept the binary numbers which are divisible by 5.
Solution: i) DFA - Refer section 1.6.
ii) DFA for divisibility by 5: For designing DFA as a divisibility by 5 tester for a binary string we will
consider following states.
q0 - remainder 0 state
q1 - remainder 1 state
q2 - remainder 2 state
q3 - remainder 3 state
q4 - remainder 4 state
Now we will design DFA by considering above states and finding next states with input 0 and 1.
The DFA will be

Simulation: Consider the string (1111)2 = (15)10

q0 Ⱶ 1111
1q1 Ⱶ 111
11q3 Ⱶ 11
111q2 Ⱶ 1
1111q0 Ⱶ
Divisible by 5. q0 is a final state.
21
Course Code/Title: CS3401/Theory of Computation

Consider input string (1110) = (14) 10

q0 Ⱶ 1110
1 q1 Ⱶ 110
11 q3 Ⱶ 10
111 q2 Ⱶ 0
1110 q4 Ⱶ
Remainder 4. q4 is remainder 4 state.
Example 1.6.9 Draw transition diagram for recognizing the set of all operators in C language. AU: Dec.-
07, Marks 10
Solution:
• Logic: In C language there are various operators, such as relational operators bitwise operators and
arithmetic operators. Various relational operators are <, <=, >=, !=, ==. The bitwise operators are &&, ||. Let
us draw the transition diagram for these operators.
• Design:

Example 1.6.10 Construct a DFA accepting all string w over {0, 1}, such that number of 1's in w is 3 mod
4. AU: Dec.-11, Marks 8

22
Course Code/Title: CS3401/Theory of Computation

Solution: The DFA will be

Example 1.6.11 Give deterministic finite automata accepting the following language over the alphabet.
1) Number of 1's is a multiple of 3.
2) Number of 1's is not a multiple of 3. AU: Dec.-13, Marks 8
Solution: 1) We assume alphabet as input set Σ = {1}

2) For recognizing number of 1's not a multiple of 3, we will use the DFA in step (1). That means we will
make non final states as final and final state as non-final ones. The DFA will then be as shown in figure.

Example 1.6.12 Given Σ = (a, b), construct a DFA which recognize the language
L= {bm abn :m,n>0}. AU Dec.-16, Marks 6
Solution:
• The m and n are > 0 and there is no restriction on number of m and n. In other words any number of m and
n are allowed except null.
• Hence we can rewrite given L as
L = b+ ab+
• From this L we can construct DFA as

23
Course Code/Title: CS3401/Theory of Computation

Example 1.6.13 Construct a DFA to accept strings over (a, b), such that every block of length five contains
at least two a's. Use extended transition of function to trace a string W = aabba.
Solution: The following DFA contains block of five symbols. The DFA loops back when the block ends. At
each state both the a and b symbols are considered. The state names indicate the total number of a's so far
visited. For instance if the state name is 1 then it indicates that there is single a being read. When two a's are
read then it leads to a final state. The DFA will be shown in Fig. 1.6.12.

Example 1.6.14 Design a DFA which accept strings of O's and 1's which when interpreted as a binary
integer is multiple of 5. Also give the sequence of states that DFA is in while processing the input string:
1001011.
Solution: The required DFA can be drawn as follows.

Processing of 1001011

24
Course Code/Title: CS3401/Theory of Computation

q0 Ⱶ 1001011
1 q1 Ⱶ 001011
10 q2 Ⱶ 01011
100 q4 Ⱶ 1011
1001 q4 Ⱶ 011
10010 q3 Ⱶ 11
100101 q2 Ⱶ 1
1001011 q0 Ⱶ Accept.

Example 1.6.15 Design a FA for following language

L = {W|W is Binary word of length 4i (where i >= 1) such that each consecutive block of 4 bits contains
atleast 2 0s} = {0000, 0110, 01101100, ...) AU: Dec 19, Marks 13
Solution :

Non-deterministic Finite Automata (NFA)

AU: May-09,12, Marks 8
• The concept of Non-deterministic Finite Automata is exactly reverse of Deterministic Finite Automata. The
Finite Automata is called NFA when there exists many paths for a specific input from current state to next
state. The NFA can be shown as in Fig. 1.7.1
• Note that the NFA shows from q0 for input a there are two next states q1 and q2. Similarly, from q0 for input
b the next states are q0 and q1.

25
Course Code/Title: CS3401/Theory of Computation

• Thus it is not fixed or determined that Fig. 1.7.1 Non-deterministic finite automata with a particular input
where to go next. Hence this FA is called non-deterministic finite automata.

• Consider the input string bba. This string can be derived as

Input b b a
Path q0 q0 q1
Input b b a
Path q0 q0 q2
Input b b a
Path q0 q1 q1
Thus you cannot take the decision of which path has to be followed for deriving the given string.
Definition of NFA
The NFA can be formally defined as a collection of 5-tuples.
1) Q is a finite set of states.
2) Σ is a finite set of inputs.
3) δ is called next state or transition function.
4) q0 is initial state.

5) F is a final state where F Q.

There can be multiple final states. Thus the next question might be what is the use of NFA. The NFA is
basically used in theory of computations because they are more flexible and easier to use than the DFAs.
Difference between NFA and DFA

26
Course Code/Title: CS3401/Theory of Computation

Example 1.7.1 Construct a NFA for a language L which accepts all the strings in which the third symbol
from right end is always a. Over Σ= {a, b}.
Solution:
• Logic: The strings in such a language are of the form

Thus we get third symbol from right end as 'a' always. The NFA then can be
• Design:

The above figure is a NFA because in state q0 with input 'a' we can go to either state q0 or state q1.

Example 1.7.2 Draw state transition diagram for FA over {a, b} containing substring aabb. AU:
May-09, Marks 4
Solution: The FA can be

Example 1.7.3 Construct NFA accepting binary strings with two consecutive 0's. AU: May-12, Marks 8
Solution: For constructing this NFA the input set Σ ={0,1}. The NFA will be -

27
Course Code/Title: CS3401/Theory of Computation

Finite Automata with Epsilon Transitions

• The ɛ-transitions in NFA are given in order to move from one state to another without having any symbol
from input set Σ.
Consider the NFA with ɛ as:

• In this NFA with ε, q0 is a start state with input 0 one can be either in state qo or in state q1. If we get at the
start a symbol 1 then with ε - move we can change state from q0 to q1 and then with input we can be in state
q1.
• On the other hand, from start state q0, with input 1 we can reach to state q2.
• Thus it is not definite that on input 1 whether we will be in state q1 or q2. Hence it is called
nondeterministic finite automata (NFA) and since there are some ε moves by which we can simply change
the states from one state to other. Hence it is called NFA with ε.
Definition of NFA with ε
The language L accepted by NFA with &, denoted by M = (Q, Σ, δ, q0, F) can be defined as:
Let, M = (Q, Σ, δ, q0, F) be a NFA with ε.
Where
Q is a finite set of states.
Σ is input set.
δ is a transition or a mapping function for transitions from Q×{ΣUε} to 2Q.
q0 is a start state.
F is a set of final states such that F ϵ Q.

Example 1.8.1 Construct NFA with ε which accepts a language consisting the strings of any number of a's
followed by any number of b's. Followed by any number of c's.
Solution: Here any number of a's or b's or c's means zero or more in number. That means there can be zero or
more a's followed by zero or more b's followed by zero or more c's. Hence NFA with ε can be -
Normally ε's are not shown in the input string. The transition table can be -

28
Course Code/Title: CS3401/Theory of Computation

We can parse the string aabbcc as follows -

δ (q0, aabbcc) Ⱶ δ (q0, abbcc)
Ⱶ δ (q0, bbcc)
Ⱶ δ (q0, εbbcc)
Ⱶ δ (q1, bbcc)
Ⱶ δ (q1, bcc)
Ⱶ δ (q1, cc)
Ⱶ δ (q1, εcc)
Ⱶ δ (q2, cc)
Ⱶ δ (q2, c)
Ⱶ δ (q2, ε)
Thus we reach to accept state, after scanning the complete input string.
Definition of ε - closure
The ε - closure (p) is a set of all states which are reachable from state p on ε - transitions such that:
i) ε - closure (p) = p where p ϵ Q.
ii) If there exists ε closure (p) = {q} and δ(q,ε) = r then
ε - closure (p) = {q, r}

Example 1.8.2 Find ε - closure for the following NFA with ε.

29
Course Code/Title: CS3401/Theory of Computation

Solution:
ε - closure (q0) = {q0, q1, q2} means self state + ε - reachable states.
ε - closure (q1) = {q1, q2} means q1 is a self state and q2 is a state obtained from q1 with ε input.
ε - closure (q2) = {q2}

Example 1.8.3 Build a non-deterministic FSM with & that accepts

L = {w = {a, b, c)*: w contains at least one string that consists of three identical symbolds in a row). For
example
• The following strings are in L are aabbb, baabbbccc
• The following strings are not in L are ε, aba, abababab, abcbcab.
Solution: The NDFSM with ε is

Equivalence of NFA with ε to NFA without ε

AU May-04, 09, 12, Dec.-09, 12, 13, Marks 12
In this method we try to remove all the ε transitions from given NFA. The method will be
1. Find out all the ε transitions from each state from Q. That will be called as ε-closure {q} where qi ϵ Q.
2. Then δ' transitions can be obtained. The δ' transitions means an ε-closure on δ moves.
3. Step-2 is repeated for each input symbol and for each state of given NFA.
4. Using the resultant states the transition table for equivalent NFA without & can be built.
Theorem: If L is accepted by NFA with ε transitions, then there exist L which is accepted by NFA without ε
transitions. AU May-09, Marks 12; Dec.-09, 13, Marks 8
Proof :
Let, M = (Q, Σ, δ, q0, F) be an NFA with ε transitions.
Construct M' = (Q, Σ, δ', q0, F') where

30
Course Code/Title: CS3401/Theory of Computation

F' = FU{q0} if ε-closure contains state off

F otherwise
M' is a NFA without ε moves. The δ' function can be denoted by δ" with some input. For example, δ' (q, a) =
δ" (q, a) for some q in Q and a from Σ. We will apply the method of induction with input x. The x will not be
ɛ because
δ' (q0, ε) = {q0}
8" (q0, ε) = ε-closure (q0). Therefore we will assume length of string to be 1.
Basis: |x| = 1. Then x is a symbol a.
δ'(q0,a) = δ" (q0,a)
Induction |x| > 1 Let x = wa
8'(q0, w) = δ'(δ'(q0, w), a)
By inductive hypothesis,
δ'(q0, w) = δ" (q0, w) = p
Now we will show that δ' (p, a) = δ (q0, wa)
But
δ'(p, a) = U δ'(q, a) = U δ" (q, a)
q in p q in p
As
p = δ" (q0, w)
We have, U δ" (q, a) = δ" (q0, wa)
q in p
Thus by definition δ"
δ'(q0, wa) = δ" (q0, wa)
Rule for conversion
δ′(q, a) = ε - closure (δ (δ (q, ε), a))
where δ(q,ε) = ε - closure (q)
Before solving some examples based on conversion of NFA with ε to NFA without ɛ above rule should be
remembered.
Subset construction algorithm:
1. Initially ε - closure (q0) is in D states of DFA.
2. While there are unmarked states qi in D states
{
31
Course Code/Title: CS3401/Theory of Computation

3. Marks qi
4. for each symbol a
{
5. U = ε - closure (δ(qi, a))
6. if (U is not in D states)
{
7. Add U as unmarked state in D states.
}
8. Dtran [qi, a] = U
}
}
Example for Understanding
Example 1.9.1 Convert the given NFA with ɛ to NFA without ε. AU: Dec.-09, Marks 8

Solution: Step 1: We will first obtain ε - closure of each state i.e. we will find out ε - reachable states from
current state.
Hence
ε - closure (q0) = {q0, q1, q2}
ε - closure (q1) = {q1, q2}
ε - closure (q2) = {q2}
As ε - closure (q0) means with null input (no input symbol) we can reach to q0, q1 or q2. In a similar manner
for q1 and q2 ε - closures are obtained.
Step 2: Now we will obtain δ' transitions for each state on each input symbol.
δ' (q0, 0) = ε - closure (δ (δ' (q0, ε), 0))
= ε - closure (δ(ε - closure(q0), 0))
= ε - closure (δ(q0, q1, q2), 0).
= ε - closure (δ(q0, 0) U δ(q1, 0) U δ (q2,0))
= ε - closure (q0 U ϕ U ϕ)
= ε - closure (q0) = {q0, q1, q2}

32
Course Code/Title: CS3401/Theory of Computation

δ' (q0, 1) = ε - closure (δ (δ`(q0,ε), 1))

= ε - closure (δ (q0, q1, q2), 1)
= ε - closure (δ (q0, 1) U δ (q1, 1) U δ (q2,1))
= ε closure (ϕ U q1 U ϕ)
= ε - closure (q1)
δ' (q0, 1) = {q1, q2}
δ' (q1,0) = ε - closure (δ (δ`(q1,ε), 0))
= ε - closure (δ (ε - closure (q1), 0))
= ε closure (δ (q1,q2), 0)
= ε closure (δ (q1, 0) U δ (q2, 0))
= ε closure (ϕUϕ)
= ε - closure (ϕ)
=ϕ
δ' (q1, 1) = ε - closure (δ (δ` (q1, ε), 1))
= ε - closure (δ (ε - closure (q1), 1))
= ε - closure (δ (q1, q2), 1)
= ε - closure (δ (q1, 1) U δ (q2, 1))
= ε - closure (q1 U ϕ)
= ε - closure (q1)
= {q1, q2}
δ′(q2, 0) = ε- closure (δ (δ` (q2, ε), 0))
= ε - closure (δ (ε - closure (q2), 0))
= ε - closure (δ (q2, 0))
= ε - closure (ϕ)
=ϕ
δ ' (q2, 1) = ε - closure (δ (δ` (q2, ε), 1))
= ε closure (δ (ε - closure (q2), 1))
= ε - closure (δ (q2,1))
= ε - closure (ϕ)
δ' (q2, 1) = ϕ
δ' (q0, 2) = ε - closure (δ (δ` (q2, ε), 2))
33
Course Code/Title: CS3401/Theory of Computation

= ε - closure (δ (ε -closure (q0), 2))

= ε - closure (δ (q0, q1, q2), 2).
= ε - closure (δ (q0, 2) U δ (q1, 2) U δ (q2, 2))
= ε - closure (q2)
= ε - closure (q2)
= {q2}
δ' (q1,2) = ε - closure (δ (δ` (q1, ε), 2))
= ε - closure (δ (ε - closure (q1), 2))
= ε - closure (δ (q1, q2), 2)
= &- closure (δ (q1, 2) U δ (q2, 2))
= ε closure (ϕ U q2)
= {q2}
δ′ (q2, 2) = ε - closure (δ (δ` (q2, ε), 2))
= ε - closure (δ (ε - closure (q2), 2))
= ε - closure (δ (q2, 2))
= ε - closure (q2)
= {q2}
Now we will summarize all the computed δ' transitions -
δ'(q0, 0) = {q0, q1, q2}, δ'(q0, 1) = {q1, q2), δ'(q0, q2) = {q2}
δ'(q1, 0) = ϕ δ'(q1, 1) = {q1, q2}, δ'(q1, 2) = {q2}
δ'(q2, 0) = ϕ δ'(q2, 1) = ϕ δ'(q2, 2) = {q2}
Step 3:
From this we can write the transition table as -

Step 4:
34
Course Code/Title: CS3401/Theory of Computation

The NFA will be,

Here q0, q1 and q2 is a final state because ε closure (q0), ε - closure (q1) and ε - closure (q2) contains final state
q2.

Example 1.9.2 Convert the following NFA with e to NFA without ε.

Solution: We will first obtain ε - closure of every state. The ɛ - closure is basically an ε - transition from one
state to other. Hence
ε - closure (0) = {0}
ε - closure (1) = {1}
ε - closure (2) = {2, 3, 4, 6, 9}
ε - closure (3) = {3, 4, 6}
ε - closure (4) = {4}
ε - closure (5) = {5, 8, 3, 4, 6, 9}
= {3, 4, 5, 6, 8, 9} sorted it!
ε - closure (6) = {6}
ε - closure (7) = {7, 8, 3, 4, 6, 9}
= {3, 4, 6, 7, 8, 9}

35
Course Code/Title: CS3401/Theory of Computation

ε - closure (8) = {8, 3, 4, 6, 9}

= {3, 4, 6, 8, 9}
ε - closure (9) = {9}
Now we will obtain δ' transitions for each state and for each input symbol.
δ' (0, a) = ε - closure (δ (δ` (0, ε), a))
= ε - closure (δ (ε - closure(0), a))
= ε - closure (δ (0, a))
= ε - closure (1)
{1}
δ ' (0, b) = ε - closure (δ (δ` (0,ε), b))
= ε - closure (δ (ε - closure (0), b))
= ε - closure (δ (0, b))
= ε - closure (ϕ)
=ϕ
δ' (1,a) = ε - closure (δ (δ` (1,ɛ), a))
= ε - closure (δ (ε - closure (1), a))
= ε - closure (δ (1, a))
= ε - closure (ϕ)
=ϕ
δ ' (1, b) = ε - closure (8 (8 (1,ε), b))
= ε - closure (δ (ε - closure (1), b))
= ε - closure (δ (1, b))
= ε - closure (2)
= {2, 3, 4, 6, 9}
δ ' (2, a) = ε - closure (δ (δ` (2,ε), a))
= ε - closure (δ (ε - closure (2), a))
= ε - closure (δ (2, 3, 4, 6, 9), a)
= ε - closure (δ (2, a) U δ (3, a) U δ (4, a) U δ (6, a) U δ (9, a))
= ε - closure (ϕ U ϕ U 5 U ϕ U ϕ )
= ε - closure (5)
= {3, 4, 5, 6, 8, 9}
36
Course Code/Title: CS3401/Theory of Computation

δ' (2, b) = ε - closure: (δ (δ (2, ε), b))

= ε - closure (δ (ε - closure (2), b))
= ε - closure (δ (2, 3, 4, 6, 9), b)
= ε - closure (δ(2, b) U δ(3, b) U δ(4, b) U δ(6, b) U δ(9, b))
= ε - closure (ϕ U ϕ U ϕ U 7 U ϕ)
= ε - closure (7)
= {3, 4, 6, 7, 8, 9}
δ'(3, a) = ε - closure (δ (δ'(3,ε), a))
= ε - closure (δ (ε - closure (3), a))
= ε - closure (δ (3, 4, 6), a).
= ε - closure (δ (3, a) U δ (4, a) U δ (6, a))
= ε - closure (ϕ U 5 U ϕ)
= ε - closure (5)
= {3, 4, 5, 6, 8, 9}
δ`(3, b) = ε - closure (δ (δ`(3, ε), b))
= ε - closure (δ (ε - closure (3), b))
= ε - closure (δ (3, 4, 6), b)
= ε - closure (δ (3, b) U δ (4, b) U δ (6, b))
= ε - closure (ϕ U ϕ U 7)
= ε - closure (7)
= {3, 4, 6, 7, 8, 9}
δ` (4, a) = ε - closure (δ (δ` (4, ε), a))
= ε - closure (δ (ε - closure (4), a))
= ε - closure (δ (4, a))
= ε - closure (5)
= {3, 4, 5, 6, 8, 9}
δ`(4, b) = ε - closure (δ (δ` (4, ε), b))
= ε - closure (δ (ε - closure (4, b))
= ε - closure (δ (4, b))
= ε - closure (ϕ)
=ϕ
37
Course Code/Title: CS3401/Theory of Computation

δ ' (5, a) = ε - closure (δ (δ`(5, ε), a))

= ε - closure (δ (ε - closure (5), a))
= ε - closure (δ (3, 4, 5, 6, 8, 9), a)
= e-closure (δ (3, a) U (4, a) U δ (5, a) U δ (6, a) U δ (8, a) U δ (9,a))
= ε - closure (ϕ U 5 U ϕ U ϕ U ϕ U ϕ U ϕ)
= ε - closure (5)
= {3, 4, 5, 6, 8, 9}
δ' (5, b) = ε - closure (δ (δ`(5, ε), b))
= ε - closure (δ (ε - closure (5), b))
= ε - closure (δ (3, 4, 5, 6, 8, 9), b)
= ε - closure (δ (3, b) U δ (4, b) U δ (5, b) U δ (6, b) U δ (8, b) U δ (9, b))
= ε - closure (ϕ U ϕ U ϕ U 7 U ϕ U ϕ)
= ε - closure (7)
= {3, 4, 6, 7, 8, 9}
δ' (6, a) = ε - closure (δ (δ` (6, ɛ), a))
= ε - closure (δ (ε - closure (6), a))
= ε - closure (δ (6, a))
= ε - closure (ϕ)
=ϕ
8' (6, b) = ε - closure (δ (δ (6, ɛ), b))
= ε - closure (δ (ε - closure (6), b))
= ε - closure (δ (6, b))
= ε - closure (7)
= {3, 4, 6, 7, 8, 9}
δ' (7, a) = ε - closure (δ (δ`(7, ε), a))
= ε - closure (δ (ε - closure (7), a))
= ε - closure (δ (3, 4, 6, 7, 8, 9), a)
= ε - closure (δ (3, a) U δ (4, a) U δ (6, a) U δ (7, a) U δ (8, a) U δ (9, a))
= ε - closure (ϕ U 5 U ϕ U ϕ U ϕ U ϕ)
= ε - closure (5)
= {3, 4, 5, 6, 8, 9}
38
Course Code/Title: CS3401/Theory of Computation

δ ' (7, b) = ε - closure (δ (δ` (7, ε), b))

= ε - closure (δ (ε - closure (7), b))
= ε - closure (δ (3, 4, 6, 7, 8, 9), b)
= ε - closure (δ (3, b) U δ (4, b) U δ (6, b) U δ (7, b) U δ (8, b) U δ (9, b))
= ε - closure (ϕ U ϕ U 7 U ϕ U ϕ U ϕ)
= ε - closure (7)
= {3, 4, 6, 7, 8, 9}
δ' (8, a) = ε - closure (δ (δ`(8, ε), a))
= ε - closure (δ (ε - closure (8), a))
= ε - closure (δ (3, 4, 6, 8, 9), a)
= ε - closure (δ (3, a) U δ (4, a) U δ (6, a) U δ (8, a) U δ (9, a))
= ε - closure (ϕ U 5 U ϕ U ϕ U ϕ)
= ε - closure (5)
= {3, 4, 5, 6, 8, 9}
δ' (8, b) = ε - closure (δ (δ` (8, ε), b))
= ε - closure (δ (ε - closure (8), b))
= ε - closure (δ (3, 4, 6, 8, 9), b)
= ε - closure (δ (3, b) U δ (4, b) U δ (6, b) U δ (8, b) U δ (9, b))
= ε - closure (ϕ U ϕ U 7 U ϕ U ϕ)
= ε - closure (7)
= {3, 4, 6, 7, 8, 9}
δ' (9, a) = ε - closure (δ (δ` (9, ε), a))
= ε - closure (δ (ε - closure (9), a))
= ε - closure (δ (9, a))
= ε - closure (ϕ)
=ϕ
δ' (9, b) = ε - closure (δ (δ` (9, ε), b))
= ε - closure (δ (ε - closure (9), b))
= ε - closure (δ (9, b))
= ε - closure (ϕ)
=ϕ
39
Course Code/Title: CS3401/Theory of Computation

Now we will build the transition table using above calculated δ' transitions.

State {2} is a final state since ε - closure (2) contains 9 which is actually a final state in given NFA. Similarly
state 5, 7, 8 and 9 are final states.
Example 1.9.3 Convert the following NFA with & to NFA without ɛ.

Solution: We will first obtain & - closures of q0, q1 and q2 as follows.

ε - closure (q0) = {q0}
ε - closure (q1) = {q1, q2}
ε - closure (q2) = {q2}
Now the δ' transitions on each input symbol is obtained as,
8' (q0, a) = ε - closure (δ (δ` (q0, ε), a))
= ε - closure (δ (ε - closure (q0), a))
= ε - closure (δ (q0, a))
= ε - closure (q1)
= {q1, q2}

40
Course Code/Title: CS3401/Theory of Computation

δ' (q0, b) = ε - closure (δ (δ` (q0, ε), b))

= ε - closure (δ (ε - closure (q0), b))
= ε - closure (δ (q0, b)).
=ϕ
δ' (q1, a) = ε - closure (δ (δ` (q1, ε), a))
= ε - closure (δ (ε - closure (q1), a))
= ε - closure (δ (q1, q2), a)
= ε - closure (δ (q1, a) U δ (q2, a))
= ε - closure (ϕ U ϕ)
=ϕ
δ' (q1, b) = ε - closure (δ (δ` (q1, ε), b))
= ε - closure (δ (ε - closure (q1), b))
= ε - closure (δ (q1, q2), b)
= ε - closure (δ (q1, b) U δ (q2, b))
= ε - closure (q2)
= ε - closure (q2)
= {q2}
δ' (q2, a) = ε - closure (δ (δ` (q2, ε), a))
= ε - closure (δ (ε - closure (q2), a))
= ε - closure (δ (q2, a))
= ε - closure (ϕ)
=ϕ
δ' (q2, b)
= ε - closure (δ (δ`(q2, ε), b))
= ε - closure (δ (ε - closure (q2), b))
= ε - closure (δ (q2, b))
= ε - closure (q2)
= {q2}
The transition table can be –

41
Course Code/Title: CS3401/Theory of Computation

States q1 and q2 becomes the final as closures of q1 and q2 contains the final state q2. The NFA can be shown
by transition diagram as shown in Fig. 1.9.5.

Example 1.9.4 Convert the given NFA with ɛ to ordinary NFA.

Solution: We will first obtain ε - closure of each state.

ε - closure (q0) = {q0, q1, q2}
ε - closure (q1) = {q1, q2)
ε - closure (q2) = {q2}
Now &' transitions for each state on each input.
8' (q0, a) = ε - closure (δ (δ` (q0, ε), a))
= ε - closure (δ (ε - closure (q0), a))
= ε closure (δ ((q0, q1, q2), a))
= ε closure (δ (q0, a) U δ (q1, a) U δ (q2, a))
= ε - closure (ϕ U q1 U q1).
= ε - closure (q1)
= (q1, q2)

42
Course Code/Title: CS3401/Theory of Computation

δ' (q0, b) = ε - closure (δ (δ` (q0, ε), b))

= ε closure (δ (ε - closure (q0), b))
= ε - closure (δ ((q0, q1, q2), b))
= ε - closure (δ (q0, b) U δ (q1, b) U δ (q2, b))
= ε - closure (q0 U ϕ U q0)
= ε - closure (q0)
= (q0, q1, q2)
δ' (q1, a) = ε - closure (δ (δ` (q1, ε), a))
= ε - closure (δ (ε - closure (q1), a))
= ε - closure (δ ({q1, q2), a))
= ε - closure (δ (q1, a) U δ (q2, a))
= ε - closure (q1 U q1)
= ε - closure (q1)
= {q1, q2}
δ' (q1, b) = ε - closure (δ (δ` (q1, ε), b))
= ε - closure (δ (ε - closure (q1), b))
= ε - closure (δ (q1, q2), b))
= ε - closure (δ (q1, b) U δ (q2, b))
= ε closure (ϕ U q0)
= {q0, q1, q2}
δ' (q2, a) = ε - closure (δ (δ` (q2, ε), a))
= ε - closure (δ (ε - closure (q2), a))
= ε - closure (δ (q2, a))
= ε - closure (q1)
= (q1, q2)
δ' (q2, b) = ε - closure (δ (δ` (q2, ε), b))
= ε closure (δ (ε - closure (q2), b))
= ε - closure (δ (q2, b))
= ε - closure (q0)
= {q0, q1, q2}
The transition table can be –
43
Course Code/Title: CS3401/Theory of Computation

Example 1.9.5 Construct an NFA without ε transitions for the NFA given in Fig. 1.9.7. AU May-12,
Marks 8

Solution: We will first obtain ε - closures of q0 and q1 as follows -

ε - Closure (q0) = {q0, q1}
ε - Closure (q1) = {q1}
Now δ' transitions on each input symbol is obtained as -
δ'(q0, 0) = ε - Closure (δ (δ` (q0, ε), 0))
= ε - Closure (δ (ε - Closure (q0), 0))
= ε - Closure (δ ((q0, q1), 0))
= ε - Closure (q0)
δ' (q0, 0) = {q0, q1}
δ' (q0, 1) = ε - Closure (δ (δ` (q0, ε), 1))
= ε - Closure (δ (ε - Closure (q0), 1))
= ε - Closure (8 ((q0, q1), 1))
= ε - Closure (q1)
δ' (q0, 1) = {q1}
δ' (q1, 0) = ε - Closure (δ (δ` (q1, ε), 0))
= ε - Closure (δ (ε - Closure (q1), 0))
= ε - Closure (δ (q1, 0))
= ε - Closure (ϕ)
δ' (q1, 0) = ϕ
δ' (q1, 1) = ε - Closure (δ (δ` (q1, ε), 1))
= ε - Closure (δ (ε - Closure (q1), 1))
44
Course Code/Title: CS3401/Theory of Computation

= ε - Closure (δ (q1, 1))

= ε - Closure (q1)
δ' (q1, 1) = {q1}
The transation table for NFA without & will be,

The transition diagram will be -

Review Question
1. If L is accepted by a NFA with & transition then show that L is accepted by an NFA without ε transition.
AU: May-04, Dec.-09, Marks 8; May-09, Marks 12, Dec.-12, Marks 8
Equivalence of NFA and DFA
AU: May-05,12,13,14,16,18, Dec.-04,06,14,15,16,19, Marks 13
NFA can be converted to equivalent DFA. Following theorem illustrates this concept.
Theorem: Let L be a set accepted by non-deterministic finite automation. Then there exists a deterministic
finite automation that accepts L.
OR
Prove that "A language L is accepted by some DFA if and only if L is accepted by some NFA". AU: Dec.-15,
Marks 10, AU: May-05, Dec.-14, Marks 10
Proof :Let
M = (Q, Σ, δ, q0, F) be an NFA for language L. Then define DFA M' such that,
M' = (Q', Σ`, δ', q0`, F')
The states of M' are all the subset of M'. The Q'=2Q.
F' be the set of all the final states in M.
The elements in Q' will be denoted by [q1, q2, q3, ... qi] and the elements in Q are denoted by {q0, q1, q2,
… }The [q1, q2, ... qi] will be assumed as one state in Q' if in the NFA q0 is a initial state it is denoted in DFA
as q0` = [q0]. We define,
δ' ([q1, q2, q3, … qi], a) = [P1, P2, P3, ... Pj]

45
Course Code/Title: CS3401/Theory of Computation

if and only if,

8({q1, q2 ,q3, ....qi}, a) = {P1, P2, P3, …. Pj}
This means that whenever in NFA, at the current states (q1, q2, q3, ...qi} if we get input a and it goes to the
next states [P1, P2, ... Pj} then while constructing DFA for it the current state is assumed to be [q1, q2, q3, …
qi, a]. At this state, the input is a and the next is assumed to be [P1, P2, ... Pj]. On applying δ function on each
of the states q1, q2, q3, ...qi the new states may be any of the states from [P1, P2, ... Pj]. The theorem can be
proved with the induction method by assuming length of input string x
δ' (q0, x) = [q1, q2, ... qi].
if and only if,
δ (q0, x) = {q1, q2, q3, ... qi}
Basis: If length of input string is 0
i.e. |x| = 0, that means x is ε then q0` = [q0]
Induction: If we assume that the hypothesis is true for the input string of length m or less than m. Then if x a
is a string of length m+1. Then the function δ' could be written as,
δ' (q0, xa) = δ' (δ' (q0, x), a)
δ' (q0, x) = [P1, P2, … Pj]
if and only if,
δ (q0, x) = {P1, P2, P3, ... Pj}
By definition of δ'
δ' ([P1, P2, … Pj], a) = [r1, r2, .... rk]
if and only if,
δ ({P1, P2, … Pj} a) = {r1, r2, ... rk}
Thus
δ' (q0, x a) = [r1, r2, .... rk]
if and only if
δ (q0, x a) = {r1, r2, ... rk}
is shown by inductive hypothesis.
Thus L (M) = L (M')
With the help of this theorem, let us try to solve few examples.
Conversion from NFA to DFA
We will discuss the method of converting NFA to its equivalent DFA.
Let, M = (Q, Σ, δ, q0, F) is a NFA which accepts the language L(M). There should be equivalent DFA
denoted by M' = (Q', Σ`, δ', q0`, F') such that L(M) = L(M').
46
Course Code/Title: CS3401/Theory of Computation

The conversion method will follow following steps -

1) The start state of NFA M will be the start for DFA M'. Hence add q0 of NFA (start state) to Q'. Then find
the transitions from this start state.
2) For each state [q1, q2, q3, ... qi] in Q' the transitions for each input symbol Σ can be obtained as,
i) δ' ([q1,q2 ...qi], a) = δ (q1, a) U δ (q2, a) U .........(qi, a)
= [q1, q2, …. qk ] may be some state.
ii) Add the state [q1, q2, .... qk] to DFA if it is not already added in Q'.
iii) Then find the transitions for every input symbol from Σ for state [q1, q2, ....,qk ]. If we get some state [q1,
q2, ... qn ] which is not in Q' of DFA then add this state to Q`.
iv) If there is no new state generating then stop the process after finding all the transitions.
3) For the state [q1, q2, …. qn] ϵ Q' of DFA if any one state qi is a final state of NFA then [q1, q2,......qn ]
becomes a final state. Thus the set of all the final states ϵ F' of DFA.
Example 1.10.1 Determine the DFA from a given NFA.
M = ((q0, q1), (a, b), δ, q0, {q1}) with the state table diagram for δ given below.

AU Dec.-16, Marks 10, May-18, Marks 13

Solution: Let the DFA M'= (Q', Σ, δ ', q0, F')
Now, the δ' function will be computed as follows -
As δ (q0, 0) = {q0, q1} δ` ([q0], 0) = [q0, q1]
As in NFA the initial state is q0, the DFA will also contain the initial state [q0].
Let us draw the transition table for δ function for a given NFA.

From the transition table we can compute that there are [q0], [q1], [q0, q1] states for its equivalent DFA. We
need to compute the transition from state [q0, q1].
47
Course Code/Title: CS3401/Theory of Computation

δ ({q0, q1},0) = δ (q0, 0) U δ (q1, 0)

= {q0, q1} U ϕ
= {q0, q1}
So, δ' ([q0, q1], 0) = [q0, q1]
Similarly,
δ' ({q0, q1}, 1) = δ (q0,1) U δ (q1,1)
= {q1} U {q0, q1}
= {q0, q1}
So, δ' ([q0, q1], 1) = [q0, q1]
As in the given NFA q1 is a final state, then in DFA wherever q1 exists that state becomes a final state. Hence
in the DFA final states are [q1] and [q0, q1]. Therefore set of final states F = {[q1], [q0, q1]}

We can even change the names of the states of DFA.

A = [q0]
B = [q1]
C= [q0, q1]
With these new names the DFA will be as in Fig. 1.10.2.

Example 1.10.2 Construct DFA equivalent to the NFA

M = ((p, q, r), (0, 1), δ, p {q, s}) Where & is defined in the following table.
48
Course Code/Title: CS3401/Theory of Computation

AU: Dec.-04, Marks 8

Solution: To construct DFA,
δ {p, 0} = {q, s} new state generated
δ {p, 1} = {q}
δ {q, 0} = {r}
δ {q, 1} = {q, r} new state
δ {r, 0} = {s}
δ (r, 1) = {p}
δ (s, 0} = -
δ {s, 1} = {p}
δ {{q, s}, 0} = {r}
δ {{q, s}, 1} = {p, q, r} new state
8 {{q, r), 0} = {r, s} new state
δ {{q, r}, 1} = {p, q, r}
δ {{p, q, r}, 0} = {q, r, s} new state
δ {{p, q, r}, 1} = {p, q, r}
δ {{r, s), 0} = {s}
δ {{r, s), 1} = {p}
δ {{q, r, s}), 0} = {r, s}
δ {{q, r, s), 1} = {p, q, r}
The transition table is as shown below.

49
Course Code/Title: CS3401/Theory of Computation

Example 1.10.3 Construct DFA equivalent to the given NFA.

AU: Dec.-06, Marks 8, Dec.-19, Marks 13

Solution: The NFA M = {{p, q, r, s}, {0, 1}, δ (p), {s}}
The equivalent DFA will be constructed.

Continuing with the generated new states.

50
Course Code/Title: CS3401/Theory of Computation

The final state F' = { [s], [p, q, r, s], [p, q, s], [p, r, s], [p, s] }
The transition graph shows two disconnected parts. But part I will be accepted as final DFA because it
consists of start state and final states, in part II there is no start state. Refer Fig. 1.10.3 (See Fig. 1.10.3 on
next page):
Example 1.10.4 Convert the following NFA to a DFA . AU: May-13, Marks 10

51
Course Code/Title: CS3401/Theory of Computation

Solution: We will apply δ transitions on each state for each input.

δ ([p], a) = [p]
δ ([p], b) = {p, q} = [p, q] → new state
δ ([q], a) = [r]
δ ([q], b) = [r]
δ ([r], a) = ϕ
δ ([r], b) = ϕ
The 8 transition on newly generated states
δ ([p, q], a) = {p, r} = [p, r] → new state
δ ([p, q], b) = {p, q, r) = [p, q, r] → new state
δ ([p, r], a) = {p} U ϕ = [p]
δ ([p, r], b) = {p, q} U i.e. [p, q]
δ ([p, q, r], a) = {p} U {r} U ϕ = [p, r]
δ ([p, q, r], b) = {p, q} U {r} U ϕ = {p, q, r} i.e. [p, q, r]
As no new state is getting generated in above transitions, the transition table can be constructed as follows -

52
Course Code/Title: CS3401/Theory of Computation

Assuming [p] as start state and [r] as final state

The states [p, r] and [p, q, r] are final states as they contain [r].
The DFA can be represented by the transition diagarm as shown -

The states [q] and [r] are eliminated as they are dead states.
Example 1.10.5 Construct a DFA accepting binary strings such that the third symbol from the right end is
1. AU May-12, Marks 10
Solution: The strings in such a language are -

The NFA will be,

The transition table can be –

53
Course Code/Title: CS3401/Theory of Computation

We will obtain the δ transitions on each input and state.

δ (q0, 0) = [q0]
δ (q0, 1) = [q0, q1] i.e. [q0, q1] → New state
δ (q1, 0) = [q2], δ (q1, 1) = [q2]
δ (q2, 0) = [qf], δ (q2, 1) = [qf]
δ ([q0, q1], 0) = {q0, q2}, = [q0, q2] i.e. New state
δ ([q0, q1], 1) = {q0, q1, q2} = [q0, q1, q2] → New state
δ ([q0, q2], 0) = {q0, qF} = {q0, qf} → New state
δ ([q0, q2], 1) = {q0, q1, 9f} = [q0, q1, qf] → New state
δ ([q0, q1, q2], 0) = {q0, q2, qf} → New state
δ ([q0, q1, q2], 1) = {q0, q1, q2, qf } → New state
δ ([q0, qf], 0) = [q0]
δ ([q0, qf], 1) = [q0, q1]
δ ([q0, q1, qf], 0) = [q0, q2]
δ ([q0, q1, qf], 1) = [q0, q1, q2]
δ ([q0, q2, qf], 0) = [q0, qf]
δ ([q0, q2, qf], 1) = [q0, q1, qf]
δ ([q0, q1, q2, qf], 0) = [q0, q2, qf]
δ ([q0, q1, q2, qf], 1) = [q0, q1, q2, 9f]
The transition table for above computation is as given below -
The states q1, q2 and qf are not reachable states. Hence they can be eliminated.

54
Course Code/Title: CS3401/Theory of Computation

Example 1.10.6 Construct a non-deterministic finite automaton accepting the set of strings over {a,b}
ending in aba. Use it to construct a DFA accepting the same set of strings. AU: May-14, Marks 10
Solution: NFA for accepting the strings ending with aba is,

The transition table will be

We will obtain 8 transitions for each input on each state.

δ (q0, a) = {q0, q1} = [q0, q1] new state.

55
Course Code/Title: CS3401/Theory of Computation

δ (q0, b) = {q0}
δ (q1, a) = ϕ
δ (q1, b) = {q2}
δ (q2, a) = {q3}
δ (q2, b) = ϕ
δ (q3, a) = ϕ
δ (q3, b) = ϕ
The δ transitions on newly generated states is
δ ([q0, q1], a) = {q0, q1} i.e. [q0, q1]
δ ([q0, q1], b) = {q0, q2} = [q0, q2] new state
δ ([q0, q2], a) = {q0, q1, q3} = [q0, q1, q3] new state
δ ([q0, q2], b) = {q0}
δ ([q0, q1, q3], a) = [q0, q1]
δ ([q0, q1, q3], b) = [q0, q2]
As no new state is getting generated. We will build transition table is as follows -

The DFA will be as shown in Fig. 1.10.5

The states q1, q2 and q3 are non-reachable. Hence they will be eliminated.
Example 1.10.7 Construct a DFA equivalent to the NFA. M=({a, b, c, d}, {0,1} δ, a {b, d}) where δ is a
defined as AU Dec.-14, Marks 6

56
Course Code/Title: CS3401/Theory of Computation

Solution: Refer similar example 1.10.2 by assuming p = a, q=b, r = c and s = d.

Example 1.10.8 Construct NFA that accepts all string that end in 01. Give its transition table and extended
transition function for the input string 00101. Also construct a DFA for the above NFA using subset
construction method. AU May-16, Marks 10
Solution: The NFA will be designed using
r.e. = (0+1)* 01

The transition table will be as follows:

Refer example 1.10.6 for conversion of NFA to DFA.

Review Question
1. Prove that "A language L is accepted by some DFA if and only if L is accepted by some NFA". AU
Dec.-15, Marks 10
Equivalence of NFA with ε to DFA
AU: May-05, 11, Dec.-06,13,15,18, Marks 16
Prove that there exists a DFA for every ε - NFA.
AU: May-11, Marks 8
Step 1: Consider M = (Q, Σ, δ, q0, F) is a NFA with ε. We have to convert this NFA with ε to equivalent DFA
denoted by

57
Course Code/Title: CS3401/Theory of Computation

MD = (QD, Σ, δD, q0, FD)

Then obtain,
ε - closure (q0) = {P1, P2, P3... Pn} then [P1, P2, P3 ,... Pn] becomes a start state of DFA.
Now [P1, P2, P3... Pn] ϵ QD
Step 2: We will obtain δ transitions on [P1, P2, P3, ... Pn ] for each input.
δD ([P1, P2, Pn], a) = ε - closure (δ (P1, a) U δ (P2, a) U... δ (Pn, a))
= Uni=1 ε - closure d (Pi, a)
where a is input ϵ Σ.
Step 3: The states obtained [P1, P2, P3, ... Pn] ϵ QD. The states containing final state Pi is a final state in DFA.
Now let us see some examples of conversion based on this procedure.
Example 1.11.1 Convert the following NFA with ε to equivalent DFA.

Solution:
Step 1: To convert this NFA we will first find ɛ-closures.
ε - closures {q0} = {q0, q1, q2}
ε - closures {q1} = {q1, q2}
ε - closures {q2} = {q2}
Step 2: Let us start from ε - closure of start state
ε - closure {q0} = {q0, q1, q2} we will call this state as A.
Now let us find transitions on A with every input symbol.
δ (A, a) = ε-closure (δ (A, a))
= ε - closure (δ (q0, q1, q2), a)
= ε - closure {(q0, a) U δ (q1, a) U δ (q2, a)}
= ε - closure {q1}
= {q1, q2). Let us call it as state B.
δ (A, b) = ε-closure (δ (A, b))
= ε - closure (δ (q0, q1, q2), b)

58
Course Code/Title: CS3401/Theory of Computation

= ε - closure {δ (q0, b) U δ (q1, b) U δ (q2, b)}

= ε - closure {q0}
= {q0, q1, q2} i.e. A.
Hence we can state that,
δ' (A, a) = B
δ` (A, b) = A
Step 3: Now let us find transitions for state B = {q1, q2}
δ' (B, a) = ε - closure (δ (q1, q2), a)
= ε - closure {q1}
= {q1, q2} i.e. B
δ` (B, b) = ε - closure (δ ( q1, q2), b)
= ε - closure {δ (q1, b) U δ (q2, b)}
= ε - closure {q0}
= (q0, q1, q2) i.e. A.
Step 4: Hence the generated DFA is

Example 1.11.2 Convert the given NFA into its equivalent DFA -

Solution: Let us obtain ε - closure of each state.

ε - closure (q0) = {q0, q1, q2}
ε - closure (q1)= {q1, q2}
ε - closure (q2) = {q2}
Now we will obtain d' transition. Let e-closure (q0) = {q0, q1, q2} call it as state A.
δ' (A, 0) = ε - closure { δ ((q0, q1, q2), 0)}
= ε - closure {δ (q0, 0) U δ (q1, 0) U δ (q2, 0)}
59
Course Code/Title: CS3401/Theory of Computation

= ε - closure {q0}
= {q0, q1, q2} i.e. state A
δ' (A, 1) = ε - closure { δ ((q0, q1, q2), 1)}
= ε - closure {(q0,1) U δ (q1,1) U δ (q2,1)}
= ε - closure {q1, q2}
= {q1, q2} Call it as state B
δ' (A, 2) = ε - closure {δ ((q0, q1, q2), 2)}
= ε - closure {δ (q0, 2) U δ (q1, 2) U δ (q2, 2)}
= ε - closure {q2}
= {q2} Call it as state C.
Thus we have obtained,
δ` (A, 0) = A
δ` (A, 1) = B
δ` (A,2) = C
i.e.
Now we will find transitions on states B and C for each input.

Hence,
δ' (B, 0) = ε - closure {δ (q1, q2), 0}
= ε - closure {δ (q1, 0) U δ (q2, 0)}
= ε - closure {ϕ}
=ϕ
δ' (B, 1) = ε - closure {δ (q1, q2), 1}
= ε - closure {δ (q1, 1) U δ (q2, 1)}
= ε - closure {q1}

60
Course Code/Title: CS3401/Theory of Computation

= {q1, q2) i.e state B itself.

δ` (B, 2) = ε - closure {δ (q1, q2), 2}
= ε - closure {δ (q1, 2) U δ (q2, 2)}
= ε - closure {q2}
= {q2} i.e state C.
Hence,
δ` (B, 0) = ϕ
δ` (B, 1) = B
δ` (B, 2) = C

The partial transition diagram will be,

Now we will obtain transitions for C:
δ` (C, 0) = ε - closure {δ (q2, 0)}
= ε - closure {ϕ}
=ϕ
δ` (C, 1) = ε - closure {δ (q2, 1)}
= ε - closure {ϕ}
=ϕ
δ` (C,2) = ε - closure {δ (q2, 2)}
= q2

61
Course Code/Title: CS3401/Theory of Computation

Hence the DFA is,

As A = {q0, q1, q2} in which final state q2 lies hence A is final state in B = {q1, q2} the state q2 lies hence B is
also final state in C = {q2}, the state q2 lies hence C is also a final state.
Example 1.11.3 Consider following NFA with ε.
AU: May-11, Marks 6

Convert it to its equivalent DFA.

Solution: We will first compute ε - closure for start state p.
ε closure (p) = {p} call it as state A.
Now we will obtain 8 transitions on state A.

State A
62
Course Code/Title: CS3401/Theory of Computation

δ' (A, a) = ε - closure (δ (A, a))

= ε - closure (δ (p, a))
= ε - closure (p)
= {p} i.e. state A only.
δ' (A, b) = ε - closure (δ (A, b))
= ε - closure (δ (p, b))
= ε - closure (q)
= {q, p} i.e. {p, q} Let us call it state B.
δ' (A, b) = B
δ' (A, c) = ε - closure (δ (A, c))
= ε - closure (δ (p, c))
= ε - closure (r) = {q, r} Call it as state C.
State B = {p, q}
δ' (B, a)
= ε - closure (δ (B, a))
= ε - closure (δ (p, q), a)
= ε - closure (δ (p, a) U δ (q, a))
= ε - closure (p U q)
= ε - closure (p, q)
= ε - closure(p) Ụ ɛ - closure(q)
= {P} U {q} = {p, q} i.e. state B only.
δ' (B, a) = B.
δ' (B, b) = ε - closure (δ (B, b))
= ε - closure (δ (p, q), b)
= ε - closure (δ (p, b) U δ (q, b))
= ε - closure (q U r)
= ε - closure (q, r)
δ' (B, b) = ε - closure(q) U ε - closure(r)
= {p, q} U {q, r} = {p, q, r} i.e. state D
δ`(B, b) = D.
δ' (B, c) = ε - closure (δ (B, C))
63
Course Code/Title: CS3401/Theory of Computation

= ε - closure (δ (p, q), c)

= ε - closure (δ (p, c) U δ (q, c))
= ε - closure (r U ϕ)
= ε - closure (r)
= {q, r}
δ' (B, c) = C
State C = {q, r}
δ' (C, a) = ε - closure (δ (C, a))
= ε - closure (δ (q, r), a)
= ε - closure (δ (q, a) U δ (r, a))
= ε - closure (q U r)
= ε - closure (q) U ε - closure(r)
= {p, q} U {q, r}
= (p, q, r) i.e. state D.
δ' (C, a) = D
8' (C, b) = ε - closure (δ (C, b))
= ε - closure (δ (q, r), b)
= ε - closure (δ (q, b) U δ (r, b)).
= ε - closure (r U ϕ)
= ε - closure (r)
= {q, r) i.e. state C.
δ' (C, b) = C
δ' (C, c) = ε - closure (δ (C, c))
= ε - closure (δ (q, r), c)
= ε - closure (δ (q, c) U δ (r, c))
= ε - closure (ϕ U p)
= ε - closure (p)
= {p} i.e. state A.
δ' (C, c) = A
State D = {p, q, r}
δ' (D, a) = ε - closure (δ (D, a))
64
Course Code/Title: CS3401/Theory of Computation

= ε - closure (δ (p, q, r), a)

= ε - closure (δ (p, a) U δ (q, a) U δ (r, a))
= ε - closure (p U q U r)
= ε - closure (p) U ɛ - closure(q) U ε - closure (r)
= (p, q, r) i.e. state D.
δ ' (D, a) = D
8' (D, b) = ε - closure (δ (D, b))
= ε - closure (δ (p, q, r), b)
= ε - closure (δ (p, b) U δ (q, b) U δ (r, b))
= ε - closure (q U r U ϕ)
= ε - closure (q, r)
= ε - closure (q) U ε - closure (r)
= (p, q, r) i.e. state D.
δ' (D, b) = D
δ' (D, c) = ε - closure (δ (D, c))
= ε - closure (δ (p, q, r), c)
= ε - closure (δ (p, c) U δ (q, c) U δ (r, c))
= ε - closure (r U ϕ U p)
= ε - closure (r) U ε - closure (p)
= {q, r} U {P}
= {p, q, r} i.e. state D.
δ' (D, c) = D
The transition table from above calculations can be obtained as,

65
Course Code/Title: CS3401/Theory of Computation

As state A = {p} it is a start state and states C and D contain final state r, hence these are final states. The
transition diagram for the DFA is,

Example 1.11.4 Consider the following ε - NFA for an identifier. Consider the ε -closure of each state and
find it's equivalent DFA. AU: Dec.-15, Marks 10
Solution:
ε - closure (1) = {1} Call it as state A
δ' (A, letter) = ε - closure(δ (1, letter)
= ε - closure(2)
= {2, 3, 4, 5, 8, 10} Call it as state B
δ' (A, letter) = B
δ' (A, digit) = ε - closure(δ (1, digit))
=ϕ
δ' (A digit) = ϕ
δ' (B, letter) = ε - closure(δ (2, 3, 4, 5, 8, 10), letter)
= ε – closure (6)
= {6, 7, 4, 5, 8, 10) i.e.
= {4, 5, 6, 7, 8, 10} Call it as state C
δ' (B, letter) = C
δ' (B, digit) = ε - closure(&(2, 3, 4, 5, 8, 10), digit)
= ε – closure (9)
= {9, 7, 4, 5, 8, 10} i.e.
= {4, 5, 7, 8, 9, 10} Call it as state D
δ' (B, digit) = D
δ' (C, letter) = ε - closure(δ (4, 5, 6, 7, 8, 10), letter)

66
Course Code/Title: CS3401/Theory of Computation

= ε – closure (6)
=C
δ' (C, letter) = C
δ' (C, digit) = ε - closure(δ (4, 5, 6, 7, 8, 10), digit)
= ε – closure (9)
=D
δ' (C, digit) = D
δ' (D, letter) = ε - closure(δ (4, 5, 7, 8, 9, 10), letter)
= ε - closure (6)
=C
δ' (D, letter) = C
δ' (D, digit) = ε - closure(δ (4, 5, 7, 8, 9, 10), digit)
= ε - closure (9)
=D
δ' (D, digit) = D

The two states C and D are equivalent. Similarly state B and C are equivalent
B = C = D.
The minimized DFA will then be

Example 1.11.5 Convert the following ε - NFA to NFA and then convert the resultant NFA to DFA.
AU Dec.-18, Marks 13

67
Course Code/Title: CS3401/Theory of Computation

Solution: Conversion of NFA to NFA

We will obtain ɛ - closure of each state
ε - closure (A) = {A, B, C}
ε - closure (B) = {B, C}
ε - closure (C) = {C}
ε - closure (D) = {D}
Now we will obtain δ' transitions for each state on each input symbol.
δ' (A, 0) = ε - closure (δ (ε - closure(A), 0))
= ε - closure (δ ((A, B, C), 0))
= ε - closure (δ (A, 0) U δ (B, 0), U δ (C,0))
= ε - closure (ϕ U ϕ U ϕ)
=ϕ
δ' (A, 0) = ϕ
δ' (A, 1) = ε - closure (δ (ε - closure(A), 1))
= ε - closure (δ (A, B, C), 1)
= ε - closure (A, D, C)
= ε - closure (A) U ε - closure (D) U ε - closure (C)
= {A, B, C, D}
δ' (A, 1) = {A, B, C, D}
δ' (B, 0) = ε - closure (δ (ε - closure (B), 0))
= ε - closure (δ (B, C), 0)
δ' (B, 0) = ϕ
δ' (B, 1) = ε - closure (δ (ε - closure (B), 1))
= ε - closure (δ ((B, C), 1)
= ε - closure (D, C)

68
Course Code/Title: CS3401/Theory of Computation

= ε - closure (D) U ε - closure(C)

=DUC
= {D, C}
δ' (B, 1) = {D, C}
δ' (C, 0) = ε - closure(δ (ε - closure(C), 0)
= ε - closure (δ (C, 0)
= ε - closure (ϕ)
δ' (C, 0) = ϕ
δ' (C, 1) = ε - closure (δ (ε - closure (C), 1)
= ε - closure (δ (C, 1)
= ε - closure (C)
= {C}
δ' (C, 1) = C
δ' (D, 0) = ε closure (δ (ε - closure(D), 0))
= ε - closure (δ (D, 0)
= ε - closure (B)
δ' (D, 0) = (B, C)
δ' (D, 1) = ε - closure (8 (e-closure(D), 1))
= ε - closure (δ (D, 1)
= ε - closure (ϕ)
δ' (D, 1) = ϕ
The transition table will be

The NFA will be:

69
Course Code/Title: CS3401/Theory of Computation

Conversion of NFA to DFA

δ (A, 0) = 0
δ (A, 1) = {A, B, C, D} → call it as state P
δ (A, 1) = p
δ (P, 0) = P
= δ ((A, B, C, D), 0)
= δ (A, 0) U δ (B, 0) U δ (C, 0) U δ (D, 0)
{B, C} → call it as state Q
S (P, 0) = Q
δ (P, 1) = δ ((A, B, C, D), 1)
= δ (A, 1) U δ (B, 1) U δ (C, 1) U δ (D, 1)
= {A, B, C, D}
δ (P,1) = P
δ (Q, 0) = δ ((B, C,), 0)
= δ (B, 0) U δ (C, 0)
δ (Q, 0) = ϕ
δ (Q, 1) = ((B, C), 1)
= δ (B, 1) U δ (C, 1)
= {C, D} U {C}
= {C, D} → call it as state R
δ (Q, 1) = R
δ (R, 0) = {δ (C, D), 0}
= {B, C}
δ (R, 0) = Q
δ (R, 1) = δ ((C, D), 1)

70
Course Code/Title: CS3401/Theory of Computation

δ (R, 1) = {C}
δ (C, 0) = ϕ
δ (C, 1) = C
The transition table will be

Review Questions
1. Let L be a set accepted by NFA then prove that there exists a deterministic finite automaton that accepts L.
Is the converse true? AU: May-05, Marks 10
2. Prove that a language L is accepted by some ε - NFA if and only if L is accepted by some DFA. AU: Dec.-
06, Marks 8
3. Prove the equivalence of NFA and DFA using subset construction. AU: Dec.-13, Marks 8
Minimization of DFA
AU Dec.-18, May-13, 14, 16, Marks 10
The minimization of FSM means reducing the number of states from given FA. Thus we get the FSM with
redundant states after minimizing the FSM.
While minimizing FSM we first find out which two states are equivalent we can represent those two states
by one representative state.
71
Course Code/Title: CS3401/Theory of Computation

The two states q1 and q2 are equivalent if both δ (q1, x) and δ (q2, x) are final states or both of them are non
final states for all x ϵ Σ* (Σ* indicate any string of any length) we can minimize the given FSM by finding
equivalent states.
Example 1.12.1 Minimize the DFA as given below. AU May-16, Marks 8

Solution :
We will build the transition table for given DFA, as follows:

Step 1: We will build a table in following format for finding equivalent states and mark final and non-final
states with x

72
Course Code/Title: CS3401/Theory of Computation

Step 2: The states that need to be marked are (A, B), (A, D), (A, E), (A, F), (A, G), (A, H), (B, D), (B, E),
(B, F), (B, G), (B, H), (D, E), (D, F), (D, G), (D, H), (E, F), (E, G), (E, H), (F, G), (F, H), (G, H).
If we observe transition table then
δ (B, 0) = G
δ (B, 1) = C
δ (H, 0) = G
δ (H, 1) = C
Similarly
δ (D, 0) = C
δ (D, 1) = G
δ (F, 0) = C
δ (F, 1) = G
Thus pairs (B, H) and (D, F) are equivalent
Step 3:

Step 4:
Now, consider pair (A, E)
73
Course Code/Title: CS3401/Theory of Computation

Pair (A, E) is equivalent

Step 5: i) Pair (A, B)
δ (A, 0) = B δ (A, 1) = F → Final, Non Final states
δ (B, 0) = G δ (B, 1) = C → Final, Non Final states
Pair (A, B) is not equivalent
ii) Pair (A, D)

Pair (A, F) is not equivalent.

iv) Pair (A, G)
δ (A, 0) = B δ (A, 1) = F
δ (G, 0) = G δ (G, 1) = E
To decide equivalence of pair (A, G) we need to find equivalence of pair (B, G) and (E, F)
δ (B, 0) = G δ (B, 1) = C → Final, Non-Final pair
δ (G, 0) = G δ (G, 1) = E → Final, Non Final pair
Pair (B, G) is not equivalent. Similarly we find pair (E, F) and ultimately pair (A, G) are not equivalent.
v) Pair (A, H)
δ (A, 0) = B δ (A, 1) = F → Final, Non-Final pair
δ (H, 0) = G δ (H, 1) = C → Final, Non-Final pair

74
Course Code/Title: CS3401/Theory of Computation

Pair (A, H) is not equivalent

Step 6: In this way, we find pairs (A, E), (B, H) and (D, E) are only equivalent pairs and all other remaining
pairs are not equivalent.

Thus we get equivalent pairs as (A, E), (B, H), (D, F). Hence the minimized DFA will be,

Example 1.12.2 Minimize the

75
Course Code/Title: CS3401/Theory of Computation

AU Dec.-18, Marks 7
Solution: We will construct table as follows
We will mark final and non-final state by x

Now we will find the equivalence of the pairs (3, 4), (3, 5), (3, 6), (4, 5), (4, 6),(5, 6),
Pair (3, 4)
δ (3, a) = 6 δ (3, b) = 7 → Final, Non Final Pair
δ (4, a) = 5 δ (4, b) = 4 → Final, Non Final Pair
Hence put x in (3, 4)
Pair (3, 5)

76
Course Code/Title: CS3401/Theory of Computation

δ (3, a) = 6 δ (3, b) = 7 → Final, Non Final Pair

δ (5, a) = 7 δ (5, b) = 5 → Final, Non Final Pair
Hence put x in (3, 5)
Pair (3, 6)
δ (3, a) = 6 δ (6, a) = 2 → Final, Non Final Pair
δ (3, b) = 7 δ (6, b) = 7
Hence put x in (3, 6)
Pair (4, 5)
δ (4, a) = 5 δ (5, a) = 7 → Final, non final pair
δ (4, b) = 4 δ (5, b) = 5
Hence put x in (4, 5)
Pair (4, 6)

Pair (5, 6)
δ (5, a) = 7 δ (5, b) = 5 → Final, Non Final Pair
δ (6, a) = 2 δ (6, b) = 7 → Final, Non Final Pair
Hence put x in (5, 6)
Thus we do not get any of the mentioned pairs as equivalent pair.
The only equivalent pairs are (1, 2), (1, 7), (2, 7)
We assume state 1 = 2 = 7. We eliminate state 2 and 7 by replacing them by 1.
The minimized DFA can be given by following transition table.

77
Course Code/Title: CS3401/Theory of Computation

But, since state 4 and 5 are not reachable from start state 1, we eliminate them. Also, state 6 is a dead state.
Hence, minimizes DFA is

Example 1.12.3 Define distinguishable and indistinguishable states. Using table filling method, minimize the
following DFA. Draw the transition diagram of resulting DFA.

78
Course Code/Title: CS3401/Theory of Computation

Solution: Distinguishable and indistinguishable states: If for some input string w, δ (p w) gives an accepting
state and δ (q, w) gives a non-accepting state or vice versa then states p and q are called distinguishable
states or non-equivalent states.
If for some input string w, δ (p, w) and δ (q, w) both produces either accepting states or non-accepting states,
then states p and q are called indistinguishable or equivalent states.
We will apply a table filling method for minimizing the given DFA.

We will mark X in a final and non-final pairs. Now we will consider each pair and check for its equivalence
consider pair G, H.
δ (G, 0) = H and δ (G, 1) = B
δ (H, 0) = I and δ (H, 1) = C
Since pairs (H, I) and (B, C) are already marked X, pair (G, H) is not equivalent so we will mark X in pair
(G, H).

79
Course Code/Title: CS3401/Theory of Computation

Now, consider pair (E, H),

δ (E, 0) = F and δ (E, 1) = I
δ (H, 0) = I and δ (H, 1) = C
As (F, I) and (I, C) both are final states, hence pair (E, H) is said to be equivalent and we won't put X in the
pair (E, H).
Now, consider pair (E, G),
δ (E, 0) = F and δ (E, 1) = I
δ (G, 0) = H and δ (G, 1) = B
As pairs (F, H) and (I, B) have X, we put X in (E, G).
Consider pair (E, F),
δ (E, 0) = F and δ (E, 1) = I
δ (F, 0) = G and δ (F, 1) = B
Put X in pair (E, F). Hence table will be

80
Course Code/Title: CS3401/Theory of Computation

Consider pairs (D, H), (D, G), (D, F), (D, E) out of which
δ (D, 0) = E and δ (D, 1) = H
δ (H, 0) = I and δ (H, 1) = C
Hence put X in (D, H),
δ (D, 0) = E δ (D, 1) = H
δ (G, 0) = H δ (G, 1) = B
Pair (E, H) is equivalent. For pair (H, B) we will find their input transitions. Both state H and state B yield
final states we say pair (D, G) is equivalent at the same time we find pair (H, B) as equivalent.
δ (D, 0) = E and δ (D, 1) = H
δ (F, 0) = G and δ (F, 1) = B
As pair (E, G) is having X we will put X in (D, F).
Consider pair (D, E),
δ (D, 0) = E δ (D, 1) = H
δ (E, 0) = F δ (E, 1) = I
Pair (D, E) is not matching, put X in (D, E).
Consider pair (B, G),
δ (B, 0) = C δ (B, 1) = F
δ (G, 0) = H δ (G, 1) = B
As pair (C, H) is not equivalent put X in (B, G).
Consider pair (B, F),
δ (B, 0) = C δ (B, 1) = F
δ (F, 0) = G δ (F, 1) = B
81
Course Code/Title: CS3401/Theory of Computation

As pair (C, G) is having X, we put X in (B, F).

Consider pair (B, E),
δ (B, 0) = C δ (B, 1) = F
δ (E, 0) = F δ (E, 1) = I
As (C, F) and (F, I) are both final states we say pair (B, E) is equivalent.
Consider pair (D, B),
δ (B, 0) = C δ (B, 1) = F
δ (D, 0) = E δ (D, 1) = H
As pair (E, C) have X, we put X in pair (D, B).
Consider pair (A, H),
δ (A, 0) = B δ (A, 1) = E
δ (H, 0) = I δ (H, 1) = C
As X is in pair (B, I) we put X in (A, H).
Consider pair (A, G),
δ (A, 0) = B δ (A, 1) = E
δ (G, 0) = H δ (G, 1) = B
As pairs (B, H) and (B, E) are equivalent.
We can say pair (A, G) is equivalent.
Consider pair (A, E),
δ (A, 0) = B δ (A, 1) = E
δ (E, 0) = F δ (E, 1) = I
As (B, F) have X we will put X in (A, E) pair (A, D) is already equivalent.
Consider pair (A, B),
δ (A, 0) = B δ (A, 1) = E
δ (B, 0) = C δ (B, 1) = F
As pair (B, C) have X, we will put X in (A, B).
Hence finally table will be,

82
Course Code/Title: CS3401/Theory of Computation

The blank entries represent equivalent states

State A = G = D
State B = H = E
State C = I = F
Hence reduced DFA will be,

Example 1.12.4 Minimize the Finite automaton Fig. 1.12.2 below and show both the given and the reduced
one are equivalent.

83
Course Code/Title: CS3401/Theory of Computation

AU May-14, Marks 10
Solution: We will first construct the transition table for given DFA -

Now we will partition the states Q in Q10 and Q20. The state q4 is a final state. Hence
Q10= F = {q4}
Q20 = Q – Q10 = {q0, q1, q2, q3)
П0 = {{q4}, {q0, q1, q2, q3}}
Now we will compare q0 with q1. We find that under 0 column we get q1 and q2. And q1 and q2 lie in the same
set i.e. Q2. But under 1-column of q0 and q1 we get q3, q4 respectively. But q3 ϵ Q20 and q4 ϵ Q10. Hence they
are not 1- equivalent.
Similarly compare q0 and q2. We will find that under 0 column of q0 and q2 we get q1 only. But under 1-
column of q0 and q2 we get q3 and q4. The q3 ϵ Q2 and q4 ϵ Q1.
Hence q0 and q2 are not 1 - equivalent. Similarly q0 is not 1 - equivalent to q3 because of 1 column entries.

84
Course Code/Title: CS3401/Theory of Computation

Q'1 = {q4}
Q'2 = {q0}
Q'3 = {q1, q2, q3}
Hence, II1 = {{q4}, {q0}, {q1, q2, q3}}
Now in set (q1, q2, q3) we compare q1 with q2 under 0-column we get q2 and q1 which are in the same set, and
under 1 - column we get q4. And for state q1 and q3 we get same entries under 0 column and under 1 -
column. Hence we can group them {q2, q3}.
The equivalence class becomes,
П2 = {{q4}, {q0}, {q1}, {q2, q3}}
Now further we cannot partition any of the set. We get
П3 = {{q0}, {q2}, {q4}, {q1, q3}}

Review Question
1. Discuss on the relation between DFA and minimal DFA. AU: May-13, Marks 6

85
Course Code/Title: CS3401/Theory of Computation

Two Marks Questions with Answers

Q.1 List any four ways of theorem proving.
Ans. : 1) Proof by contradiction.
2) Proof by contrapositive.
3) Proof by counter example.
4) Proof by principle of mathematical induction.
Q.2 Differentiate between proof by contradiction and proof by contrapositive. AU: May-11
Ans. The difference between proof by contradiction and contrapositive

Q.3 Define automata.

Ans.: Automata are the kind of machines which take some string as input. This input goes through a finite
number of states and may enter in the final state.
Q.4 List the applications of automata theory.
Ans.: 1. Automata theory is the base for the formal languages and these formal languages are useful of the
programming languages.
2. Automata theory plays an important role in compiler design.
3. To prove the correctness of the program automata theory is used.
4. In switching theory and design and analysis of digital circuits automata theory is applied.
5. Automata theory deals with the design finite state machines.
Q.5 What is structural induction? AU: Dec.-11
Ans.: Structural induction is a kind of proof by induction. It is used to prove that there exists a relationship
between some function of integers and a given formula. For this proof technique -
1. Prove the pattern is true for smallest number we care about.
2. Assume it holds for an arbitrary number n.

86
Course Code/Title: CS3401/Theory of Computation

3. Prove that if it is true for n, then it must be true for n + 1, as well.

Q.6 How does recursive function solves Fibonacci function ?
Ans.: Following recursive formula is used to solve Fibonacci function.
Fib(n) = Fib(n - 1) + Fib(n - 2)
Fib(0) = 0 and Fib(1) = 1
For example, to compute Fib(4)

Q.7 What is induction principle? Give an example. AU: Dec.-12

Ans.: The proof by mathematical induction can be carried out using following steps –
1. Basis: In this step we assume the lowest possible value. This is an initial step in the proof of mathematical
induction.
For example, we can prove that the result is true for n = 0 or n = 1.
2. Induction Hypothesis: In this step we assign value of n to some other value k. That mean we will check
whether the result is true for n = k or not.
3. Inductive Step: In this step, if n = k is true then we check whether the result is true for n k+ 1 or not. If we
get the same result at n = k + 1 then we can state that given proof is true by principle of mathematical
induction.
Q.8 What is the proof by contradiction? AU: May-12
Ans.: In proof by contradiction technique, for the statement of the form if A then B we start with statement A
is not true and thus by assuming this false A we try to get the conclusion of statement B. When it becomes
impossible to reach to statement B, then we contradict ourselves and accept that A is true.
Q.9 Define NFA with ε transition. Is the NFA's with ε transitions more powerful than the NFA's without ε
transitions? AU: May-05, 18
Ans.: The NFA can be formally defined as a collection of 5 tuples.
Q is a finite set of states.
Σ is a finite set of inputs.

87
Course Code/Title: CS3401/Theory of Computation

δ is called next state or transition function.

q0 is initial state.

F is a final state where F Q.

No. The NFA with e transitions are equivalent to the NFA without ε transitions.
Q.10 Construct a finite automata for the language {0n | n mod 3 = 2, n ≥ 0}. AU: Dec.-06
Ans.: While testing divisibility by 3 we group the input as

q0 remainder 0 state.
q1 remainder 1 state.
q2 remainder 2 state.
The q2 is remainder 2 state hence we will make it as final state.
Q.11 What is a finite automation? Give two examples. AU: May-07, Dec.-15, 17
Ans.: A finite automation is a collection of 5-tuples (Q, Σ, δ, q0, F) where
• Q is a finite set of states, which is a non-empty one.
• Σ is input alphabet, indicates input set.
• q0 in Q is the initial state.
• F is a set of final states.
• δ is a transition function.
For example -
1. The FA which accepts only those strings which start with 1 and end with 0.

2. The FA which accepts the only input 101.

88
Course Code/Title: CS3401/Theory of Computation

Q.12 Enumerate the differences between DFA and NFA. AU: May-07,14, Dec.-17, 18
Ans. :

Q.13 Construct a DFA over Σ = (a, b) which produces not more than 3a's. AU: May-08
Ans.: In the given language at the most 3a's are allowed and there is no restriction on number of b's. Such a
DFA can be as shown in Fig. 1.13.4.

The above DFA accepts {ε, a, aa, aaa, ab, aba,...}. The states q0, q1, q2 and q3 are final states but state q4 is a
non-final state. Thus the above DFA accepts 3a's and not more than that.
Q.14 Define the languages described by NFA and DFA. AU: Dec.-08
[Refer sections 1.6 and 1.7
• The finite automata is called Deterministic Finite Automata if there is only one path for a specific input
from current state to next state. For example, the DFA can be shown in Fig. 1.6.1.

89
Course Code/Title: CS3401/Theory of Computation

• The concept of Non-deterministic Finite Automata is exactly reverse of Deterministic Finite Automata. The
Finite Automata is called NFA when there exists many paths for a specific input from current state to next
state. The NFA can be shown as in Fig. 1.7.1

Q.15 Construct deterministic finite automata to recognise odd number of 1's and even number of zero's. AU:
May-10
Ans. :

Q.16 Construct a DFA for the language over {0, 1}* such that it contains "000" as a substring. AU : May-11
Ans.:

90
Course Code/Title: CS3401/Theory of Computation

Q.17 Construct a DFA for the following:

a) All strings that contain exactly 4 - zeros.
b) All strings that don't contain the substring 110. AU: Dec.-11
Ans. a) The DFA will be

b) For required DFA, we will first create a DFA that contains the substring 110.

Now change non-final state to final state and final state to non-final state.

Q.18 Find the set of strings accepted by the finite automata. AU: Dec.-10

Ans.: Set of strings accepted by given finite automata are

S = {ε, 0, 1, 00, 000, 11, 111, 01, 10, 101, 110, 001, ...)
Q.19 Define a) Finite Automaton (FA) b) Transition diagram. AU: Dec.-12
Ans.: a) Finite Automaton (FA): Refer answer of Q.11.
Ans.: A finite automation is a collection of 5-tuples (Q, Σ, δ, q0, F) where
• Q is a finite set of states, which is a non-empty one.
• Σ is input alphabet, indicates input set.
• q0 in Q is the initial state.
• F is a set of final states.

91
Course Code/Title: CS3401/Theory of Computation

• δ is a transition function.
b) Transition diagram: A transition diagram can be defined as collection of -
1) Finite set of states K
2) Finite set of symbols
3) A non empty set S of K which is called start state.

4) A set F K of final states.

5) A transition function K × A → K with K state and A as input from Σ*.
Q.20 What is meant by DFA ? [Refer section 1.6] AU: May-13
The finite automata is called Deterministic Finite Automata if there is only one path for a specific input from
current state to next state. For example, the DFA can be shown in Fig. 1.6.1.

From state S0 for input 'a' there is only one path, going to S2. Similarly from S0 there is only one path for
input b going to S1.
The DFA can be represented by the same 5-tuples described in the definition of FSM.
Q.21 Define the term epsilon transition. AU: May-13
Ans.: In the non deterministic finite state machine, the transition that does not require input symbols for state
transition and is capable of transiting to zero or more states with & is called epsilon transition.
Q.22 What is a non deterministic finite automation? [Refer section 1.7] AU: Dec.-13
• The concept of Non-deterministic Finite Automata is exactly reverse of Deterministic Finite Automata.
The Finite Automata is called NFA when there exists many paths for a specific input from current state to
next state. The NFA can be shown as in Fig. 1.7.1
• Note that the NFA shows from q0 for input a there are two next states q1 and q2. Similarly, from q0 for
input b the next states are q0 and q1.
• Thus it is not fixed or determined that Fig. 1.7.1 Non-deterministic finite automata with a particular input
where to go next. Hence this FA is called non-deterministic finite automata.

92
Course Code/Title: CS3401/Theory of Computation

Q.23 Draw the transition diagram (automata) for an identifier. AU: Dec.-13
Ans. :

Q.24 Define deductive proof. AU Nov.-14

Ans.: The deductive proof consists of sequence of statements given with logical reasoning in order to prove
the first or initial statements. The initial statement is called hypothesis.
Q.25 Design DFA to accept strings over Σ = (0,1) with two consective O's. AU: Nov.-14
Ans.:

Q.26 Define Deterministic Finite Automata (DFA). AU: Dec.-16,19

Ans.:
The Deterministic Finite Automata is a collection of following things:
1) Finite set of states - Q
2) Finite set of input symbols - Σ
3) The start state q0 such that q0 ϵ Q.
4) The set of final states F such that F ϵ Q
5) The mapping function δ.
The DFA is denoted by,
M = (Q, Σ, δ, q0, F).

93
Course Code/Title: CS3401/Theory of Computation

Q.27 Draw a non-deterministic automata to accept a string containing substring 0101. AU: May-16
Ans.:

Q.28 Obtain the DFA equivalent to the following NFA. AU: Dec.-03

Ans.: The transition table for given NFA can be drawn as follows.

To construct equivalent DFA.

δ (q0, 0) = {q0, q1} a new state
δ {q0, 1} = {q0}
δ {q1, 1) = -
δ (q1, 1} = {q2}
δ {q2, 0} = -
δ {q2, 1} = -
δ {{q0, q1), 0} = {q0, q1}
δ {{q0, q1), 1} = {q0, q2} a new state
δ {{q0, q2}, 0} = {q0, q1}
δ {{q0, q2}, 1} = {q0}
Hence the DFA is

94
Course Code/Title: CS3401/Theory of Computation

The transition diagram can be drawn as follows.

Q.29 Obtain the NFA without ε transition to the following NFA with ε transition. AU: Dec.-03

Ans.: Remove ε transition from q0 to q1.

Now remove ε transition from q0 to q2.

As q0 to q2 is ε transition q0 will become start and final state both.

Q.30 Obtain the ε - closure of states q0 and q1 in the following NFA with ε transition. AU: Dec.-04

95
Course Code/Title: CS3401/Theory of Computation

Ans.: ε - closure {q0} = {q0, q1, q2}

ε - closure {q1} = {q1, q2}
These are ε - reachable states from q0 and q1.
Q.31 Obtain ε - closure of each state in the following NFA with ε move. AU: Dec.-05
Ans.: The ε - closure of each state means collection of ε - reachable states.

ε - closure (q0) = {q0, q1, q2} as we have ε transition from q0 to q0, q1, q2.
ε - closure (q1) = {q1, q2}
ε - closure {q2} = {q2}
Q.32 Find the language accepted by the DFA given below. AU: May-06

Ans.: The regular expression for this DFA is

r.e. = 1*00*1 (0+1)*
= 1*0*1 (0+1)*
That means this is a language containing all the strings which consist of atleast one single pair of 01.
Q.33 Find the closure of the states 1, 2 and 4 in the following transition diagram. AU: May-06

96
Course Code/Title: CS3401/Theory of Computation

Ans.: ε - closure {1} = {1, 2, 3, 6, 4}

ε - closure {2} = {2, 3, 6}
ε - closure {4} = {4}
Q.34 Define ε - closure.
Ans.: The ε - closure (p) is a set of all states which are reachable from state p on ε - transitions such that:
i) ε - closure (p) = p where p ϵ Q.
ii) If there exists ε - closure (p) = {q} and δ (q, ε) = r then
ε - closure (p) = {q, r}
Q.35 Define ε - closure (q) with an example. AU: May-12
Ans. Definition: Refer answer of Q.34.
Ans.: The ε - closure (p) is a set of all states which are reachable from state p on ε - transitions such that:
i) ε - closure (p) = p where p ϵ Q.
ii) If there exists ε - closure (p) = {q} and δ (q, ε) = r then
ε - closure (p) = {q, r}
Example: Refer answer of Q.31.
Ans.: The ε - closure of each state means collection of ε - reachable states.

ε - closure (q0) = {q0, q1, q2} as we have ε transition from q0 to q0, q1, q2.
ε - closure (q1) = {q1, q2}
ε - closure {q2} = {q2}

97
Course Code/Title: CS3401/Theory of Computation

UNIT II: Regular Expressions and Languages

Syllabus
Regular expression - Regular Languages- Equivalence of Finite Automata and regular expressions Proving
languages to be not regular (Pumping Lemma) - Closure properties of regular languages.

Regular Expression and Regular Languages

AU May-13, 16, Marks 8
Let Σ be an alphabet which is used to denote the input set. The regular expression over Σ can be defined as
follows.
1. ϕ is a regular expression which denotes the empty set.
2. ε is a regular expression and denotes the set {ε} and it is a null string.
3. For each 'a' in Σ 'a' is a regular expression and denotes the set {a}.
4. If r and s are regular expressions denoting the languages L1 and L2 respectively, then
r+s is equivalent to L1 U L2 i.e. union.
rs is equivalent to L1 L2 i.e. concatenation
r* is equivalent to L1* i.e. closure.
The r* is known as kleen closure or closure which indicates occurrence of r for ∞ number of times.
For example if Σ = {a} and we have regular expression R = a*, then R is a set denoted by R= {ε, a, aa, aaa,
aaaa, ...}
That is R includes any number of a's as well as empty string which indicates zero number of a's appearing,
denoted by & character.
Similarly there is a positive closure of L which can be shown as L+. The L+ denotes set of all the strings
except the ε or null string. The null string can be denoted by ε or ^ If Σ = {a} and if we have regular
expression R = a+ then R is a set denoted by
R = {a, aa, aaa, aaaa, ....)
We can construct L* as
L* = ε L +
Let us try to use regular expressions with the help of some examples.
Definition of Regular Language: A language is regular if it can be expressed in terms of regular expression.
Example 2.1.1 Design regular expression for the language containing all the strings containing any number
of a's and b's.
Solution: The regular expression will be
r.e. = (a + b)*
This will give the set as L = {ε, a, aa, ab, b, ba, bab, abab, ..... any combination of a and b}.
98
Course Code/Title: CS3401/Theory of Computation

The (a + b)* means any combination with a and b even a null string.
Example 2.1.2 Write r.e. to denote a language L which accepts all the strings which begin or end with either
00 or 11.
Solution: The r.e. can be categorized into two subparts.
R = L 1 + L2
L1 = The strings which begin with 00 or 11.
L2 = The strings which end with 00 or 11.
Let us find out L1 and L2.
L1 = (0011) (any number of O's and 1's)
L1 = (0011) (0+1)*
Similarly,
L2 = (any number of 0's and 1's) (00 + 11)
= (0+1)* (00 + 11)
Hence
R = [(00+11) (0+1)*] + [(0+1)* (00+11)]
Example 2.1.3 Write the r.e. to denote the language L over Σ = {a, b} such that all the strings do not contain
the substring "ab".
Solution: The L = {ε, a, b, bb, aa, ba, baa ...)
The r.e. = (b* a*)
In this regular expression if we substitute a* = ε we get all combination of b's and similarly if we substitute
b* = ε then we will get all combinations of a's. We have strictly maintained a condition for not to have ab as
substring by giving the regular expression as b* a*.
Example 2.1.4 What is regular expression? Write a regular expression for set of strings that consists of
alternating 0's and 1's. AU May-16, Marks 8
Solution: Regular expression - Refer section 2.1.
Regular Expression
Let Σ be an alphabet which is used to denote the input set. The regular expression over Σ can be defined as
follows.
1. ϕ is a regular expression which denotes the empty set.
2. ε is a regular expression and denotes the set {ε} and it is a null string.
3. For each 'a' in Σ 'a' is a regular expression and denotes the set {a}.
4. If r and s are regular expressions denoting the languages L1 and L2 respectively, then
r+s is equivalent to L1 U L2 i.e. union.
99
Course Code/Title: CS3401/Theory of Computation

rs is equivalent to L1 L2 i.e. concatenation

r* is equivalent to L1* i.e. closure.
The r* is known as kleen closure or closure which indicates occurrence of r for ∞ number of times.
For example if Σ = {a} and we have regular expression R = a*, then R is a set denoted by R= {ε, a, aa, aaa,
aaaa, ...}
r.e. = (0+ 1+ 0+ 1+)*
Example 2.1.5 Write regular expression to describe following languages:
i) {w = {0, 1}*}: w corresponds to binary encoding, without leading 0's, of natural numbers that are evenly
divisible by 4}
ii) {w = {0, 1}}*: w corresponds to binary encoding, without leading 0's of natural numbers that are powers
of 4}
iii) {w = {0-9}*: w corresponds to the decimal encoding, without leading 0's of an odd natural number}.
Solution:
i) The valid strings for given language are (100, 1000, 1100, 11100,...)
For ex: 100 = 4
Hence regular expression will be
r.e. = (1(0+1)* 00) + 0
ii) The vaild strings for given language are (100, 10000, 1000000,...}
Since (i) 100 in binary = 1×22 + 0×21 + 0×20 = 4 + 0 + 0 = 4 in decimal
(ii) 10000 in binary = 1×24 + 0×23 + 0×22 + 0×21 + 0×20 = 16 in decimal
Thus we want 4, 16, 64... in binary representation as valid string.
Hence the regular expression is
r.e. = 1(00)*
iii) The odd natural numbers are those numbers that end with either 1, 3, 5 or 9. Hence regular expression
using the set (0-9)* will be as follows
r.e. = (ε +((1-9)(0-9)* ))(1+3+5+7+9)
Example 2.1.6 Write regular expressions for the following languages over the alphabet Σ = (a, b)
i) All strings that do not end with 'aa'.
ii) All strings that contain an even number of 'b's.
iii) All strings which do not contain the substring 'ba'.
Solution:
i) The language contains all the strings that do not end with aa means it may end with bb, ba or ab. Hence r.
e. will be
100
Course Code/Title: CS3401/Theory of Computation

(a + b) * ( (ab)* + (ba)* + b*)

ii) r. e. = (a* b a* b)*
iii) The L = {ε, a, b, bb, aa, ab, abb, ... }
r. e. = (a*b*)
Example 2.1.7 Give the Regular Expression for the following languages:
i) L = { x|x ϵ {a,b}* and x contains exactly two a's}
ii) L = (a, c, ab, cb, abb, cbb, abbb, cbbb, ...}
iii) L = { x|x ϵ {a, b}* and x is any string that begins in "abb" or a}
Solution:
i) b* ab* ab*
ii) The set contains all the string that either begin with a or c but always end with any number of b's.
r.e. = (a+c) b*
iii) r.e. = (abb + a) (a + b)*
Review Question
1. Discuss on regular expressions. AU: May-13, Marks 8
Equivalence of Finite Automata and Regular Expressions
There is a close relationship between a finite automata and the regular expression we can show this relation
in Fig. 2.2.1.

The Fig. 2.2.1 shows that it is convenient to convert the regular expression to NFA with & moves. Let us see
the theorem based on this conversion.
Equivalence of NFA and Regular Expression
AU: May-04,06,09,10,11,12,14,16,17, Dec.-10,14,15,19, Marks 10
Theorem 1: Let r be a regular expression, then there exists a NFA with ε transitions that accepts L (r).

101
Course Code/Title: CS3401/Theory of Computation

Proof: This theorem can be proved by induction method.

The basis of induction will be by considering r has zero operators.
Basis (zero operators) - Now, since r has zero operators, means r can be either ε or ϕ or a for some a in input
set Σ.
The finite automata for the same can be written as

Induction: This theorem can be true for n number of operators. The n is greater than or equal to 1. The
regular expression contains equal to or more than one operators.
In any type of regular expression there are only three cases possible.
1. Union 2. Concatenation 3. Closure
Let us see each,
Case 1: Union case
Let r = r1 + r2 where r1 and r2 be the regular expressions.
There exists two NFA's M1 = (Q1, Σ1, δ1, {f 1})
and M2 = (Q2, Σ2, δ2,{f2})
L (M1) = L(r1) means the language states by regular expression r1 is same which is represented by M1.
Similarly L (M2) = L (r2).
Q1 represents the set of all the states in machine M1.
Q2 represents the set of all the states in machine M2.
We assume that Q1 and Q2 are totally different i.e. Q1 and Q2 are disjoint.
Let q0 be new initial state and f0 be the new final state we will form
M = ((Q1 U Q2 U {q0, f0}), (Σ1 U Σ2), δ, q0 {f0})
The δ is denoted by,
i) δ (q0, ε) (q1, q2}
ii) δ (q, a) = δ1 (q, a) for q in Q1 - {f1} and a in Σ1 U {E}.
iii) δ (q, a) = δ2 (q, a) for q in Q2 -{f2} and a in Σ2 U {E}.
iv) δ (f1, ε) = δ1 (f2, ε) = {f0}
All the moves are now present in machine M which is as shown Fig. 2.3.2.

102
Course Code/Title: CS3401/Theory of Computation

The construction of machine M is shows the transition from q0 to f0 must begin by going to q1 or q2 on ε. If
the path goes to q1, then it follows the path in machine M1 and goes to the state f1 and then to f0 on ε.
Similarly, if the path goes to q2, then it follows the path in machine M2 and goes to state f2 and then to f0 on ε.
Thus the L (M) = L (M1) U L (M2). That means either the path in machine M1 or M2 will be followed.
Case 2: Concatenation case
Let, r = r1 r2 where г1 and r2 are two regular expressions. The M1 and M2 denotes the two machines such that
L (M1) = L (r1) and L (M2) = L (r2).
The construction of machine M will be
M = (Q1 U Q2, Σ1 U Σ2, δ,{q1}, {f2})
The mapping function δ will be given as
i) δ (q, a) = δ1 (q, a) for q in
Q1 - {f1} and α in Σ1 U{ε}
ii) δ (f1, ε) = {q2}.
iii) δ (q, a) = δ2 (q, a) for q in
Q2 and a in Σ1 U {ε}
The machine M is shown in the Fig. 2.3.3.

The initial state is q1 by some input a the next state will be f1. And on receiving ε the transition will be from
f1 to q2 and the final state will be f2. The transition from q2 to f2 will be on receiving some input b.
Thus L (M) = ab
That is a is in L (M1) and b is in L (M2).
Hence we can prove L (M) = L (M1) L (M2).
Case 3: Closure case
Let r = r1 where r1 be a regular expression.
103
Course Code/Title: CS3401/Theory of Computation

The machine M1 is such that L(M1)=L(r1).

Then construct M = (Q1 U {q0, f0}, Σ1, δ, q0, {f0}).
The mapping function δ is given
by,
i) δ (q0, ε) = δ (f1, ε) = {q1, f0}
ii) δ (q, a) = δ1 (q, a) for q in
Q1 - {f1} and a in Σ1 U {ε}
The machine M will be

The machine M1 shows that from q0 to q1 there is a transition on receiving ε similarly, from q0 to f0 on &
there is a path. The path exists from f1 to q1, a back path. Similarly a transition from f1 to f0 final state, on
receiving ε. The total recursion is possible. Thus one can derive ɛ, a, aa, aaa, .... for the input a.
Thus L (M) = L (M1)* is proved.
Now based on this proof let us solve some examples. These examples illustrate how to convert given regular
expression to NFA with ɛ moves.
Example 2.3.1 Construct an NFA equivalent to the following regular expression
((10) + (0+1)*) 01. AU: May-06, Marks 10
Solution: Consider
r.e. = (r1 + r2) r3
where
r1 = 10
r2 = (0+1)*
r3 = 01

We will build NFA for each r1, r2 and r3.

r1 = 10

104
Course Code/Title: CS3401/Theory of Computation

r2 = (0+1)*
r3 = 01

Now we will design the final NFA for r. (See Fig. 2.3.8 on next page)

(I+00) (1+0) = 97
Example 2.3.2 Construct a NFA equivalent to (0 + 1)* (00 + 11). AU May-04, Marks 8
Solution: Consider
r.e. = (0 + 1)* (00 + 11)
r1 = (0 + 1)
r2 = (00 + 11)
The NFA for r1 can be drawn as follows.

105
Course Code/Title: CS3401/Theory of Computation

The NFA for r2 can be

The NFA for the given regular expression can be (See Fig. 2.3.11 on next page).
Example 2.3.3 Construct NFA with epsilon for the RE = (a|b)* ab and convert into DFA and further find the
minimized DFA. AU May-17, Marks 16
Solution: The NFA with ɛ can be constructed as follows

The above NFA can be converted to DFA as follows -

106
Course Code/Title: CS3401/Theory of Computation

ε - closure (q0) = {q0, q1, q2, q4, q7} = Call it as A

δ' (A, a) = ε - closure (δ (q0, q1, q2, q4, q7), a)
= ε - closure (q3, q8)
= {q1, q2, q3, q4, q6, q7, q8}
δ' (A, a) = Call it as state B
δ' (A, a) = B
δ' (A, b) = ε - closure (δ (q0, q1, q2, q4, q7), b)
= ε - closure (q5)
= {q1, q2, q4, q5, q6, q7} Call it as C
δ' (A, b) = C
δ' (B, a) = ε - closure (δ (q1, q2, q3, q4, q6, q7, q8), a)
= ε - closure (q3, q8)
δ' (B, a) = B
δ' (B, b) = ε - closure (δ (q1, q2, q3, q4, q6, q7, q8), b)
= ε - closure (q5, q9)
= {q1, q2, q4, q5, q6, q7, q9} Call it as D
δ' (B, b) = D
δ' (C, a) = ε - closure (δ (q1, q2, q4, q5, q6, q7), a)
= ε - closure (q3, q8)
δ' (C, a) = B
δ' (C, b) = ε - closure (δ (q1, q2, q4, q5, q6, q7), b)
= ε - closure (q5)
δ' (C, b) = C
δ' (D, a) = - closure (δ (q1, q2, q4, q5, q6, q7, q9), a)
= ε - closure (q3, q8)
δ' (D, a) = B
δ' (D, b) = δ - closure (δ (q1, q2, q4, q5, q6, q7, q9), b)
= ε - closure (q5, q9)
δ' (D, b) = D
As no new state is getting generated the transition table will be

107
Course Code/Title: CS3401/Theory of Computation

The δ transition of state B and state D is same but B is a non final state while D is a final state. So we can not
merge them. We can merge state A and state C. Then the minimized DFA will be

Direct Method for Conversion of RE to FA

1. State Elimination Method
This is the simplest method of obtaining regular expression. We will use following rules to obtain r.e. by
eliminating states
1. Eliminate all the states except final state and start state.
2. Reduce the given finite automata and obtain the generalised transition graph with (start and end states as
follows

The regular expression for this finite automata will be –

108
Course Code/Title: CS3401/Theory of Computation

3. If we reduce the finite automaton to only one state graph by state eliminating method then -

4. After eliminating the sufficient number of states we can obtain r.e. as sum of the expressions derived from
the reduced automata. Let us understand this method of obtaining regular expression with the help of some
examples.
Example 2.3.4 Obtain method r.e. from given FA by state elimination method.

Solution: In above given FA state q3 is a dead state. Hence we will eliminate state q3. Thus the FA now
becomes

This FA resembles the generic finite automata with two state (as given in Fig. 2.3.15)
Hence required r.e. will be
a*bb* As q2 is a final state we get
i.e. r.e. = a*b+
Example 2.3.5 Represent the language given by the following DFA, by obtaining r.e. by state elimination
method.

109
Course Code/Title: CS3401/Theory of Computation

Solution: In above transition graph state q1 is a dead state. We can not reach to final state from this state,
hence we will eliminate state q1. The FA then becomes as –

The state q2 can be written as (a + b) *. Hence the required r.e. is a(a+b)*. This regular expression specifies a
language which starts with letter a and it is followed by any number of a's and b's.
Example 2.3.6 Construct Finite automaton to accept the regular expression
(0+1)*(00 + 11)(0+1)*. AU: May-14, Marks 8, May-11, Marks 6
Solution:
The FA for r.e. =(0+1) (00 + 11) (0+1)* as follows –

110
Course Code/Title: CS3401/Theory of Computation

Example 2.3.7 Construct Finite Automata equivalent to the regular expression (ab +a)*. AU: Dec.-15, Marks
6
Solution: First of all we will construct NFA for given regular expression.

The NFA without ε is

Example 2.3.8 Draw a non-deterministic automata to accept string containing the substring 0101. AU May-
16, Marks 2

111
Course Code/Title: CS3401/Theory of Computation

Solution: The regular expression is

(0+1)* 0101 (0+1)*
The non-deterministric finite automata is

Example 2.3.9 Construct a finite automata for the regular expression 10 + (0+11)0*1 AU Dec.-19, Marks 6
Solution :

112
Course Code/Title: CS3401/Theory of Computation

Review Question
1. Let r be a regular expression. Then prove that there exists a NFA with & transition that accept L(r).
AU: Dec.-03, Marks 16; Dec.-06, Marks 8; Dec.-10, Marks 10; May-12, Marks 6
Conversion of Finite Automata to Regular Expressions
AU Dec.-03,04,05,09,11,13,16,19, May-05,06,07,08, 12, Marks 16

113
Course Code/Title: CS3401/Theory of Computation

The Arden's theorem is useful for checking the equivalence of two regular expression as well as in
conversion of DFA to r.e. Let us see its use in conversion of DFA to r.e.
Following algorithm is used to build the r.e. from given DFA.
1. Let q1 be the initial state.
2. There are q2, q3, q4, ...qn number of states. The final state may be some qj where j ≤ n.
3. Let αji represents the transition from qj to qi
4. Calculate qj such that
qi = αji qj
If qi is a start state
to qi
qi = αji qj + ε
5. Similarly compute the final state which ultimately gives the regular expression r.
Let us solve few examples based on this algorithm.
Example 2.4.1 Construct r.e. from given DFA.

Solution: Let us write down the equations state on

q1 = q1 a + ε
Since q1 is a start state ε will be added and the input a is coming to q1 from q1 hence we write
State = Input coming to it × Source state of input
Similarly q2 = q1 a + q2 b
Let us simplify q1 first
q1 = q1 a + ε
We can re-write it as
q1 = ε + q1 a
which is similar to R = Q + RP which further gets reduced to R = QP*.
Assuming R = q1, Q = ε, p = a
We get
q1 = ε . a*
q1 = a*
114
Course Code/Title: CS3401/Theory of Computation

εR=R
Substituting value of q1 in q2 we get
q2 = q1 b + q2 b
q2 = a * b + q2 b
We can compare this equation with R = Q + R P assuming R = q2, Q = a*b, P = b which gets reduced to R =
QP*.
q2 = a*b.b*
As R R* = R+
q2 = a*.b+
From the given DFA, if we want to find out the regular expression, we normally calculate the equation for
final state. Since in the given DFA q2 is a final state and q2 = a*b+. We can conclude as the DFA represents a
as regular expression.
Example 2.4.2 Represent the language accepted by following DFA.

Solution: Since there is only one state in the finite automata let us solve for q0 only.
q0 = q00 + q01 + ε
q0 = q0 (0+1) + ε
= ε . (0+1)* R = Q + R P
q0 = (0+1)*
Since q0 is a final state, q0 represents the final r.e. as
r = (0 + 1)*
L (r) = {ε, 0,00,1,11,10,....}
L (r) = {any combination of 0 and 1}
Example 2.4.3 Construct r.e. for the given DFA. AU May-07, Marks 6

Solution: Let us build the regular expression for each state.

q1 = q10 + ε

115
Course Code/Title: CS3401/Theory of Computation

q2 = q11 + q21
q3 = q20 + q3 (0 + 1)
Since final states are q1 and q2, we are interested in solving q1 and q2 only.
Let us see q1 first
q1 = ε + q10
Which is R = Q + R P equivalent so we can write
q1 = ε .(0)*
q1 = 0*
ε. R = R
Substituting this value into q2, we will get
q2 = 0*1 + q21
q2 = 0*1 (1)* R = Q + R P ⇒ Q P*
The regular expression is given by
r = q1 + q2 =0* + 0* 1. 1*
r = 0* + 0* 1+ 1.1* = 1+
Example 2.4.4 Convert the following NFA into a regular expression. AU: Dec.-13, Marks 8

Solution: We will obtain regular expression using Arden's method.

The equations for each state are -
A = A0 + A1 + ε = A(0 + 1) + ε
B = A1
C = B (0+1)
D = C (0+1)
We will solve equation (1)
A = A (0+1) + ε
i) R = RP + Q gives R = QP* ii) εR* = R*
A = ε(0+1)* = (0+1)*

116
Course Code/Title: CS3401/Theory of Computation

A = (0+1)* … (5)
Equation (2) becomes
B = A1 = (0+1)* 1 … (6)
Now by using equation (6) we get equation (3) as
C = B (0+1)
C = (0+1)* 1 (0+1) … (7)
Using equation (7), we get equation (4) as
D = C (0+1)
= (0+1)* 1 (0+1) (0+1) … (8)
As state C and D are final states equation (7) and equation (8) represent final regular expression.
r.e. [(0+1)* 1 (0 + 1)] + [(0+1)* 1 (0 + 1) (0 + 1)]
Example 2.4.5 Construct the regular expression corresponding to the state diagram given in the following
Fig. 2.4.5. AU: May-05, Marks 10; May-08, Marks 16, Dec.-19, Marks 2

Solution: We will obtain the regular expression for the given state diagram using Arden's theorem. Let us
write equations for each state.
q1 = q10 + q30 + ε being a start state, add ɛ.
q2 = q11 + q21 + q31
q3 = q20
Consider q2 first.
q2 = q11 + q21 + q31
q2 = q11 + q21 + q201 q3 = q20
q2 = q2 (1+01) + q11
R = Q + RP gives R = QP*
R = q2, Q = q11, P = (1 + 01)
q2 = q11 (1+01)*
Then put value of q2 in q3 and we get,
q3 = q11 (1+01)* 0
117
Course Code/Title: CS3401/Theory of Computation

Now substitute value of q3 in q1

q1 = q10 + q30 + ε
q1 = q10 + q11 (1+01)* 00 + ε
q1 = q1 [0+1 (1+01)* 00] + ε
R = Q + RP gives R = QP*
R = q1, Q = ε, P = 0+1 (1+01)* 00 we get
q1 = ε [0+1 (1+01)* 00]*
q1 = (0+1 (1+01)* 00)* εR=R
State q1 is a final state. Hence an equation for final state becomes a regular expression for given state
diagram.
The r.e. = (0+1 (1+01)* 00)*
Example 2.4.6 Obtain the regular expression for the finite automata. AU: May-12, Marks 8

Solution: We will write the equations for each state,

q1 = q1 a + ε … (1)
q2 = q2a + q1b … (2)
q3 = q2b … (3)
Solving equation (1)
q1 = q1 a + ε
q1 = ε a* = a*
R = Q + RP
gives R = QP*
and ε R* = R*
Solving equation (2) using q1 = a* we get,
q2 = q2 a + a* b
q2 = a* b a*
Solving q3 by putting q2 = a* b a*
we get
q3 = q2 b

118
Course Code/Title: CS3401/Theory of Computation

q3 = a* ba* b
As q3 represents the final state, the equation for state q3 represents the regular expression. Hence regular
expression = a* ba* b.
Review Questions
1. State and explain the conversion of DFA into regular expression using Arden's theorem. Illustrate with an
example. AU: Dec.-11, Marks 16
2. Discuss the basic approach to convert from NFA to regular expression. Illustrate with an example. AU
Dec.-16, Marks 16
Equivalence of Two Regular Expressions
AU May-10,11, Marks 9
The two regular expressions P and Q are equivalent (denoted as P = Q) if and only if P represents the same
set of strings as Q does. For showing this equivalence of regular expressions we need to show some
identities of regular expressions.
Let P, Q and R are regular expressions then the identity rules are as given below
1. ε R = R ε = R
2. ε* = ε ε is null string
3. (ϕ)* = ε ϕ is empty string.
4. ϕ R = R ϕ = ϕ
5. ϕ + R = R
6. R + R = R
7. RR* = R*R = R+
8. (R*)* = R*
9. ε + RR* = R*
10. (P+Q) R = PR + QR
11. (P+Q)* = (P* Q*) = (P* + Q*)*
12. R* (ε + R) = (ε + R) R* = R*
13. (R + ε)* = R*
14. ε + R* = R*
15. (PQ)* P = P (QP)*
16. R* R + R = R* R
Let us see one important theorem named Arden's Theorem which helps in checking the equivalence of two
regular expressions.

119
Course Code/Title: CS3401/Theory of Computation

Arden's Theorem: Let, P and Q be the two regular expressions over the input set 2. The regular expression R
is given as
R = Q + RP
Which has a unique solution as R = QP*.
Proof : Let, P and Q are two regular expressions over the input string Σ.
If P does not contain & then there exists R such that
R = Q + RP …. (2.5.1)
We will replace R by QP* in equation (2.5.1)
Consider R.H.S. of equation (2.5.1)
= Q + QP* P
= Q(ε + P* P)
= QP*
ε + R * R = R*
Thus R = QP*
is proved. To prove that R = QP* is a unique solution, we will now replace L.H.S. of equation (2.5.1) by Q +
RP. Then it becomes
Q + RP
But again R can be replaced by Q + RP.
Q + RP = Q + (Q + RP) P
= Q + QP + RP2
Again replace R by Q + RP.
= Q + QP + (Q + RP) P2
= Q + QP + QP2 + RP3
Thus if we go on replacing R by Q + RP then we get, Q + RP = Q + QP + QP2 + ... + QPi + Rpi+1
= Q(ε + P+ P2 + ….. Pi) + Rpi+1
From equation (2.5.1),
R = Q (ε + P+ P2 + ….. + Pi) + Rpi+1 …. (2.5.2)
Where i ≥ 0
Consider equation (2.5.2),
R = Q(ε + P+ P2 + ... + Pi + RPi+1 /p*
R = QP* + RPi+1
Let w be a string of length i.
120
Course Code/Title: CS3401/Theory of Computation

In RPi+1 has no string of less than i + 1 length. Hence w is not in set RPi+1. Hence R and QP* represent the
same set. Hence it is proved that
R = Q + RP has a unique solution.
R = QP*
Example 2.5.1 Prove (1+00*1) + (1+00*1) (0+10*1) * (0+10*1) = 0*1(0+10*1) *AU: May-11, Marks 8
Solution: Let us solve L.H.S. first,
(1+00*1) + (1+00*1) (0+10*1) * (0+10*1)
We will take (1+00*1) as a common factor
1+00*1
(ε+(0+10*1)*(0+10*1))
(ε+ R*R) where R = (0+10*1)
As we know, (ε + R*R) = (ε + RR*) = R*
(1+00*1) ((0+10*1)*) out of this consider
(1+00*1) (0+10*1)*
Taking 1 as a common factor
(ε+00*) 1 (0+10*1) *
Applying ε + 00* = 0*
0*1 (0+10*1) *
= R.H.S.
Hence the two regular expressions are equivalent.
Example 2.5.2 Show that (0*1*)* = (0+1)*
Solution: Consider L.H.S.
= (0*1*)*
{ε, 0,00,1,11,111, 01, 10,...}
= {any combination of O's, any combination of 1's, any combination of 0 and 1, ε}
Similarly,
R.H.S.
= (0+1)*
= {ε, 0, 00, 1, 11, 111, 01, 10,....}
= {ε, any combination of 0's, any combination of 1's, any combination of 0 and 1}
Hence, L.H.S. = R.H.S. is proved.

121
Course Code/Title: CS3401/Theory of Computation

Example 2.5.3 Prove that r (s+t) = rs + rt

Solution: In case of L.H.S.
L.H.S. = r (s+t) solving this further
= r.s + r.t
i.e. r is concatenated with s or with t
= R.H.S.
L.H.S. = R.H.S. is proved.
Check for the following regular expressions for equivalence and justify.
i) R1 = [(a + bb)* (b + aa)*]*
ii) R2 = (a + b)*
Here R1 and R2 are equivalent because the strings which can be generated by R1 can be generated by R2 or
vice versa.
For instance,
R1 = abab - this string can be generated by selecting a from (a + bb)* then b from
(b + aa)* again a from (a + bb)* and b from (b + aa)*.
R2 = abab - this sting can be selecting a then b repetitively from (a + b)*
Thus R1 R2 is proved
ii) R1 = (a + b)* abab*
R2 = b* a (a + b)* ab*
Here strings generated by R1 are same as R2
For instance R1 can generate abababb. Similarly R2 can generate abababb as we will select 'null' from b* then
'null' 'a'; then 'bab' from (a + b)* then 'abb' from ab*
Thus
R1 = R2 is proved.
Example 2.5.4 Prove ε + 1* (011)* (1* (011)*)* = (1 + 011)*
Solution: Let, L.H.S. is
ε + 1*(011)* (1* (011)*)*
If we consider 1*(011)* as P1 then,
= ε + P1 P1* ε + P1P1* = P1*
= P1*
We can put P1 = 1* (011)* then,
= (1*(011)*)*
122
Course Code/Title: CS3401/Theory of Computation

Now consider P2 = 1 and P3 = (011) then it becomes

= (P2* P3*)* (P* Q*)* = (P + Q)*
= (P2 + P3)*
= (1 + 011)*
= R.H.S.
Thus L.H.S. = R.H.S.
Hence
ε + 1* (011)* (1* (011)*)* = (1+011)* is proved.
Proving Languages to be not Regular (Pumping Lemma)
AU: May-04,06,07,12, Dec.-12,13,14,15, Marks 6
• Pumping lemma is a basic and important theorem used for checking whether given string is accepted by
regular expression or not. In short, this lemma tells us whether given language is regular or not.
• One key them is that any language for which it is possible to design the finite automata is definitely the
regular language.
Theorem: Let L be a regular set. Then there is a constant n such that if Z is any word in L and |Z| ≥ n we can
write z = u v w such that |u v| ≤ n, |v| ≥ 1 for all i ≥ 0, u vi w is in L. The n should not be greater than the
number of states.
Proof: If the language L is regular it is accepted by a DFA. M = (Q, Σ, δ, q0, F). With some particular number
of states say, n. Consider the input can be a1, a2, a3, .... am, m≥n. The mapping function δ could be written as
δ(q0, q1, q2, q3 ... qi) = qi
The transition diagram is as shown in Fig. 2.6.1.

If qm is in F i.e. q1, q2, q3, … qm is in L(M) then a1, a2,...aj ak+1 ak+2 ......am is also in L(M)
. Since there is path from q0 to qm that goes through qj but not around the loop labelled aj+1 .... ak. Thus
δ (q0, a1, aj ak+1 ...am) = δ (δ (q0, q1, ... qj), ak+1 .... am)
= δ (qj, qk+1 ...qm)
= δ (qk, qk+1 ...qm)
= qm
That is what we have proved that given any long string can be accepted by FA, we should be able to find a
substring near the beginning of the string that may be pumped i.e. repeated as many times as we like and
resulting string may be accepted by FA.
123
Course Code/Title: CS3401/Theory of Computation

• Advantage of Pumping Lemma

The pumping lemma is used to check whether given language is regular or not.
Example 2.6.1 Show that the set L = { bi2 |i>1} is not regular. AU: May-06, Marks 6
OR
ii) Prove that L = {0i2 /i is an integer; i≥1 is not regular. AU: Dec.-14, 15, Marks 6
Solution: We have to prove that the language L= bi2 is not regular. This language is such that number of b's is
always a perfect square.
For example, if we take i = 1
L = b12 = b the length = 12
= b22 = bbbb length = 22
and so on.
Now let us consider
L = bn2 where length = n2
it is denoted by z.
|z| = n2
By pumping lemma z = u v w
where 1 ≤ |v| ≤ n
As z = uvi w where i = 1
Now we will pump v i.e. make i = 2.
As we made i = 2 we have added one n2.
1≤ | v | ≤ n.
n2 +1 ≤ uvw | ≤ n+n2
i.e. n2 +1 ≤ | uvw | ≤ n2 +n+n+1
i.e. n2 +1 ≤ | uvw | ≤ (n+1)2
= n2 ≤ | uvw | ≤ (n+1)2
Thus the string lies between two consequetive perfect squares. But the string is not a perfect square. Hence
we can say the given language is not regular.
For example,
L = bi2
Let i = 2
L = bbbb
L = uvw
124
Course Code/Title: CS3401/Theory of Computation

Assume uvw = bbbb

Take
u=b
v = bb
w=b
By pumping lemma, even if we pump v i.e. increase v then language should show the length as perfect
square.
= uvw
= uv. vw
= bbbbbb
= length of b is not a perfect square
Thus the behaviour of the language is not regular, as after pumping something onto it does not show the
same property (being square for this example.)
Example 2.6.2 Is the following language regular ? Justify your answer
L = {02n|n≥1}
AU: May-07, Marks 2, May-13, Marks 4
Solution: This is a language length of string is always even.
i.e.
n = 1; L = 00
n =2 L = 00 00 and so on.
Let L = uvw
L = 02n
|z| = 2n = u vi w
If we add 2n to this string length.
|z| = 4n = uv. vw
= even length of string.
Thus even after pumping 2n to the string we get the even length. So the language L is regular language.
Example 2.6.3 Show that L = {0n 1n+1 | n>0} is not regular.
Solution: Let us assume that L is a regular language.
|z| = |uvw|
= 0n 1n+1
Length of string [z] = n + n + 1 = 2n + 1.
125
Course Code/Title: CS3401/Theory of Computation

That means length is always odd.

By pumping lemma
= |uv. vw|
That is if we add 2n + 1
2n + 1 < (2n + 1) + 2n + 1
2n+1 < 4n+ 2
But if n = 1 then we obtain 4n+ 2 = 6 which is no way odd. Hence the language becomes irregular.
Even if we add 1 to the length of |z|, then
|z| = 2n + 1 + 1
= 2n + 2
= even length of the string.
So this is not a regular language.
Example 2.6.4 Show that set L = (0i1i | i ≥ 1} is not regular. AU: May-04, Dec.-04,05, Marks 6
Solution: Assume that L = {0i 1i | i ≥ 1} is regular.
Let, w = 0 1 such that |w| = 2n. By pumping lemma we can write
w = xyz such that |xy| ≤ n and |y| ≠ 0.
Now if xy1z ϵ L then the language L is said to be regular.
There are many cases - i) y has only 0's ii) y has only 1's iii) y has both 0's and 1's. i) If y has only O's then
the string
w = 0n-k|n = xz since y = 0k and i = 0
Surely n-k ≠ n. Hence xz € L.
Hence our assumption of being L regular is wrong.
ii) If y has only 1's then, for i = 0 and y = 1k
w = xz = 0n 1n-k
As n ≠ n-k, xz = w € L
Again L is not regular.
iii) If y has 0's and 1's then
w = 0n-k 0k 1j 1n-j = xyi z
If i = 2 then
w = 0n-k 02k 12j 1n-1 € L
Hence from all these 3 cases it is clear that language L is not regular.

126
Course Code/Title: CS3401/Theory of Computation

Example 2.6.5 Which of the following languages is regular? Justify.

1) L = {an bm | n, m ≥ 1}
2) L = {an bn | n ≥ 1} AU: May-12, Marks 8
Solution : 1) Let, L = {an bm | n, m ≥ 1}
Here the number of a's and b's can be at least one. We can write the regular expression for given L as
r.e. = a+ b+
For this regular expression the FA can be
As we can draw the FA for representing given language, the given L is said to be regular.

2) Given L = {an bn | n ≥ 1} is not regular. Refer similar example 2.6.4.

Example 2.6.6 Using pumping lemma for the regular sets, prove that the language L= {ambn | m>n} is not
regular. AU: Dec.-12, Marks 10
Solution: Let us assume that L is a regular language. The string W ϵ L such that
|W| = | xyz | = am bn
Length of string |W| = m + n, where m > n. By pumping lemma we can write
W = xyz such that |xy| ≤ n |y| ≠ 0.
Now if xyiz ϵ L then the language is said to be regular.
There are many cases: i) y has only a's
ii) y has only b's
iii) y has both a's and b's.
i) If y has only a's then assume W = a3 b2.
If we map W = xyiz with i = 0. Then W in equation (1) becomes
W= a aa bb
x=a, y=aa, z=bb
W = xz y1 = y0 = 1
W = abb = a1b2 € {L = am bn | m>n}
ii) y has only b's then assume W = a3 b2
If we map W = xyiz with i = 3 then W in equation (2) becomes
Regular Expressions and Languages
W= aaa bb
127
Course Code/Title: CS3401/Theory of Computation

x = aaa
y=b
z=b
W = (aaa) (bbb) (b)
W = a3 b4 € {L = am bn | m > n}
iii) y has both a's and b's. Then assume W = a3 b2.
If we map W = xyiz with i = 2 then W in equation (3) becomes
W = aa ab b
x = aa
y = ab
z=b
W = (aa) (abab) (b)
= a3 bab2 € ambn
From above three cases it is clear that our assumption of L being regular is wrong. This proves that given L =
ambn is not regular.
The simple way to know whether given language is regular or not is that try to draw finite automata for it, if
you can easily draw the FA for the given L then that language is surely the regular otherwise not.
Example 2.6.7 Using pumping lemma for regular sets, prove that the language L = {0m1n 0m+n | m ≥ 1 and n ≥
1} is not regular. AU: Dec.-13, Marks 10
Solution: Let us assume that L is a regular language. The input string w ϵ L such that
|w| = | xyz | = 0m1n 0m+n
By pumping lemma we can write
w = xyz such that |xy| ≤ n and |y| ≠ 0.
There are three cases: i) y has only 0's
ii) y has only 1's
iii) y has 0's and 1's.
Case i) y has only 0's
Consider w = 00010000
If we map w = xyz then
By pumping lemma,
w = xyiz
W = 0 00 10000
128
Course Code/Title: CS3401/Theory of Computation

0 = x, 00 = y, 10000 = z
if i = 2 then
w = xyyz i.e.
= 0(00) (00) (10000)
W = 05 11 04 € 0m 1n 0m+n
Case ii) y has only 1's
Consider w = 00110000
If we map w = xyz then
By pumping lemma,
w = 00 11 0000
x = 00, y = 11, z = 0000
w = xyiz
if i = 2 then
w = xyyz i.e.
= 00(11) (11) (0000)
= 02 14 04 € 0m 1n 0m+n
Case iii) y has 0's and 1's
Consider w = 001000
w = 0 01 000
x = 0, y = 01, z = 000
If we map w = xyz then
By pumping lemma,
w = xyiz
If i = 2 then
w = xyyz i.e.
= 0 (01) (01) (000)
= 021 011103 € 0m1n 0m+n
From above three cases, it is clear that our assumption of L being regular is wrong. This proves that given L
= 0m1n 0m+n is not regular.
Example 2.6.8 Prove that following languages are not regular:
i) { w ϵ {a,b}* |w = wR} ii) Set of strings of 0's and 1's beginning with 1, whose value treated as a binary
number is prime. AU: Dec.-19, Marks 13
129
Course Code/Title: CS3401/Theory of Computation

Solution: i) Let, the given language

• L = {w ϵ {a, b}* |w = wR} is regular
• Suppose there is a DFA for L with p states. Let w be word in L. We will pump the strings, such that
w = xyz.
• We will choose w = 0P10P ϵ L
• By pumping Lemma,
w = xyz, y ≥ 1,|xy|≤ p and
w = xyiz is in L for every i
• The pumping part is at the beginning of string. Hence |xy|≤ p and xy consists of 0's only
• Since |y| ≥ 1, y contains at least one 0.
• If i = 2 then w = xyyz and it must ϵ L
if w = 00 0 1000
x = 00
y=0
z = 1000
w = xyyz
w = 00001000 € L
• This shows that, our assumption of being L is regular is wrong.
• This proves that given language is not regular.
ii) L = Binary numbers of prime numbers
Let, w = xyz ϵ L we assume that L is a binary language of prime numbers.
• Assume | xyz |= n.
• Assume L is regular.
• By pumping lemma.
w = xyz, |y| ≥ 1, |xy| ≤ p and w = xyiz is in L for every i
• i = 2, then
w = xyyz
|w| = n+1 € L
This shows that our assumption of L being regular is wrong and L is non-regular.
Closure Properties of Regular Languages
AU: May-06,10,13,14, Dec.-07.08,10,12,13,17, Marks 8
130
Course Code/Title: CS3401/Theory of Computation

If certain languages are regular and language L is formed from them by certain operations (such as union or
concatenation) then L is also regular. These properties are called closure properties of regular languages.
Such languages represent the class of regular languages which is closed under the certain specific operations.
The closure properties express the idea that when one or many languages are regular then certain related
languages are also regular. The closure properties of regular languages are as given below.
1. The union of two regular languages is regular.
2. The intersection of two regular languages is regular.
3. The complement of a regular languages is regular.
4. The difference of two regular languages is regular.
5. The reversal of a regular languages is regular.
6. The closure operation on a regular language is regular.
7. The concatenation of regular language is regular.
8. A homomorphism of regular languages is regular.
9. The inverse homomorphism of regular language is regular.
Theorem 1: If L1 and L2 are two languages then L1 U L2 is regular.
Proof: If L1 and L2 are regular then they have regular expression L1 = L (R1) and L2 = L (R2) Then L1 U L2 =
L (R1+ R2) thus we get L1 U L2 as regular language. (any language given by some regular expression is
regular).
Theorem 2: The complement of regular language is regular. AU May-14, Marks 6, Dec.-08, Marks 2
Proof : Consider L1 be regular language which is accepted by a DFA M = (Q, Σ, δ, q0, F) The complement of
regular language is L1 which is accepted by M' = (Q, Σ, δ, q0, Q - F) That means M is a DFA with final states
ϵ F and M' is a DFA in which all the non-final states of M become final. In other words, we can say that the
strings that are accepted by M are rejected by M' similarly, the strings rejected by M are accepted by M'.
Thus as L1 is accepted by DFA M', it is regular.
Theorem 3: If L1 and L2 are two regular languages then L1∩ L2 is regular. AU: Dec.-07, 08, Marks 4
Proof: Consider that languages L1 is regular. That means there exists some DFA M1 that accepts L1. We can
write M = (Q1, Σ, δ1, q1, F1) Similarly being L2 regular there is another DFA M2 (Q2, Σ, δ2, q2, F2)
Let, L be the language obtained from L1 ∩ L2. We can the simulate M = (Q, Σ, δ, q, F)
where
Q = Q1 ∩ Q 2
δ = δ1 ∩ δ2 a mapping function derived from both the DFAS.
q ϵ Q which is initial state of machine M.
F = F1 ∩ F2, the set of final states, which is common for M1 and M2 both.

131
Course Code/Title: CS3401/Theory of Computation

It is clear that there exists some DFA which accepts L1 ∩ L2 i.e. L. Hence L is a regular language. This
proves that if L1 and L2 are two regular languages then L1 is regular. In other words the regular language is
closed under intersection.
Theorem 4: If L1 and L2 are two regular languages then L1 - L2 is regular.
Proof: The L1 - L2 can also be denoted as L1 U Ḹ2
Consider L1 be regular language which is accepted by DFA M =(Q,Σ,δ,q0,F) The complement of regular
language L1 is Ḹ1 which is accepted by M'=(Q,Σ,δ,q0,Q-F) That means M is a DFA with final state's set F and
M' is a DFA in which all the non final states of M become final states and all the final states of M become
non-final states. Thus L1 and Ḹ2 are two regular languages. That also means: these languages are accepted by
regular expressions. If L1 = L(R1) and Ḹ2 = L(R`2). Then L1 U Ḹ2 = L (R1 + R`2). This ultimately shows that
L1 U Ḹ2 is regular. In other words L1 – L2 is regular. Thus regular languages are closed under difference.
Theorem 5: The reversal of a regular languages is regular. AU: Dec.-07, 08, Marks 4
Proof: Reversal of a string means obtaining a string which is written from backward that is w is denoted as
reversal of string w. That means L (wR) = (L(w))R. This proof can be done with basis of induction.
Basis: If w= ε or ϕ then wR is also ε or ϕ
i.e. (ε)R = ε and (ϕ)R = ϕ
Hence L(wR) is also regular.
Induction :
Case 1: If w = w1+ w2 then
w = (w1)R + (w)R
As the regular language is closed under union. Then w is also regular.
Case 2: If w = w1 + w2
Consider w1 = (ab, bb)
and w2 = (bbba, aa)
The wR1 = (ba, aa)
wR2 = (aaab, bb) then
w – wR1 wR2
(ba, aa, aaab, bb) is also regular. Thus given language is regular one.
Theorem 6: The closure operation on a regular language is regular.
Proof: If language L1 is regular then it can be expressed as L1 = L(R1) Thus for a closure operation a
language can be expressed as a language of regular expressions. Hence L1 is said to be a regular language.
Theorem 7: If L1 and L2 are two languages then L1 L2 is regular. In other words regular languages are closed
under concatenation.
Proof: If L1 and L2 are regular then they can be expressed as L1 = L(R1) and L2 = L(R2) Then L1 L2 = L(R1 R2)
thus we get a regular language. Hence it is proved that regular languages are closed under concatenation.
132
Course Code/Title: CS3401/Theory of Computation

Theorem 8: A homomorphism of regular languages is regular.

Proof: The term homomorphism means substitution of string by some other symbols. For instance the string
"aabb" can be written as 0011 under homomorphism. Clearly here, a is replaced by 0 and b is replaced by 1.
Let Σ is the set of input alphabets and Γ be the set of substitution symbols then Σ* → Γ* is homomorphism.
The definition of homomorphism can be extended as
Let, w = a1 a2 ... an
h(w) = h(a1) h(a2) ... h(an)
If L is a language that belongs to set Σ, then the homomorphic image of L can be defined as:
h(L) = {h(w): w ϵ L}
To prove that if L is regular h(L) is also regular consider following example -
Let, Σ = {a, b} and w = abab
Let h(a) = 00
and h(b) = 11
Then we can write h(w) = h(a) h(b) h(a) h(b)
= 00110011
The homomorphism to language is applied by applying homomorphism on each string of language.
If L = ab*b then,
L = {ab, abb, abbb, abbbb, ...)
Now h(L) = (0011, 001111, 00111111, 0011111111, ...)
h(L) = 00 (11)* As it can be represented by a regular expression, it is a regular language. Hence it is proved
that if L is regular then h(L) is also regular. In other words, family of regular languages is closed under
homomorphism.
Theorem 9: The inverse homomorphism of regular language is regular.
Proof : Let Σ* → Γ* is homomorphism.
The Σ is the input set and Γ be the substitution symbols used by homomorphic function.
Let, L be the regular language where L ϵ Σ, then h(L) be homomorphic language. The inverse homomorphic
language can be represented as h-1(L)
Let,
h-1(L) = {w | wϵL}
If L is regular then h(L) is also regular because regular language is closed under homomorphism. That if
there exist a FA M = (Q, ϵ, δ, q0, F) which accepts L then h(L) must also be accepted by FA M. For
complement of L i.e. language L' the inverse homomorphic language is h-1(L). Let M' be the FA in which all
the final states of M become non-final states and all the non-final states of M become the final states. Clearly
the language L' can be accepted by M' Hence h-1(L) must also be accepted by FA M'.

133
Course Code/Title: CS3401/Theory of Computation

For example - Let L = (010)* be a regular language. And L = {010, 010010, ...} Let h(0) = a and h(1) = bb be
homomorphic function. Then
h(L) = (abba)*
This L can be represented by following DFA.

Thus there exists a FA which accepts h-1(1). This shows that, inverse homomorphism of regular language is
regular.
Review Questions
1. Show that regular languages are closed under intersection and reversal. AU: Dec.-07, 08, Marks 8
2. Prove that regular sets are closed under substitution. AU: Dec.-10, Marks 6
3. State and prove using an example, the properties of regular language. AU: May-10, Marks 7
4. Prove any two closure properties of regular languages. AU: Dec.-12, Marks 6
5. Discuss in detail about the closure properties of regular languages. AU: May-13, Dec.-13, Marks 8; Dec.-
17, Marks 13
Two Marks Questions with Answers
Q.1 Is it true that the language accepted by any NFA is different from the regular language? Justify your
answer. AU: May-04
Ans. No, any language accepted by DFA, NFA, ε-NFA is called a regular language. For any finite automaton
we can construct an equivalent regular expression and the language represented by regular expressions is a
regular language.
Q.2 Describe the following by regular expression
a) L1 = The set of all strings of 0's and 1's ending in 00.
b) L2 The set of all strings of 0's and 1's beginning with 0 and ending with 1.
AU: May-04, Dec.-12
Ans. a) The set of all strings of 0's and 1's is given by (0 + 1)*.

134
Course Code/Title: CS3401/Theory of Computation

Hence r.e. for L1 = (0+1)* 00.

b) The set of all strings beginning with 0 can be 0 (0+1)*.
Hence r.e. for L2 = 0 (0+1)* 1.
Q.3 Show that (r*)* = r* for a regular expression r. AU: Dec.-04
Ans. Consider,
r=0 where Σ = {0}
Now L.H.S. = (r*)*
= ((0)*)*
= {ε, 0, 00, 000, ...} …(1)
Thus the set contains string of O's including null string.
Now R.H.S. = r*
= (0)*
= {ε, 0, 00, ... } …(2)
From equation (1) and (2) it is proved that
L.H.S. = R.H.S.
Hence, (r*)* = r
Q.4 Find the language accepted by the following automaton. AU : May-05

Ans. The r.e. that can be obtained from given DFA is

r.e. = 0* 1*
That means the strings accepted by FA will be any number of O's followed by any number of 1's. Any
number means it can be zero as well.
Q.5 Define regular expression. Give an example. AU: Dec.-05, May-13
Ans. Let Σ be an alphabet which is used to denote the input set. The regular expression over Σ can be defined
as follows.
1. ϕ is a regular expression which denotes the empty set.
2. ε is a regular expression and denotes the set {ε}.
3. For each 'a' in Σ 'a' is a regular expression that denotes the set {a}.
4. If r and s are regular expressions denoting the languages L1 and L2 respectively then
135
Course Code/Title: CS3401/Theory of Computation

r+s is equivalent to L1 U L2 i.e. union.

rs is equivalent to L1 L2 i.e. concatenation.
r* is equivalent to L1* such that if Σ = {a} then
L1* = {ε, a, aa, ...}
For example: Write the regular expression for the language accepting all possible string over = {a}.
Regular expression = a*
Q.6 Let R be any set of regular languages. Is U Rj regular? Prove it. AU: Dec.-06
Ans. If R be the set of regular languages then U R is regular.
Proof : Let, r = r1 + r2 where r1 and r2 be the regular expressions.
There exists two NFA's.
M1 = (Q1, Σ1, δ1, {f1})
M1 = (Q2, Σ2, δ2, {f2})
L(M1) = L(r1): Means the language stated by r1 is same which is represented by M1. Similarly L(M2) = L(r2).
Q1 represents the set of all the states in machine M1.
Q2 represents the set of all the states in machine M2.
It can be represented as,

We assume that Q1 and Q2 are totally disjoint. We will now assume q0 as a new initial state and f0 be the new
final state. Then we will form new machine M as
M = ((Q1 U Q2 U {q0, f0}), (Σ1 U Σ2), δ, q0{f0})
This shows that L(M) = L(M1) U L(M2)
i.e. L(R) = L(r) = L(r1) U L(r2)
The machine designed for L(r1) U L(r2) shows that language Ri is regular.
Q.7 Verify whether L = {a2n |n ≥1} is regular. AU: May-07
Ans. Refer similar example 2.6.2.
Q.8 State pumping lemma and its advantages. AU: Nov.-14, Dec.-07, 08, 13, 17

136
Course Code/Title: CS3401/Theory of Computation

Ans.: Pumping lemma: Let L be a regular set. Then there exists a constant n such that if z is any word in L
such that |z| ≥ n then we can write z = uvw such that |uv| <n and |v| ≥ 1 for all i ≥ 0 and uv1w is in L. The n
indicates number of states in FA and should not be greater than the number of states.
The advantage of pumping lemma is that this theorem is used to check whether given language is regular or
not.
Q.9 Show that the complement of a regular language is also regular. AU: Dec.-07
Ans. If L is a regular language, then its complement denoted by L' is also regular. To prove this, consider that
language L is accepted by finite automaton M. Now all the words accepted by language L will reach to final
state of machine M. If we change all the states of M to non-final states and all the non-final states of M to
final state we get a new FA which is denoted by M'. Now this M' will accept all the words not belonging to L
and reject all the words belonging to L. That means M' will accept the language L'. Thus there exists FA
which accepts L'. Hence L' which is complement of L is also regular.
Q.10 Construct a DFA for the regular expression aa*bb*. AU : May-08
Ans. The DFA for aa*bb* is -

The state q0 is a start state and state q2 is a final state.

Q.11 Show that the complement of regular language is also regular. AU: Dec:-08
Ans. Refer answer of Q.9
If L is a regular language, then its complement denoted by L' is also regular. To prove this, consider that
language L is accepted by finite automaton M. Now all the words accepted by language L will reach to final
state of machine M. If we change all the states of M to non-final states and all the non-final states of M to
final state we get a new FA which is denoted by M'. Now this M' will accept all the words not belonging to L
and reject all the words belonging to L. That means M' will accept the language L'. Thus there exists FA
which accepts L'. Hence L' which is complement of L is also regular.
Q.12 Show that ϕ is ϵ by constructing its NFA using Thomson's construction. AU: Dec.-08
Ans. The Thomson's construction for ϕ* will be

Note that is represented by q1 to f1. We can reach to a final state f0 from q0 with input ε. Hence ϕ* = ε is
shown by above figure.
Q.13 Construct an NDFA for all strings over alphabet = {a, b} that contains a substring 'ab'. AU: May-09
137
Course Code/Title: CS3401/Theory of Computation

Ans. The NDFA over Σ = (a, b) is -

The transition table will be

Q.14 Write regular expressions for the following language over the alphabet Σ = {0,1}. "The set of all strings
not containing 101 as a substring". Provide justification that your regular expression is correct. AU : May-09
Ans. We will first construct DFA for the language containing 101 as substring.

Now, just change the non-final states to final states and make final state as non-final state. The DFA then
becomes –

The regular expression for above DFA will be

138
Course Code/Title: CS3401/Theory of Computation

r.e. = 0*(1*(00*)*)*
Q.15 Prove or disprove the following for regular expression (a+b) + (cd) for Σ = {a,b,c,d}. AU: May-09
Ans.: To prove whether or not given language is regular or not following theorem is used -
"For every regular language there exists a finite automata".
If we could be able to build the FA for given expression then that expression is side to be regular. Hence

The NFA with ε can be built for given expression.

Hence the given expression is regular.
Q.16 What is [10,11]* ? (Write atleast first seven terms). AU: Dec.-09
Ans.: The {10+ 11}* is a set containing the strings of any combination of 10 and 11. This set also contains &
or null string.
The items of this set are
{ε, 10, 11, 1010, 1011, 1111, 1110, 111111, 101010, ...}
Q.17 Let L= {W: W ϵ {0, 1}* W does not contain 00 and is not empty}. Construct a regular expression that
generates L} AU : May-10
Ans: We will first build a finite automata for the language accepting the strings containing 00.

Now to accept the language which does not contain 00, we will change the non final state to final state and
final state to non final state.
The regular expression will be (01+ 1) + (10+ 1) + 0.

139
Course Code/Title: CS3401/Theory of Computation

Q.18 Is the set of strings over the alphabet {0} of the form 0n where n is not a prime is regular ? Prove or
disprove. AU: Dec.-11
Ans. Let us assume that L is a regular language n is not a prime number.
Let zϵL, L = 0n
|z| = uvw, here i = 1.
Now consider L = uvi w where i = 2
= u v. vw
That means adding 1 to n, we get
n < |uvvw|
n < n+1
But (n + 1) can be a prime number. Hence our assumption becomes contradictory to it. This shows that L is
not regular language.
Q.19 Construct regular expression for the language over the set ẑ = {a,b} in which total number of a's are
divisible by 3.
Ans. r.e. = (b* ab* ab* a)*
Q.20 Find out the language generated by the regular expression (0+1)*.
Ans.: L = {ε, 0, 1, 00, 11, 01, 10,111, ....}
L = {Any number of 0's and 1's including nullstring}
Q.21 What is the closure property of regular set s?
Ans.: If certain languages are regular and language L is formed by them by certain operations such as (union,
concatenation and so on) and if we find L as regular, then this property is called closure property of regular
sets.
Q.22 Mention the applications of pumping lemma.
Ans.: 1. Pumping lemma is used for deciding whether or not the given language is regular.
2. It is also useful for determing whether L is accepted by a regular expression or not.
Example 1:
L = {0n1n} is not regular.
L = {0P|p-is a prime number}
Example 2:
All these languages are non-regular languages and this can be proved by pumping lemma.
Q.23 Is it true that the language accepted by NFA is different from regular language? Justify your answer.
Ans. The language accepted by NFA is always regular. Because any NFA is equivalent to DFA. And if we
represent certain language by NFA then we can definitely represent it using DFA. The regular language is a
140
Course Code/Title: CS3401/Theory of Computation

kind of language which can be represented by DFA. Hence the language accepted by NFA is not different
from regular language.
Q.24 Give regular expression to describe an identifier and positive integer.
Ans.: id = (a - zA - Z) (a - zA - Z 0-9)*
P = (0-9)+
Q.25 Find the string of minimum length in {0,1}* NOT in the language corresponding to the given regular
expressions.
a) 0* (100*) * 1* b) (1+01) (0 +01) *
Ans. a) {110} € 0* (100*)* 1*.
b) ϕ.
Q.26 Design FA that accepts {0,1}*.
Ans.:

Q.27 Write a regular expression which generates strings with at least one 0 and one 1.
Ans. r.e. = = (0+ 1*) (1+ 0*) (0+1)*
Q.28 Give the operations that satisfy closure properties of regular languages.
Ans. The operations are union, intersection, complement, difference, reversal, concatenation, reversal,
homomorphism, inverse homomorphism.
Q.29 Give a regular expression for the set of all strings having odd number of 1's.
Ans.: r.e. = 1(0+11)*
Q.30 State the precedence of regular expression operators.
Ans.:
1. The star operator is having highest precedence.
2. The dot operator (concatenation) has the next highest position,
3. Final precedence is given to + i.e. union operation. The union is an associative operator.
Q.31 What does regular expression (a/b) * denote ?
Ans. The strings generated by the given expression are {ε, a, b, aa, bb, ab, ba, ....} This denotes the language
L = {Any number of a's and/or b's including null string}.
Q.32 Give the regular expression for set of all strings ending in 00. AU: Dec.-10
Ans. r.e. = = (0+1)* 00

141
Course Code/Title: CS3401/Theory of Computation

Q.33 Construct NFA for regular expression a*b*. AU: May-12

Ans.:

Q.34 Is regular set closed under complementation? Justify. AU : May-12

Ans. Yes regular set is closed under complementation. The regular set is denoted by the regular languages
and regular languages are closed under complementation. Refer answer of Q.9.
Q.35 Differentiate regular expression and regular language. AU : Dec.-12
Ans.
Regular expression over Σ can be defined by the operations such as r+s, rs and r* where r* and s both are
regular expressions. The regular languages over Σ is defined as -
1. An empty set ϕ.
3. L1 U L2 are regular languages.
2. L1 L2 are regular languages.
4. L1* is regular language.
The regular language is elaboration of regular expression. The regular expression denotes the tiny logical
unit. It is typically used to represent pattern.
Q.36 Name any four closure properties of regular languages. AU: May-13
Ans.:
1. The union of two regular languages is regular.
2. The intersection of two regular languages is regular.
3. The complement of regular language is regular.
4. The closure operation on a regular languages is regular.
Q.37 Construct NFA equivalent to the regular expression (0 + 1) 0 1. AU: Dec.-13
Ans. :

Q.38 What is meant by equivalent states in DFA ? AU: Dec.-07

Ans. The two states are said to be equivalent if there are same inputs coming to the state and same output
going out from the states.

142
Course Code/Title: CS3401/Theory of Computation

Q.39 Construct a finite automation for the regular expression 0*1*.

Ans. :

Q.40 Prove or disprove that (r+s)* = r* +s*.

Ans.:

Note that in R.H.S. there is no combination of r and s together.

Hence L.H.S. ≠ R.H.S.
i.e. (r + s)* = r*+s*.
Q.41 Write regular expression for the set of strings over {0, 1} that have at least one. AU: Dec.-15
Ans.: r.e. = (0*1+) (0+1)*
because 1+ = 11*. That means at least one 1 is always present in regular expression.
Q.42 State the pumping lemma for regular languages. AU: May-16, Dec.-18
Ans. Let, L be regular set. Then there is a constant n such that if z is any word in L and |z| ≥ n, we can write z
= uvw such that |uv| ≤ n, |v| ≥ 1 for all i ≥ 0, then uviw is in L.
Q.43 What are closure properties of regular languages. AU: Dec.-16
Ans. Following are closure properties of regular languages:
1) The union of two regular languages is regular.
2) The intersection of two regular languages is regular.
3) The complement of a regular language is regular.
4) The difference of two regular languages is regular.
Q.44 Generate NFA - ε to represent a* b|c AU: May-17
Ans.:

143
Course Code/Title: CS3401/Theory of Computation

Q.45 Show whether a language L = {0n 12n|n> 0} is regular or not using pumping lemma. AU: May-17
Ans.: We will map W = xyz for given string W ϵ L = {0n 12n}
Suppose W = 001111
If we map W = xyz then -
W = 0 011 11
x = 0, y = 011 z = 11 ...(1)
By pumping lemma if W = xyi z ϵ L then the language is regular.
For equation (1) we have W = xyiz. We assume i = 2 then string becomes
W = xyyz
= 001101111
W = 0212 0114 € L
This shows that given language is not regular.
Q.46 Give language of regular expression a ? (b|c)*. AU: May-17
Ans. The ? denotes preceding character occurs for one or zero times. The * means the string occurs for any
number of times. The language contains a string which may begin with single a or no a and followed by any
number of b's and c's.
Q.47 Write regular expression for the set of all strings of 0's and 1's not containing 101 as substring. AU:
May-18
Ans. :
r.e. = 0*(1*000*)*1*0*
In above expression all 1's are followed by 00. This pattern is repeated for any number of times.

Unit III: Context Free Grammar and Push Down Automata

Syllabus

144
Course Code/Title: CS3401/Theory of Computation

Types of Grammar - Chomsky's hierarchy of languages - Context - Free Grammar (CFG) and Languages -
Derivations and Parse trees - Ambiguity in grammars and languages - Push Down Automata (PDA):
Definition - Moves - Instantaneous descriptions - Languages of pushdown automata- Equivalence of
pushdown automata and CFG - CFG to PDA - PDA to CFG - Deterministic Pushdown Automata.

Types of Grammar and Chomsky's Hi Hierarchy of Languages

The Chomsky's Hierarchy represents the class of languages that are accepted by different machine. The
category of languages in Chomsky's Hierarchy is as given below –

This is a hierarchy therefore every language of type 3 is also of type 2, 1 and 0. Similarly every language of
type 2 is also of type 1 and 0 etc.

Type 3 Regular languages

Regular languages are those languages which can be described using regular expressions. These languages
can be modelled by NFA or DFA.
Type 2 Context free languages

145
Course Code/Title: CS3401/Theory of Computation

The context free languages are the languages which can be represented by Context Free Grammar (CFG).
The production rule is of the form
Α→α
where A is any single non-terminal and a is any combination of terminals and non-terminals.
A NFA or DFA cannot recognize strings of this language because these automata are not having "stack" to
memorize. Instead of it the Push Down Automata can be used to represent these languages.
Type 1 - Context sensitive languages
The context sensitive grammars are used to represent context sensitive languages. The context sensitive
grammar is follows the following rules -
1. The context sensitive grammar may have more than one symbol on the left hand side of their production
rules.
2. The number of symbols on the left hand side must not exceed the number of symbols on the right hand
side.
3. The rule of the form A → ε is not allowed unless A is a start symbol. It does not occur on the right hand
side of any rule.
The automaton which recognizes context sensitive languages is called linear bounded automaton. While
deriving using context sensitive grammar the sentential form must always increase in length every time a
production rule is applied. Thus the size of a sentential form is bounded by a length of the sentence we are
deriving.
Type 0 Unrestricted languages
There is no restriction on the grammar rules of these type of languages. These languages can be effectively
modeled by Turing machines.
Context-Free Grammar (CFG) and Languages
Definition :
The context free grammar can be formally defined as a set denoted by G = (V, T, P, S) where V and T are set
of non-terminals and terminals respectively. P is set of production rules, where each production rule is in the
form of
non-terminal → non-terminals
or non-terminal → terminals
S is a start symbol.
For example,
P = {S→ S + S
S→ S * S
S→ (S)
S→ 4}

146
Course Code/Title: CS3401/Theory of Computation

If the language is 4 + 4 * 4 then we can use the production rules given by P. The start symbol is S. The
number of non-terminals in the rules P is one and the only non terminal i.e. S. The terminals are +, *, (,) and
4.
We are using following conventions.
1. The capital letters are used to denote the non-terminals.
2. The lower case letters are used to denote the terminals.
Example: The formation of production rules for checking syntax of any English statement is
SENTENCE → NOUN VERB
NOUN→ Rama / Seeta / Gopal
VERB→ goes / writes / sings
Thus if want to derive a string "Rama sings" then we can follow the above rules.
Derivations
AU May-10,11,12,16, Dec.-11,14,16,17,18, Marks 16
The production rules are used to derive certain strings. We will now formally define the language generated
by grammar G = (V, T, P, S). The generation of language using specific rules is called derivation.
Definition :
Let G = (V, T, P, S) be the context free grammar. If A →ẞ is a production of P and a and y are any strings
from non-terminals or terminals i.e. in (VUT)* then a Ay → aẞy.
Suppose a1, a2, a3,... am are strings in (VUT)*, m ≥ 1.
a1 ⇒ a2
a2 ⇒ a3
.
.
am-1 ⇒ am
Then we can say that a1 ⇒ am
The language generated by G is denoted by L(G). The language L is called context free language CFL if
L(G) is for CFG.
For example
G = ({S, B} {a, b}, {S → a B b, S)
B → bbb}
is a grammar. Then we can derive a string abbbb as -
i) We will first start from start symbol S

147
Course Code/Title: CS3401/Theory of Computation

S⇒aBb
ii) Then we will replace B by bbb
S ⇒ a B b ⇒ a bbbb
Thus we can obtain the desired language L by certain rules. The language L can be described as a language
which starts with letter a and having 4 b's following. Let us solve some examples for derivation of CFG.
Solved Examples
Example 3.3.1 Try to recognize the language L for given CFG.
G = [{S}, {a,b}, P, {S}]
where P = {S → aSb, S → ab}
Solution: Since S → a S b | a b is a rule. | indicates the 'or' operator.
S →aSb
If this rule can be recursively applied then,
S
aSb
↓
aaSbb
↓
aaaSbbb
and if finally we can put S→ ab then it becomes aaaa bbbb. Thus we can have any number of a's first then
equal number of b's following it. Hence we can guess the language as {L=an bn where n≥1}. The only way to
recognize the language is to try out various strings from the given production rules. Simply by observing the
derived strings, one can find out the language getting generated from given CFG.
Example 3.3.2 Construct the CFG for the regular expression (0+1)*
Solution: The CFG can be given by,
P = {S → 0S | 1S
S → ε}
The rules are in combination of 0's and 1's with the start symbol. Since (0+1)* indicates (ε, 0, 1, 01, 10, 00,
11, ...) in this set ε is a string. So in the rules we can set the rule S → ε.
Example 3.3.3 Construct a grammar generating
L = w c wT where we w ϵ {a,b}*
Solution: The strings which can be generated for given L is {aacaa, bcb, abcba, bacab ...}
The grammar could be
S→aSa
148
Course Code/Title: CS3401/Theory of Computation

S→ b S b
S→c
Since the language L = w c wT where w ϵ (a + b)*
Hence S → a S a or S → b S b. The string abcba can be generated from given production rules as
S
aSa
abSb
abcba

Thus any of this kind of string could be derived from the given production rules.
Example 3.3.4 Construct CFG for the language L which has all the strings which are all palindrome over Σ =
{a,b} AU: Dec.-17, Marks 7
Solution: As we know the strings are palindrome if they posses same alphabets from forward as well as from
backward.
For example, the string "madam" is a palindrome because

Since the language L is over = (a, b). We want the production rules to be build a's and b's. As ε can be the
palindrome, a can be palindrome even b can be palindrome. So we can write the production rules as
G = ({S}, {a, b}, P, S)
P can be
S→aSa
S→bSb
S→a
S→b
S→ε
The string abaaba can be derived as

149
Course Code/Title: CS3401/Theory of Computation

which is a palindrome.
Example 3.3.5 Construct CFG for the language containing all the strings of different first and last symbols
over Σ = {0,1}.
Solution: Since the problem statement says as if the string starts with 0 it should end with 1 or if the string
starts with 1 it should end with 0.
S→0A1|A0
A→0A|1A|ε
Thus clearly, in the above CFG different start and end symbols are maintained. The non terminal A → 0A |
1A | ϵ indicates (0+1)*. Thus the given CFG is equivalent to the regular expression [0 (0+1)*1+1(0+1)*0]
Example 3.3.6 Construct the CFG for the language L= an b2n where n ≥ 1.
Solution: Here the number of b's are doubled than a's so we can write
S → aSbb | abb
It is as simple as this!
Example 3.3.7 Build a CFG for the language L = {0i 1j 2k | j>i+k}.
Solution: As the language L = 0i 1j 2k such that j > i + k.
Hence we can rewrite L as

We can again rewrite L for simplification as –

150
Course Code/Title: CS3401/Theory of Computation

A→0A1|ε
B→1B|1
C→1C2|ε
Hence the CFG can be
S→ABC
A→0A1|ɛ
B→1B|1
C→1C2|ε
Example 3.3.8 Build a CFG for the language L = {0i 1j 2k | i = j}
Solution: As i = j and there is no condition on k. We can say that k is an arbitrary value. Then we rewrite L as
L = 0i 1j 2k
0i 1j = A
2k = B
S→AB
A→0A1|ε
B→2B|ε
Example 3.3.9 Obtain CFG for the language L = {0i 1j 2k | j≤ k}.
Solution: Here j≤ k. That means the language L has two variations.
L1 = 0i 1j 2j where k = j
L2 = 0i 1j 2k where k > j
Hence the required CFG can be
S→AB
A→0A|ε
B→1B2|C
C→2C|ε
Example 3.3.10 Consider the alphabet A = (a, b) and the language L= {bb, bab, baab, baaab, ...) over A. AU
May-10, Marks 16
i) Is A* finite or infinite? Give a brief reason for your answer. [2]
ii) Write down a regular expression that represents the above language L. [4]
iii) Write down a regular grammar which describes the above language L. [4]
iv) Draw the DFA corresponding to the above language L. [6]

151
Course Code/Title: CS3401/Theory of Computation

Solution: i) The A* is an infinite language, because there are any number of a's in the string and the string is
starting and ending with b. This leads to an infinite strings of the language.
ii) The regular expression will be = ba*b.
iii) The regular grammar G = (V, T, P, S) where, V is set of non terminals = {S, X, T}. T is the set of
terminals which is (a, b). P is a set of production rules as shown below -
{
S → bX
X → aX|aT|b
T→b
}
S is a start symbol.
This is a right linear grammar because the non-terminal appears at the right end of the rule.
iv) The DFA will be

Example 3.3.11 Construct a CFG for the set {ai bj ck | i ≠ j or j ≠ k} As there are two cases i ≠ j or j ≠ k. AU
May-11, Marks 6
Solution: Hence the production rules will be
S → R1 R2
R1 → aAbbBC | aaAbBC
R2 → AbBccC | AbbBcC
A → aA | ε
B → bB | ε
C → cC | ε
Example 3.3.12 If S → aSb|aAb, A → bAa, A → ba is the context free grammar. Determine the context free
language. AU Dec.-11, Marks 6
Solution: The strings generated by this grammar are (a ba b, aa babb, aaa bbaa bbb, ...) This denotes the
language L = {an bm am bn |n, m≥1}
Example 3.3.13 Find the context free langauge for the following grammars
1) S → aSbs | bSaS | ε
2) S → aSb | ab AU May-12, Marks 10

152
Course Code/Title: CS3401/Theory of Computation

Solution : 1) Let us derive some strings from given grammar.

From these derivations, we can observe that the derived strings contain equal number of a's and b's. Thus this
CFG denotes the language L containing equal number of a's and b's.
2) Refer example 3.3.1.
Example 3.3.14 Construct a context free grammar for {0m 1n | 1≤m≤n} AU: Dec.-14, Marks 4
Solution: G = (V, T, P, S) where
V = {S, A}
T = {0, 1}
P is a production rules set. It is given by
S → 0S1 | 0A |01
A → 1A | 1
Example 3.3.15 Construct a CFG for the regular expression (011 + 1) (01). AU May-16, Marks 6
Solution: The production rules are
S → AB
A→X|Y
B → 01
X → 011
Y→1
Example 3.3.16 Construct a context free grammar for the language.
L = {an | n is odd} AU: Dec.-16, Marks 6
Solution: The context free grammar G = (V, T, P, S)
Where
V = (S, T)
T = (a)
The S is a start symbol.

153
Course Code/Title: CS3401/Theory of Computation

The set of production rules P is

P = { S → aT
T → aaT | ε
}
• Simulation for string aaaaa
S
aT
aaaT
aaaaaT
aaaaa
Example 3.3.17 Give the regular expression of the language generated by the context free grammar (CFG)
given below:
S → aS | bS | a | b. Convert regular expression to ε - NFA. AU Dec.-18, Marks 7
Solution: We will first draw the FA for given CFG.

The regular expression is

r.e = (a+b)+
The NFA with ε is as designed below

Parse Trees
AU Dec.-03,04,05,10,12,14,15, May-04,05,09,13,16, Marks 16
154
Course Code/Title: CS3401/Theory of Computation

• Derivation trees is a graphical representation for the derivation of the given production rules for a given
CFG.
• It is the simple way to show how the derivation can be done to obtain some string from given set of
production rules.
• The derivation tree is also called parse tree.

• Following are properties of any derivation tree -

1. The root node is always a node indicating start symbol.
2. The derivation is read from left to right.
3. The leaf nodes are always terminal nodes.
4. The interior nodes are always the non-terminal nodes.
• For example,
S → bSb | a | b is a production rule. The S is a start symbol.
• The above tree is a derivation tree drawn for deriving a string bbabb. By simply reading the leaf nodes we
can obtain the desired string. The same tree can also be denoted by, Fig. 3.4.2

Relationship between Derivation and Derivation Trees

AU Dec.-03, 04, 05, 10, 12, 14, 15, May-04, 05, 09, 13, 16, Marks 16
Theorem: Let G = (V, T, P, S) be a context free grammar. Then S ⇒ a if and only if there is a derivation tree
in grammar G which gives the string a.

155
Course Code/Title: CS3401/Theory of Computation

OR
Theorem Let G = (V, T, P, S) be a context free grammar then prove that if the recursive inference procedure
tells us that terminal string w is in the language of variable A, then there is a parse tree with root A and yield
w. AU: Dec.-15, Marks 10
Proof: For a non-terminal S there exists S ⇒ w if and only if there is a derivation tree starting from root S
and yielding w. To prove this we will use method of induction.

… ,Sn. From S is that means S ⇒ S1, S2, ... Sn ⇒ a is input string.

Basis of induction: Assume that there is only one interior node S. The derivation tree yielding S1, S2, S3,

Induction hypothesis: We assume that for K-1 nodes the derivation tree can be drawn. We then can prove that
for K vertices also we can have a derivation tree. That means the input string a can be derived as S → S 1, S2,
S3, ….Sk. There are two cases: either Si may be a leaf variable or Si may be an interior node yielding a. The
S derives a by fewer number of K steps then a ϵ S1 S2 S3 …Sk.

If ai = Si then Si is leaf node (terminal) and if Si ⇒ ai then Si is an interior node. The tree for S1 S2 …Sk will
be shown in Fig. 3.3.4
We can also represent it as shown in Fig. 3.4.5.

156
Course Code/Title: CS3401/Theory of Computation

This proves that S ⇒ S1, S2, S3 …. Sn ⇒ a can be obtained.

Leftmost Derivation and Rightmost Derivation

AU: May-13,16, Dec.-10,15,18, Marks 9
• The leftmost derivation is a derivation in which the leftmost non-terminal is replaced first from the
sentential form.
• The rightmost derivation is a derivation in which rightmost non-terminal is replaced first from the
sentential form.
• For example
S → XYX
S → aYX
S → abX
S → aba
S → XYX
S → XYa
S → Xba
S → aba
Leftmost Derivation Rightmost Derivation
Note that we have replaced first X from left to right in leftmost derivation and XYX the last X i.e. the
rightmost symbol.
Examples for Understanding
Example 3.5.1 Let, G be the grammar
S → aB | bA
A → a | aS | bAA
B → b | bS | aBB
For the string baaabbabba. Find leftmost derivation, rightmost derivation and Parse tree. AU: Dec.-10,
Marks 9
Solution :
PPPPPPPPPPPPPPPPPPPPPPPPPPP
Example 3.5.2 Consider the following productions
S → aB bA
A → a | aS | bAA

157
Course Code/Title: CS3401/Theory of Computation

B → b | bS | aBB
For the string aaabbabbba, Find
1) Leftmost derivation
2) Rightmost derivation
3) Parse tree AU May-13, Marks 8
Solution: For leftmost derivation and parse tree refer answer of Q.10 from Two Marks Questions with
Answers
Rightmost Derivation :
Pppppppppppppppppppppppp
Example 3.5.3 Given the grammar G = (V, Σ, R, E) where
V = {E, D, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, -, *, /, ()},
Σ = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, -, *, /, ()}, and R contains the following rules:
E→D|(E)| E+ E |E + E| E* E |E| E / E
D → 0|1|2|3| ...9
find a parse tree for the string 1+2*3. AU: Dec. 15, Marks 6
Solution: The parse tree
pppppppppppppppppppppppppppppppp
Example 3.5.4 Show the derivation steps and construct derivation tree for the string 'ababbb' by using
leftmost derivation with the grammar.
S → ABIɛ
A → aB
B → Sb. AU May-16, Marks 5
Solution :
Ppppppppppppppppppppppppppppppppp
Example 3.5.5 Consider the context free grammar (CFG) given below. Give the leftmost derivation for the
string bbaa using the grammar.
S → bS | aT | ε
T → aT | bU | ε
U → aT | ɛ
AU Dec.-18, Marks 2
Solution :
pppppppppppppppppppppppppppp
158
Course Code/Title: CS3401/Theory of Computation

159
Course Code/Title: CS3401/Theory of Computation

160
Course Code/Title: CS3401/Theory of Computation

161
Course Code/Title: CS3401/Theory of Computation

162
Course Code/Title: CS3401/Theory of Computation

163
Course Code/Title: CS3401/Theory of Computation

164
Course Code/Title: CS3401/Theory of Computation

165
Course Code/Title: CS3401/Theory of Computation

166
Course Code/Title: CS3401/Theory of Computation

167
Course Code/Title: CS3401/Theory of Computation

168
Course Code/Title: CS3401/Theory of Computation

169
Course Code/Title: CS3401/Theory of Computation

170
Course Code/Title: CS3401/Theory of Computation

171
Course Code/Title: CS3401/Theory of Computation

172
Course Code/Title: CS3401/Theory of Computation

173
Course Code/Title: CS3401/Theory of Computation

174
Course Code/Title: CS3401/Theory of Computation

175
Course Code/Title: CS3401/Theory of Computation

176
Course Code/Title: CS3401/Theory of Computation

177
Course Code/Title: CS3401/Theory of Computation

178
Course Code/Title: CS3401/Theory of Computation

179
Course Code/Title: CS3401/Theory of Computation

180
Course Code/Title: CS3401/Theory of Computation

181
Course Code/Title: CS3401/Theory of Computation

182
Course Code/Title: CS3401/Theory of Computation

183
Course Code/Title: CS3401/Theory of Computation

184
Course Code/Title: CS3401/Theory of Computation

185
Course Code/Title: CS3401/Theory of Computation

186
Course Code/Title: CS3401/Theory of Computation

187
Course Code/Title: CS3401/Theory of Computation

188
Course Code/Title: CS3401/Theory of Computation

189
Course Code/Title: CS3401/Theory of Computation

190
Course Code/Title: CS3401/Theory of Computation

191
Course Code/Title: CS3401/Theory of Computation

192
Course Code/Title: CS3401/Theory of Computation

193
Course Code/Title: CS3401/Theory of Computation

194
Course Code/Title: CS3401/Theory of Computation

195
Course Code/Title: CS3401/Theory of Computation

196
Course Code/Title: CS3401/Theory of Computation

197
Course Code/Title: CS3401/Theory of Computation

198
Course Code/Title: CS3401/Theory of Computation

199
Course Code/Title: CS3401/Theory of Computation

200
Course Code/Title: CS3401/Theory of Computation

201
Course Code/Title: CS3401/Theory of Computation

202
Course Code/Title: CS3401/Theory of Computation

203
Course Code/Title: CS3401/Theory of Computation

204
Course Code/Title: CS3401/Theory of Computation

205
Course Code/Title: CS3401/Theory of Computation

206
Course Code/Title: CS3401/Theory of Computation

207
Course Code/Title: CS3401/Theory of Computation

208
Course Code/Title: CS3401/Theory of Computation

209
Course Code/Title: CS3401/Theory of Computation

210
Course Code/Title: CS3401/Theory of Computation

5
Course Code/Title: CS3401/Theory of Computation

6
Course Code/Title: CS3401/Theory of Computation

7
Course Code/Title: CS3401/Theory of Computation

8
Course Code/Title: CS3401/Theory of Computation

9
Course Code/Title: CS3401/Theory of Computation

10
Course Code/Title: CS3401/Theory of Computation

11
Course Code/Title: CS3401/Theory of Computation

12
Course Code/Title: CS3401/Theory of Computation

13
Course Code/Title: CS3401/Theory of Computation

14
Course Code/Title: CS3401/Theory of Computation

15
Course Code/Title: CS3401/Theory of Computation

16
Course Code/Title: CS3401/Theory of Computation

17
Course Code/Title: CS3401/Theory of Computation

18
Course Code/Title: CS3401/Theory of Computation

19
Course Code/Title: CS3401/Theory of Computation

20
Course Code/Title: CS3401/Theory of Computation

21
Course Code/Title: CS3401/Theory of Computation

22
Course Code/Title: CS3401/Theory of Computation

23
Course Code/Title: CS3401/Theory of Computation

24
Course Code/Title: CS3401/Theory of Computation

25
Course Code/Title: CS3401/Theory of Computation

26
Course Code/Title: CS3401/Theory of Computation

27
Course Code/Title: CS3401/Theory of Computation

28
Course Code/Title: CS3401/Theory of Computation

29
Course Code/Title: CS3401/Theory of Computation

30
Course Code/Title: CS3401/Theory of Computation

31
Course Code/Title: CS3401/Theory of Computation

32
Course Code/Title: CS3401/Theory of Computation

33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71