2 Finite Automata

Chapter 2
2.1 FINITE AUTOMATA

Definitions

It is a mathematical model which contains a finite number of states and transitions

among states in response to inputs.

FINITE AUTOMATA

Finite Finite
automata automata
without with
output output

Deterministic Non-Deterministic Epsilon

Moore Mealy
finite finite Non-Deterministic
finite automata machine machine
automata (DFA) automata (NFA)
(∈-NFA)

Finite automata without output:

Input tape

b a b a a a

Head

q0 b q1 a q2 b q3
Finite
a control
memory
Finite Automata

qn a qn–1 q4

Fig. 2.1 Diagram of Finite Automata

17
Chapter 2

Input tape: It consists of many cells where each cell can have only one
symbol. Input tape contains a single string.

Head: It reads one symbol at a time from an input string.

Finite control memory: Memory which is having the finite number of states.

2.2 FINITE ACCEPTOR (FINITE AUTOMATA WITHOUT OUTPUT)

Deterministic finite automata (DFA)
y A DFA is set of 5 tuple and defined as:
M = {Q, ∑ , δ , q0, F}
Where Q : Finite set of states
∑ : Input alphabet
δ : Transition function
q0 : Initial State
F : A finite set of final states
Here δ : Transition function

Q× ∑ → Q
↓

Next
State

{A, B, C} × {a, b} → Only deterministic output will come.

(A,a)
(A, b) A
(B, a) B
(B, b) C
(C, a)
(C, b)

Fig. 2.2

y  FA is a finite Automata in which, from every state on every input

D
symbol, exactly one transition should exist.
y DFA cannot use empty string transition.
y In DFA, if any string terminates in a state which is different from
accepting state, then DFA rejects that string.
Finite Automata

y All DFA are NFA.

18
 Chapter 2
SOLVED EXAMPLES

Q1

Language accepted by above Finite Automata?

Sol: L = {a, aa, aaa, aaaa, ba, bbbba, bababaaaa,……………} = Set of all strings ends
with ‘a’ over ∑ = {a, b}

Q2

Language accepted by above Finite Automata?

Sol: L = {ba, bab, baa, aba, abaa, abab, ………} = Set of all strings containing “ba”
as a substring over ∑ = {a, b}.

Rack Your Brain

Finite Automata

How many number of final state require to accept & in minimal finite
automata?

19
Chapter 2

Minimal DFA: When all the states in a DFA are distinguishable, i.e. no two
states in a final DFA are equivalent. The DFA is known as minimal DFA.

SOLVED EXAMPLES

Q1

Sol: L = {∈, a, b, aa, bb, ab, ba, aaa, ………………}

DFA:

Transition table:

Q2

Sol: L = {a, b, ab, ba, aa, bb, ……….……………}

DFA:

Transition table:
Finite Automata

20
 Chapter 2
Q3

Sol:
a, aa, aaa, aaaa, ................
 
ab, aab 
 
L = aba 
abb 
 
  

DFA:
a, b

q0 a q1

Dead
q2
State

a,b

y If any string starts with ‘a’, then it will be accepted by the DFA.
Let’s consider an example.
String w = aab
d (q0, a) = q1
d (q1, a) = q1
d (q1, b) = q1 (accepted by DFA)
y But if the string starts with ‘b’, it directly goes to the dead state and get
rejected by the DFA.
Let’s consider an example.
String w = ba
d (q0, b) = q2
d (q2, a) = q2 (Dead state)
Thus, string ba is rejected (not accepted by DFA).

Dead state: It is a rejecting state i.e a non final state from which there is
no path to the final state.
Finite Automata

Once we reach to dead state, there is no way to reach the final state.

21
Chapter 2

Transition table:

Q4

Sol: L = {ab, aab, abb, aaab, abab, aabb, ………….}

DFA:
a b

a b
q0 q1 q2

b a

q3

a,b

Transition table:

Q5

Sol: L = {ab, aba, aab, ………….………….}

DFA:
b a a, b

a b
Finite Automata

q0 q1 q2

22
 Chapter 2
Q6

Sol: L = {a, aa, ba, aaa, aba, ………….………….}

DFA:
b a

q0 a q1

Q7

Sol: L = {ba, aba, bba, aaba, ………….………….}

DFA:
a b

q0 b q1 a q2

b
a

Previous Years’ Question

1 (GATE 2009)
1 0

0 0

1
The above DFA accepts the set of all strings over {0, 1} that
1) Begin either with 0 or 1 2) End with 0
3) End with 00 4) Contain the substring 00
Sol: 3)
Finite Automata

23
Chapter 2

Q8

Sol: L = {a, aa, aba, aaa, ………….………….}

DFA:

a b

a b q2
q0 q1

a
b

q3

a,b

Q9

Sol: L = {a, b, aaa, bbb, aba, bab, ………….………….}

DFA:
a b

a q1 b
q0 q2

a
b

b q3

b a

q4

a
Finite Automata

24
 Chapter 2
Q10

Sol: L = {ab, ba, aab, abb, baa, ………….………….}

DFA:

a b

q0 a b
q1 q2

b a

b q3

a b

q4

Q11

Sol: L = {aaaa, baaaa, aaaab, aaaaa, ………….………….}

DFA:

b a, b

a a a q3 a q4
q0 q1 q2

b
b

b
Finite Automata

25
Chapter 2

Q12

Sol: L = {aaa, baaa, abbb, bbba, ………….………….}

DFA:
a, b

a q1 a q2 a q3
q0

b
a b
b a b

q4 q5
b

Q13

Sol: L= {∈, abab, abababab, .............aa,bb, aaa, .................................}

DFA:
b a b

q0 a b q2
q1

b a
q3

Q14
Finite Automata

26
 Chapter 2
Sol: L = {aaaab, baaab, …………………}
DFA:
a, b

a,b a,b a,b a,b b

q0 q1 q2 q3 q4 q5

q6

a, b

Q15

Sol:
b
b a

a a b
q0 q1 q2 q3

Q16
i) L
ii) L
iii) L

Sol: i) Length of the string is exactly 2 i.e. |w| = 2

a, b

a, b a, b a, b
q0 q1 q2 q3
Finite Automata

27
Chapter 2

ii) Length of the string is atleast 2 i.e. |w| ≥ 2

a, b

a, b a, b
q0 q1 q2

iii) Length of the string is at most 2, i.e. |w| ≤ 2

a, b

q0 a, b q1 a, b q2 a, b q3

Note:

Rack Your Brain

If L is a non-empty language such that any win L has length atleast

n, then any DFA accepting L must have atleast n +1 states. this
statement true (or) false?

Q17
L
L
L

Sol: i) All even length strings over ∑ = a,b { }

Finite Automata

|w| mod 2 = 0
L = { ∈ , aa, bb, ab, …………..}

28
 Chapter 2
DFA:

a, b
q0 q1

a, b

ii) All odd length strings over ∑ = a,b { }

Odd length strings meSol: |w| mod 2 = 1
DFA:

a, b
q0 q1

a, b

iii) { }
All strings whose length is divisible by 3 over ∑ = a,b

|w| mod 3 = 0

∈, aaa, aaaaaa, ..................

 
 aab  
L= 
   
 bbb  
 

q0 a, b q1 a, b
q2

a, b

Note:

Q18
Finite Automata

29
Chapter 2

Sol: i) L = {aa, baa, aba, aab, bbaa,…………….}

DFA:

b b b a, b

a a a
q0 q1 q2 q3

0 a's 1 a's 2 a's 3 a's

ii) L = {aa, aba, aaa, aaab,…………….}

DFA:
b b a, b

a a
q0 q1 q2

iii) L = {∈, a, ab, aa, aba,…………….}

DFA:
b b b a, b

a q1 a q2 a
q0 q3

Note:
d

A
A
Finite Automata

30
 Chapter 2
Grey Matter Alert!

{ }
Number of states in minimal DFA which accepts all the strings over ∑ = a,b such

that:
a) 
Number of a’s is ‘atleast m’ and number of b’s is ‘atleast n’ = (m + 1)(n + 1)
b) 
Number of a’s is ‘exactly m’ and number of b’s is ‘exactly n’ = (m + 1) (n + 1) + 1
(because of trap state, we require one more state).
c) 
Number of a’s is ‘atmost m’ and number of b’s is ‘atmost n’ = (m + 1)(n+1) + 1

Previous Years’ Question

The minimum possible number of states of a deterministic finite automaton that

accepts the regular language

L= { { }
w 1aw2 | w 1 , w2 ∈ a,b *,| w 1 |= }
2,| w2 | ≥ 3 is ________

Sol: Range: 8 to 8 (GATE 2017 (Set-2))

SOLVED EXAMPLES

Q19
Sol:
= L {a bn m
| n,m ≥ 1}
{ }
= ab, aab, abb, aabb, ..................

DFA:
a b

a b

b
a
Finite Automata

a, b

31
Chapter 2

Q20
Sol:
= L {a bn m
| n,m ≥ 0 }
{
= ∈, a,b, ab, aa,bb, ................... }
DFA:
a b a, b

b a

Q21
Sol:
=L {a b c | n,m,l ≥ 1}
n m l

{
= abc, aabc, abbc, abcc, .................... }
a b c

a b c

c a
b,c a,b

a,b,c

Q22

Sol: i) L= {a n
n ≥ 0,n ≠ 3 }
{
= ∈, a, aa, aaaa, ................. }
Finite Automata

32
 Chapter 2
a

a a a a

Not
accepting
3a’s

ii) L= {a n
n ≥ 0,n ≠ 2,n ≠ 4 }
{
= ∈, a, aaa, aaaaa, ................. }
a

a a a a a

Not Not
accepting accepting
2a’s 4a’s

Rack Your Brain

Construct the minimal DFA’s for the language L = (ab | n20) u (b’a | n21}

SOLVED EXAMPLES
Q1

Sol: Divisible by 2, so two remainders are

DFA:
0 1

q0 1 q1

(101)2 = (5)10 = Not accepted by DFA:

Finite Automata

(110)2 = (6)10 = Accepted by DFA

Transition table:

33
Chapter 2

Q2

0
Sol: Divisible by 3, so remainders are 1
2
DFA:
0 1

1 0
q0 q1 q2

1 0

Transition table:

Q3

0
Sol: Divisible by 4, so remainders are 1
2
3
Finite Automata

Transition table:

34
 Chapter 2
Here, we can merge q1 and q3 states as one state.

DFA:
0 1

1 0
q0 q13 q2
1

Q4

Sol: Transition table:

Finite Automata

⇒ Here two rows cannot be merged. Since all are different.

So, the minimum DFA will contain 7 states.

35
Chapter 2

Q5

Sol: This problem belongs to below NOTE (Case 3).

Here n = 6 (even) but not in power of 2.
n = 21 * 3
So, minimal DFA contains (1 + 3) = 4 states
We can also prove it in descriptive way.
Transition table:

⇒ Here, we can merge states q1 and q4 as q14.

Similarly, we can merge states q2 and q5 as q25.
Hence, transition Table will become:

Note:
Finite Automata

36
 Chapter 2
SOLVED EXAMPLES

Q1

Sol: Divisible by 4, so remainders are

Input = {0, 1, 2}

Transition table:

0
0 2 0 2

1 1
q0 q1 q2 q3
1
2 1

2
0

Operations on DFA:
Union:
DFA which accepts all strings starting and ending with different symbols
{ }
over ∑ = a,b .

L1 = {ab, aab, abb, ……………..}

Starts with ‘a’ and ends with ‘b’.
DFA:
Finite Automata

37
Chapter 2

a b

a b
q0 q1 q2

b a

q3

a,b

L2 = {ba, baa, bba, ……………..}

= Starts with b and ends with a
DFA:
b a

b a
q0 q1 q2

b
a

q3

a,b

DFA for L 1 ∪ L2:

a b

q0 a q1 b q2

b a

b q3

a b

q4
Finite Automata

Concatenation:

38
 Chapter 2
{ }
DFA that accepts all strings over ∑ = a,b which starts with a and ends
with b.
L1 = {Starting with a}
= {a, aa, ab, aab, ……………………}

a, b

q0 a q1

a, b

L2 = {Ending with b}
= {b, ab, bb, aab, ……………………}
a
b
q1 b q2

Now DFA for L1.L2:

a b

a b
q0 q1 q2

a
b

a, b
Finite Automata

Cross product:

39
Chapter 2

SOLVED EXAMPLES
Q1

Sol: L1 = {even number of a’s} = { ∈ , aa, baa, ……………..}

DFA:
b b
a

A B

L2 = {even number of b’s} = { ∈ , bb, abb, ……………..}

DFA:
a a
b

C D

Cross product:
{A, B} × {C, D} = {AC, BC, AD, BD}
Where final state = {AC} because A and C are both final states in
respective DFA for L1 and L2.
Initial State = {AC} because A and C are both initial states in
respective DFA for L1 and L2.

DFA for cross product:

a

AC BC

a
b b b b
a

AD BD

a
Finite Automata

40
 Chapter 2
Q2

Sol: na(w) ≅ 0 mod 3 & nb(w) ≅ 0 mod 2

DFA:
a

a a

b b b b b b

a a

Total number of states = 3 × 2 = 6

Complementation:
eg 1: L = set of all strings over ∑ = {a, b} of even length
= { ∈, ab, aa, bb, aaaa, ……………………….}
Sol: DFA:
a, b

A B

a, b

Now, L2 = set of all strings over ∑ ={a,b} of odd length

= {a, b, aaa, aab, …………….}

L=
2
L=
1
Complement of L 1

DFA for L2:

Just complement the above DFA i.e. change the final state as
Non-final state and Non-final state as Final State
a, b

A B
Finite Automata

a, b

41
Chapter 2

eg 2: L = Set of all strings over ∑ = {a, b} starting with ‘a’

= {a, aa, ab, ……………………………….}
Sol: DFA:
a, b

a
A B

a, b

L=
2
L=
1
Complement of L 1
= Set of all strings over ∑ ={a,b} not starting with ‘a’
= { ∈ , b, ba, …………………..}
DFA for complement of L1:
a, b

a
A B

a, b

Note:
Finite Automata

42
 Chapter 2
Previous Years’ Question

{ }
Let L be the language represented by the regular expression ∑ *0011 ∑ * where ∑ = 0, 1

What is the minimum number of states in a DFA that recognizes L

(complement of L)? (GATE 2015 SET 3)
1) 4 2) 5
3) 6 4) 8
Sol: 2)

Reversal:
Reversing a language meSol: reverse all strings present in the language.
Steps:
a) Draw the state as it is.
b) Make final state as initial state and initial state as final state.
c) Reverse the edges.
d) Remove all the unreachable state and its transition from initial state.

Note:

DFA for the set of string over ∑ ={a,b} which start with ‘a’.
L1 = {a, aa, ab, aab,……………..}
DFA:
a, b

q0 a
q1

q2

a, b

Now, Let L2 = Reversal of L1 = {a, aa, ba, baa, ………….}

Finite Automata

43
Chapter 2

a, b

q0 a q1

a, b

q2
q0 a q1

a, b
X
Can never reach this state from Non-Deterministic
initial state. Finite Automata (NFA)
Fig 2.3

Previous Years’ Question

Consider the following language: (GATE-2020)

L = {x ∈ {a, b}*| number of a’s in x divisible by 2 but not divisible by 3}
The minimum number of states in DFA that accepts L is ___________.
Sol: Range = 6 to 6

Q1 Counting DFA:
Number of 2-state DFA with designated initial state that can be constructed
over ∑ = a,b .{ }
Sol: q0 q1

y Final State can be : Zero state i.e. None of them final

  : One state i.e. either q0 final state
  or q1 final state
  : Two states i.e. q0 and q1 both final state
So, Total 2 = 4 possibility.
2
Finite Automata

44
 Chapter 2
y q0 on ‘a’ can either go to the state q0 or q1. q0 on ‘b’ can either go to the
state q0 or q1.
y Similarly, q1 on ‘a’ can either go to the state q0 or q1. q1 on ‘b’ can either
go to the state q0 or q1.
Total number of ways to construct 2-state DFA with designated initial
{ }
state over ∑ = a,b = 22 * 24 = 26 = 64

Q2 Number of 3-state DFA with designated initial state that can be constructed
{ }
over ∑ = a,b .

Sol: q0 q1

q2

y Final state can be:

q0 q1 q2 0 final state

q0 q1 q2

q0 q1 q2 1 final
state

q0 q1 q2

q0 q1 q2

2 final
q0 q1 q2
state

q0 q1 q2
Finite Automata

q0 q1 q2 3- final state

45
Chapter 2

Total possibility = 23 = 8 possibility

Total number of ways to construct 3-state DFA with a designated initial

{ }
state over ∑ = a,b = 23 * 36 = 8 * 93 = 5832

Note:

Given: | ∑ |=m
|Q| = number of states = n
y Number of ways, we can construct final states = 2n

Total cells in δ = n × m
=m×n
and each cell can be filled in ‘n ways’
So, Total possibility = nm×n

  

Q × ∑ → 2Q

Total number of ways to construct n-state DFA with a designated initial

state over
∑ = {1, 2, …………m} containing m symbols
Finite Automata

= 2n × nm×n

46
 Chapter 2
Q3 Number of 2-state DFA’s with a designated initial state accepting φ over
{ }
∑ = a, b

Sol: Zero final state

Since neither q0 nor q1 is final state. So, it accepts φ in 16 ways.

Case 2: One final states
1) It accepts ∈ . Thus, this cannot be the required case.

2) It can be the desired case but not all transition on it is

desirable.
a, b a, b

q0 q1

a, b b
a
q0 q1

a, b 4 possibility
a
b
q0 q1

a, b
a, b
q0 q1

Case 3: Two final states

It cannot be the described case as it is accepting ∈ .
∴ Overall total number of 2-state DFAs with designated initial state
accepting φ .
{ }
Over ∑ = a,b = (16 + 4) = 20
Finite Automata

47
Chapter 2

Q4 Number of 2-state DFA with a designated initial state accepting ∑ * (univer-

sal language) over ∑ = a, b . { }

Sol: Case 1: Zero final state

q0 q1 It is not a favourable case as it accepts φ . It cannot
accept ∑ * .

Case 2: One final state

1) q0 q1 It will not accept ∈ which is part of ∑ * . Thus, it

cannot accept ∑ * . Not favourable case.

2) q0 q1 It can be favourable case.

a, b a, b

q0 q1

a, b b

q0 a q1
4 possibility
a, b a

q0 b q1

a, b

q0 a, b q1

Case 3: 2 Final state

q0 q1
.

When both q0 and q1 states are final states, then it will accept ∑ * in 16
possible ways.
Finite Automata

∴ Overall, total number of 2–state DFA with designated initial state

accepting ∑ * over ∑ ={a,b} = 4 + 16 = 20

48
 Chapter 2
Minimization of DFA:

Definitions

Minimization of DFA meSol: trSol:forming a given DFA into an equivalent DFA that has
a minimum number of states.

i) Remove all the unreachable states (i.e. states which are not reachable from initial
state).
ii) Separate all final states in one set and all non-final states in another set.
iii) Two states p and q of a DFA are called Indistinguishable if δ * (p, w) ∈ Final state
⇒ δ * (q, w) ∈Final State
and δ * (p, w) ∉Final State ⇒ δ * (q, w) ∉Final State
for all w ∈ ∑ *
iv) On the other hand, if there exists some string w ∈ ∑ * such that δ * (p, w) ∈Final State
and δ * (q, w) ∉Final State or vice-versa, then the states p and q are said to be
distinguishable by a string ‘w’.
v) Identify distinguishable states and use the logic known as seperating the states.
It meSol: in each step if the two states in a set are distinguishable seperate them.
vi) Stop the algorithm once find no change in partition.

SOLVED EXAMPLES
Q1

Sol:
Finite Automata

49
Chapter 2

State equivalence method:

Follow steps i) and step ii), separate all final states in one set and all non
final states in another set.

{( ) ( )} [0 equivalence class]
π0 = A,B , C

Let group 1 i.e. g1 = (A, B) and

group 2 i.e. g2 = (C)
Then, A on ‘a’ goes to the group g1
And B on ‘a’ goes to the group g1.
d (A, a) = B (belongs to g1)
d (B, a) = B (belongs to g1)
A on ‘b’ goes to the group g2
B on ‘b’ goes to the group g2
d (A, b) = C (belongs to g2)
d (B, b) = C (belongs to g2)
So, A and B will be in same group(set).
π1 =π0 [1 equivalence class]

Q2
Finite Automata

50
 Chapter 2
Sol:

State equivalence method: For State B and C:

{ }
π0 =(A), (B, C,D)        

(A), (B, C), (D) 

π1 =  So, B = C
 g 1 g 2 g 3 

π2 =π1

Q3 Finite Automata

51
Chapter 2

Sol:

By state equivalence method:

 
 
π0 = (q , q
 0 1 2 3, q , q ), (q )
4 
 (g 1 ) (g2 ) 

 
 
π1 =(q0 , q1 , q2 ), (q3 ), (q4 )
 (g 1 ) (g2 ) (g3 ) 

{
π2 =(q0 , q2 ), (q1 ), (q3 ), (q4 ) }
So, q0 = q2
π3 =π2
Finite Automata

52
 Chapter 2
Q4

Sol: Remove states q , q , q , q 4 5 6 7

as these are unreachable states.

State equivalence method:

(q0 , q1 , q2 ), (q3 )

∏0 =  
 g1 g 2 
Finite Automata

53
Chapter 2

(q , q ), (q2 ), (q3 )

∏ 1 = 0 1 
 g 1 g 2 g 3 

{
∏2 =(q0 ), (q1 ), (q2 ), (q3 ) } ⇒ q0 ≠ q1

∏3 =∏2

Minimized Deterministic Finite Automata (DFA) will contain 4 states.

Rack Your Brain

Given a regular language L, will its minimal DFA unique?

Non-Deterministic finite automata (NFA)

y In NFA, there can be 0 or 1 or more than one transition for any input
symbol from any state.
y A NFA is defined as:

N
= (Q, ∑, δ, q0 ,F )
where δ : Transition function

a
eg: A A

a
B
i.e. state A on seeing input a, goes to more than one state which is A and B.
{ }
Let Q = A,B and ∑ = a,b { }
Finite Automata

Q × ∑ → 2Q

54
 Chapter 2
A, a
φ
{A}
A, b
{B}
B, a
{A,B}
B, b

Fig. 2.4

Note:

SOLVED EXAMPLES

Q1
Sol: L = {a, aa, ab, ……………………..}
NFA:
a, b

q0 a q1

Q2
Sol: L = {a, aa, ba, ab, ……………………..}
NFA:
a, b a, b

q0 a q1
Finite Automata

55
Chapter 2

Q3
Sol: L = {a, aa, ba, aba, ……………………..}
NFA:
a, b

q0 a q1

Q4
Sol: L = {ab, aba, abb, ……………………..}
NFA:
a, b

q0 a q1 b q2

Q5

Sol: L={ab, aab, bab , aba ,..........}

NFA:
a, b a, b

q0 a q1 b q2

Q6
Sol: L = {aabb, aabba, aabbb, ……………………..}
NFA:
a, b

q0 a q1 a q2 b q3 b q4
Finite Automata

56
 Chapter 2
Q7

Sol: L = {a, aa, aba, ……………………..}

NFA:
a, b

q0 a a q2
q1

Q8

Sol: L = {a, b, aa, bb, aba, bab, ……………………..}

NFA:
a, b

q0 a q1 a q2

a, b
b b

q3

a, b

Q9

Sol: L = {ab, ba, aab, abb, ……………………..}

NFA:
a, b

a q1 b

q0 q2

b a
q3
Finite Automata

a, b

57
Chapter 2

Q10
l r

Sol: L = {aaaab, baaab, ……………………..}

NFA:
a, b

a, b q1 a, b q2 a, b q3 a, b q4 b q5
q0

Q11
r l

Sol: L = {aaaaa, abbbb, ababb, baabab,…………………..}

NFA:
a, b

a a, b a, b q3 a, b q4 a, b q5
q0 q1 q2

Q12

Sol: L = {aa, baa, aba, …………………..}

NFA:
b b b

a q1 a q2
q0

Q13

Sol: L = {aa, aaa, aab, baa, baaa,…………………..}

NFA:
b b a, b

a a
q0 q1 q2
Finite Automata

58
 Chapter 2
Q14

aaaa, aabb, aaba, abaa, ..................... 

Sol: L= 
baaa,bbbb, .........................................
NFA:
a, b a, b a, b a, b
q0 q1 q2 q3 q4

Q15
Sol: Length of string is atleast 4 meSol: |w| ³ 4.

aaaa, aaaab, ..........................................

L= 
baaa,bbbbb, .........................................
NFA:
a, b

a, b a, b a, b a, b
q0 q1 q2 q3 q4

Q16

Sol: Length of string is atmost 4 meSol: |w| £ 4.

L = { ∈ , a, b, aa, ab, ba, bb,…………………..}
NFA:
a, b a, b a, b a, b
q0 q1 q2 q3 q4

Note:
If the given NFA accept set of all the strings over ∑ = a,b , where { }
Case I: Length of the string is exactly n
Case II: Length of the string is atleast n
Case III: Length of the string is atmost n
Finite Automata

In all these cases, minimum number of states in NFA = (n+1) states

59
Chapter 2

Q17
Sol: L = {a, b, aaaa, abab, …………………..}
NFA:
a, b a, b
q0 q1 q2

a, b

Rack Your Brain

Draw NFA with 3 states that accepts the language L = {a” In 21}{ba
Imzo,k 20}

Previous Years’ Question

Let N be an NFA with n states. Let K be the number of states of minimal DFA which is
equivalent to N. Which of the following is necessarily True?  (GATE 2018)
1) K ≥ 2n 2) K ≥ n
3) K ≤ n2 4) K ≤ 2n
Sol: 4)

Rack Your Brain

a a
q1 q2 q3
a

q0
a
a
q4 q5
Finite Automata

Let L be the language accepted by the above NFA. Construct an NFA

that accepts LU {a”).

60
 Chapter 2
2.2 COMPARISON OF DFA AND NFA

Table 2.1
Conversion from NFA to DFA:
Procedure:
Let N = (Q, ∑ , δ , q0, F) → NFA
M = (Q’, ∑ ’, δ ’, q0’, F’) → DFA
i) There is no change in the initial state i.e. q0' = q0

ii) Start the construction of δ ' with initial state and continue it for every
new state which will come under input column.
Terminate this process when no more new state appears in the input
column.
iii) Every set which contains final state of NFA as subset, will be the final
state for corresponding DFA.
Note:

Q1

Sol: { }
L 1 = a, aa, ab, ............

NFA:
Finite Automata

a, b

q0 a q1

61
Chapter 2

Transition table for NFA:

Corresponding transition Table for DFA obtained from above table:

where D = Dead state (Introduced in DFA)

DFA:
a, b

q0 a q1

a, b

Q2

Sol:
Finite Automata

62
 Chapter 2
DFA diagram:

a a b

b q1 a q0 q1 b q1 q2 b q0q1q2
q0
a

b a b a

q2

Q3

Sol: {
L = aa,ba,bab, aab, ................ }
NFA:
a, b

q0 a, b q1 a q2

Transition table for NFA:

Corresponding transition Table for DFA obtained from above NFA

table: Finite Automata

Here ‘D’ is dead state.

63
Chapter 2

DFA diagram: a, b

a, b a q2
q0 q1

a, b

Q4
Sol: {
L = aaaa, aaab,baab,babb, ................}
NFA:
a, b

q0 a q1 a, b q2 a, b q3

Transition table:

Corresponding transition table for DFA obtained from above table:

Finite Automata

64
 Chapter 2
a
b a

q0 a q0q1 a q0 q1q2 b q0 q2q3 b q0q1q2 q3

b a a b
a

q0q2 q0q1q3 q0q3

b b

Q5

Sol: 
Since constructing NFA is easy, first Construct NFA where each string contain
“101” as a substring
NFA:
0, 1 0, 1

q0 1 q1 0 q2 1 q3

Finite Automata

65
Chapter 2

Conversion from NFA to DFA:

DFA:
0 1 1 0

1 0 1 0 0
A B C D E F

1
0 1

Minimal DFA:

{
∏0 =(A,B, C), (D,E,F) }
∏ 1 ={(A,B), (C), (D,E,F)}

∏2 = {(A), (B), (C), (D,E,F)}

∏3 =∏2
0 1 0, 1

1 0 1
A B C DEF

Now, complement the above DFA to get the minimal DFA that accepts all the
{ }
strings over Σ = 0, 1 where each string “do not contain “101” as a substring.”

0 1 0, 1
Finite Automata

1 0 1
A B C DEF

66
 Chapter 2
2.3 EPSILON NON-DETERMINISTIC FINTE AUTOMATA (Î
Î-NFA)
Specification of epsilon NFA:
y ( )
Epsilon- NFA ∈ − NFA is the NFA which contains ∈ - moves/Null moves.
y This automation allows ∈ as possible transition.
y ∈ -NFA is defined as 5-tuple:
(Q, ∑ , δ , q0, F)
Where transition function:
δ: {}
Q × Σ ∪ ∈ → 2Q

Q: finite set of states

∑: finite set of input symbols
q0: Initial state
F: set of final states
Example: {an | n is even or divisible by 3}

q0

∈ ∈

q1 q3

a a
a

q4 a
q2

q5

∈ -closure

Definitions

The ∈ -closure of the state q, is the set that contains q along with all states which can
be reached by only getting any number of ∈ from state q.
Finite Automata

67
Chapter 2

Rack Your Brain

q0
 

q1 q2

a a 
a
q5
q3 a
q2

q4

Conversion from ∈ -NFA to NFA

y Why need ∈–NFA, when already NFA is present?
NFA: Easier to construct
∈–NFA: Even more easier to construct.

Procedure:
Let N1 = (Q', S', d', q0', F') is the ∈–NFA.
N2 = (Q, S, d, q0, F) is the equivalent NFA.
i) Initial state:
q0 = q0'
ii) d Construction:
∀i∈Σ
∀q∈Q δ(q, i) Î-closure [d' (Î-closure(q), i)]
=

iii) Final state: Find Î-closure of each state, if it contains any of the final
state of N1, then those state(s) will be the final state(s) in equivalent
NFA N2.

SOLVED EXAMPLES

Q1
Finite Automata

68
 Chapter 2
Sol: ∈–closure (q0) = {q0, q1}
∈–closure (q1) = {q1}

∈* 0 ∈*
q0 q0 q0 q0

0 q1
q1 φ

∈* 1
q0 q0 φ

1 ∈*
q1 q1 q1

∈* 0
q1 q1 φ

∈* 1 ∈*
q1 q1 q1 q1

∈ -NFA to NFA
Transition table:

NFA:

0 1

0, 1
q0 q1

Final states in the NFA: Find the ∈ -closure of each state, if it

contains any of the final state, then include this state as part of
final states of equivalent NFA.
That’s why here q0 and q1 both are final states.

Note:
Finite Automata

69
Chapter 2

Q2

Sol: ∈ -closure A) = {A, B, D}

∈ -closure B) = {B, D}
∈ -closure C) = {C}
∈ -closure D) = {D}

A
∈* 0 ∈*
A A A, B, D
0 ∈*
B C C
D 0 D ∈* D
∈* 1
A A φ
B 1 φ
D 1 D
∈*
D

B
∈* 0 ∈*
B C C
0 ∈*
D D D
∈* 1
B B φ
1 ∈*
D D D

∈* 0
C C φ
∈* 1 ∈*
C C B B

∈* 0 ∈*
D D D D
Finite Automata

∈* 1 ∈*
D D D D

70
 Chapter 2
∈ -NFA to NFA:
Transition table:

NFA:
0,1
0 0,1

0 0,1
A B D

0 1

0
C 1

Q3

Sol: ∈ -closure (q0) = {q0, q1, q2}

∈ -closure (q1) = {q1, q2}
∈ -closure (q2) = {q2}

q0 ∈* a ∈*
q0 q0 q0 ,q,q
1 2

q1 a φ
q2 a φ

q0 ∈* b
q0 φ
b ∈*
q1 q1 q1 ,q2
q2 b φ

q0 ∈* c
q0 φ
Finite Automata

q1 c φ
q2 c q2
∈* q2

71
Chapter 2

q1 ∈* a
q1 φ
q2 a φ

q1
∈* b
q2 φ
b ∈*
q1 q1 q1,q2

q1
∈* c
q1 φ
q2 c q2
∈*
q2

∈* a
q2 q2 φ
∈* b
q2 q2 φ
∈* c ∈*
q2 q2 q2 q2

∈ -NFA to NFA
Transition table:

NFA:
a b c

a,b b,c
q0 q1 q2

a,b,c

Rack Your Brain

Is the language preserved in all the steps while eliminating e-transition

from a NFA?
Finite Automata

Note:

72
 Chapter 2
Previous Years’ Question

Let δ denote the transition function and δ̂ denotes the extended transition function
of the ∈ -NFA whose transition table is given below:  (GATE-2017 Set-2)

Then ˆδ (q2 , aba) is

1) f { } 2) q0 , q1 , q3

3) {q0 , q1 , q2 } 4) {q0 , q2 , q3 }

Sol: 3)

Conversion from epislon-NFA to DFA:

Let = (Q ', ∑ ', δ ', q'0 ,F ') is the ∈-NFA.
N'
M = (Q, ∑, δ, q0 ,F) is the equivalent DFA
i) Initial State:

q0 = ( )
∈ −closure q0'

eg:

0 1 2

q0
∈ q1
∈ q2

∈−closure (q0) = {q0, q1, q2}

ii) δ Construction:
Finite Automata

 � Start Constructing δ with initial state and continue for every new
state that appears under the input column.
 � Terminate this process when no new state appears.

73
Chapter 2

iii) Final state:

All states in equivalent DFA which contain final state of ∈ -NFA as a subset, is going to be
the final state of DFA.

SOLVED EXAMPLES

Q1

Sol: ∈ – Closure (q0) = {q0,q1} = Initial state of DFA

Transition Table for DFA:

Every state which contains q1 will be the final state in DFA.

DFA:
a b

q0q1 b
q1

a,b
Finite Automata

74
 Chapter 2
Q2

Sol: ∈–closure (q0) = {q0, q1}

We can construct the transition table for DFA as:

Initial state

q0q1 a q0,q1, q2
q0q1 b q1

q0q1q2 a q0 ,q1, q2
q0q1q2 b q1,q2

q1 a q1,q2
q1 b q1

q1q2 a q1,q2
q1q2 b q1,q2

DFA:
a a, b

q0 q1 a q0 qq b q1q2
1 2

b a
Finite Automata

q1

75
Chapter 2

Here, q0q1q2 and q1q2 are final states in DFA as it contains q2

which is final states for given ∈ -NFA.

Note:

Q3

Sol: ∈–closure (q0) = {q0, q1, q2}

We can construct the transition table for DFA as:

Initial state
q0q1q2 a q0q1q2
q0q1q2 b q1q2
q0q1q2 c q2

q1q2 a Dead State ‘D’

q1q2 b q1,q2
q1q2 c q2
Finite Automata

76
 Chapter 2
q2 a Dead State ‘D’
q2 b Dead State ‘D’
q2 c q2

D a Dead State ‘D’

D b Dead State ‘D’
D c Dead State ‘D’

DFA:
c
a b c

q0q1q2 b q1q2 c
q2

a
a, b

a, b, c

Note:

Finite Automata

77
Chapter 2

Previous Years’ Question

What is the complement of the language accepted by the NFA shown below? Assume
{}
Σ = a and ∈ is the empty string.  (GATE-2012)

a ∈

∈
1) φ 2) {∈}
3) a* 4) {a,∈}
Sol: 2)

Note:

2.4 FINITE TRSol:DUCER

Definitions

Finite state trSol:ducer is a finite state automaton which produces output on reading
any input.

y  finite state trSol:ducer (FST) can be thought of as trSol:lator or relator

A
between strings in a set.
y It is very useful in parsing.

Moore machines

Definitions
Finite Automata

Moore Machines are finite state machines with output value associated with states.

78
 Chapter 2
It can be defined as –

(Q, Σ, δ, q0 , ∆, λ ) where
Q: Finite set of states
Σ: Input alphabets
δ: Transition function

Q×Σ → Q

q0 Initial state
∆: output alphabets
λ : output function which maps Q → ∆
eg:
a b

q0, 1 b q1, 0

Input: ab
a b
q0 q0 q1

1 1 0

Note:

SOLVED EXAMPLES

Q1

Sol: Whenever see ‘ab’ print ‘1’ as output

Finite Automata

=Σ {a,b=
} ∆ {0, 1}

79
Chapter 2

b a

a b
A, 0 B, 0 C, 1

Take example and verify it:

Input1: ab
a b
A B C

0 0 1 (Output)

Input2: abab
a b a b
A B C B C

0 0 1 0 1

Q2

Sol: ∑ ={a,b}
Take D = {0, 1}
a b

A, 0 b B, 0 a C, 0 a D, 1

Take example and verify it

Input: abaa A
a
A
b
B
a
C
a
D

0 0 0 0 1
Finite Automata

80
 Chapter 2
Q3

Sol: ∑ ={0, 1}
∆ = {A, B, C}
0 1

1 1
q0, C q1, C q2,B

0 1
0
0
q3,A

Take example and verify it:

1 1
Input 1: 11 q0 q1 q2

C C B

1 1 0
Input 2: 110 q0 q1 q2 q3

C C B A

Q4
0
Sol: ∑ ={0, 1} Remainder: Binary number %3 1
2
∆ ={0, 1, 2}

Represents states equal to the number of remainders when any binary number
Finite Automata

divisible by 3

81
Chapter 2

0 0 1

1 0
q0, 0 q1, 1 q2,2

Rack Your Brain

Construct a moore machine that takes base 4 numbers as input and

produces ‘reakdus modulo 6 output?

Mealy machine:

Definitions

Mealy machines are finite state machines, where output depends upon the present
input symbol and present state of the machine.

y (
It can be defined as: Q, Σ, δ, q0 , ∆, λ , ) where

Q: Finite set of states

Σ : Input alphabets
δ : Transition function

Q×Σ → Q

q0 : Initial state
∆ : Output alphabet
l: Output function Q × ∑ → ∆
a/1 b/0

b/0
eg: q0 q1

a/1

Input: ab a b q1
q0 q0
Finite Automata

1 0 (output)

82
 Chapter 2
Note:

SOLVED EXAMPLES

Sol: ∑ ={0, 1}
{ }
∆ = 0, 1

To calculate: 2’s complement of binary number 1011

1’s complement of this number = 0100
0 100
2’s complement of this number = +1
0 10 1
Observation:
From LSB whenever you see 0, leave it as it is, whenever you
see 1st 1, leave as it is. After this, whatever digits come, just
complement it, will give 2’s complement
0/0 0/1

1/1 q1
q0

1/0

Rack Your Brain

Construct a mealy machine that takes binary umber as input and

produces 1’s complement of that number as output
Finite Automata

83
Chapter 2

Previous Years’ Question

The finite state machine described by the following state diagram with A as starting state,
where an arc label is x/y and x stands for 1-bit input and y stands for 2-bit output
(GATE-CS-2002)

1) Outputs the sum of the present and the previous bits of the input.
2) Outputs 01 whenever the input sequence contains 11
3) Outputs 00 whenever the input sequence contains 10
4) None of the above
Sol: 1)

Rack Your Brain

Construct a mealy machine that takes binary umber as input and

produces output = (input)2 mod 3.

Conversion of Moore machine to Mealy machine

SOLVED EXAMPLES
Q1
Sol: 
We have to construct a Moore machine which counts the number of a’s is divisible
by 3.
b b b

a a
Finite Automata

q0, 0 q1 , 1 q 2, 2

84
 Chapter 2
When convert moore to mealy, then q0 state on input a goes to
q1 states and output associated with state q1 is 1 so, it will go
onto the transition in equivalent mealy machine. Apply similar
concepts for every state.

Transition: Diagram for mealy machine:

b/0 b/1 b/2

a/1 a/2
q0 q1 q2

a/0

Rack Your Brain

Convert the following given Moore machine to Mealy machine:

y x

x y
q0 , 0 q1, 0 q 2, 1
x

y
Finite Automata

85
Chapter 2

Conversion from mealy to moore machine:

SOLVED EXAMPLES

Q1

Sol: i)  State q1 on getting input 0 goes to state q2 and the output present
in this transition gets associated with states q2 in the corresponding
equivalent moore machine.
ii) State q1 on getting input 1 goes to state q3 and the output present in
this transition i.e. ‘z1’ gets associated with state q3 in the corresponding
equivalent moore machine.
iii) We will follow this above procedure for other states as well as the new
states we are getting.
Finite Automata

86
 Chapter 2
Rack Your Brain

Convert the following given M

Mealy m
machine to equivalent Mooremmachine.
x/1
x/1 y/1

y/0 x/1, y/1 x/0

A B C D

y/1

Finite Automata

87
Chapter 2

Chapter Summary

y Finite Automata: Finite automata is a mathematical model which involves states

and transitions among states in response to inputs.
y Types of Finite Automata: Finite automata without output and Finite automata
with output.
y Classification of Finite Automata without output: DFA, NFA, ∈ –NFA.
y Classification of Finite Automata with output: Moore machine, Mealy machine.
y DFA: A DFA has a finite set of states and a finite set of input symbols. DFA is
defined as quintuple (Q, ∑ , δ , q0, F) where δ : Q × ∑ → Q
y Minimization of DFA: TrSol:forming a given DFA into an equivalent DFA having the
minimum number of states.
y NFA: A NFA is defined as Quintuple (Q, ∑ , δ , q0, F) where δ : Q × ∑ → 2Q
y Comparison of DFA and NFA: Mainly the NFA differs from the DFA in that the NFA
can have any number of transitions (including zero) to the next states from a given
state on a given input symbol.
y Conversion from NFA to DFA: It is possible to convert any NFA to DFA that accepts
the same language. All DFAs are NFA.
y DFA obtained from NFA need not be a minimal DFA.
y ∈-Transition: It is possible to extend the NFA by allowing transitions on an empty
input (i.e. no input symbol at all).
y ∈-NFA: NFA in which transition is also defined for an empty input is known as
∈-NFA.
y Conversion from ∈-NFA to DFA as well as NFA is possible.
y Finite State TrSol:ducer: A finite state automaton which produces output on
reading any input.
y Moore Machines: Finite state machine with output value associated with states. It
is defined as (Q, ∑ , δ , q0, ∆ , λ ) where output function λ : Q → ∆ .
y Mealy Machines: Finite state machines where output is associated with the
transition.
It is defined as (Q, ∑ , δ , q0, ∆ , λ ) where output function λ : Q × ∑ → ∆ .
Finite Automata

88
 3
Regular Expression, Grammar
and Language

Chapter 3
3.1 REGULAR EXPRESSION
y Regular expression represents a regular language.
y For every regular expression, regular language can be generated and for
every regular langauge, a regular expression is possible.
y Similar to arithmetic, where operations + and × are used to build up
expressions such as (5 + 3) × 4;
Regular operations are used to build up expressions which describe
languages are known as a regular expression.
Example: (0+1)0*
� The notation involves a combination of strings of symbols from some
alphabets ∑, parentheses and the operators +, . and *
Example: If L = {∈, aa, aaaa, aaaaaa, ........} then L can be expressed as (aa)*.
Application of regular expression:
a) In Unix grep or equivalent commands for finding strings.
b) In lexical analyser generators such as Lex or flex.

Introduction: Formal definition:

Definition

a)

b)
c)

Regular Expression, Grammar and Language

Note:

Operators of regular expression:

1) Union
� If R1, R2 are any two regular expressions, then their union (R1 + R2) will
also be a regular expression.

89
Chapter 3

2) Concatenation
� If R1, R2 are any two regular expressions, then their concatenation (R1.
R2) will also be a regular expression.
3) Kleene closure
� If R1 is any regular expression, then Kleene closure of R1 (R1*) will also
be a regular expression.
There are three operations on languages that the operators of regular
expressions represent. These operations are:
1) Union
� The union of two languages L1 and L2 denoted as L1 ∪ L2.
� L1 ∪ L2 means a set of strings are either in L1 or L2 or both.
Example: L1 = {10, 111}
L2 = {∈, 01}, then L1 ∪ L2 = {∈, 01, 10, 111}
2) Concatenation
� The concatenation of two languages L1 and L2 is denoted as L1 . L2.
� L1 .L2 is the set of all strings that can be formed by taking any string
from language L1 and concatenating it with any string from language L2.
Example: L1 = {001, 10, 111}
L2 = {∈}
L1 .L2 = L1 L2 = {001, 10, 111}

Note:

3) Closure (Star closure/Kleene closure)

� The closure of any language L is represented by L*.
� Where L* represents the set of all strings that can be formed by taking
Regular Expression, Grammar and Language

any number of strings from L, with repetitions and concatenating all

of them.
L = {0, 1}
L* = all strings of 0’s and 1’s over {0, 1}
L* = U Li
i≥0

L° = { ∈ }
L1 = L
L2 = L.L
Li = L.L.L……… i times

Language associated with regular expressions:

y Regular expressions are used to describe regular languages.

90
 Chapter 3
y The language L(r) denoted by any regular expression ‘r’ is defined as:
i) φ is regular expression denoting { } i.e empty set.
ii) ∈ is a regular expression denoting { ∈ }.
iii) For every a ∈ ∑ , a is a regular expression denoting {a}.
yIf r1 and r2 are two regular expressions, then:
i) L(r1 + r2) = L(r1) ∪ L(r2)
ii) L(r1.r2) = L(r1).L(r2)
iii) L((r1)) = L(r1)
{If r1 is a regular expression, then (r1), a parenthesized r1, is also a
regular expression denoting the same language as r1.}
*
iv) L(r1* ) = (L(r1 ) )
These four rules are used to reduce L(r) to simpler components recursively.
Examples:
i) r = a*
L(r) = L(a*) = { ∈ , a, aa, aaa, ………}
ii) r=a+b
L(r) = {a, b}
iii) r = ab
L(r) = {ab}
iv) r = (a + b)*
L(r) = { ∈ , a, b, aa, ab,………}
v) r = a+ = a.a*
L(r) = {a, aa, ……………}
vi) r = a* + ba
L(r) = { ∈ , a, aa, aaa, ………,ba}

Regular Expression, Grammar and Language

Rack Your Brain

Find all strings in L((a+b)b(a+ab)*) of length less than four?

Order of precedence of regular-expression operators:

i) The star operator (*) is of the highest precedence.
ii) Next is concatenation or “dot” operator, which comes in precedence.
iii) Next is the union (+ operator) comes in precedence..
Order of precedence : * > . > +

Example: (a+b.a)* 1

2
3

91
Chapter 3

Note:

SOLVED EXAMPLES

Sol: 1) LHS: (r*)+ = {∈, r, rr,……….}

RHS: r+ = {r, rr, ……..……….}
LHS ≠ RHS
2) LHS: (r*)* = {∈, r*, r*r*,……….}
= {∈, r*, r*,……….}
= {∈, r, rr,……….}
RHS: r = {∈, r, rr, ……..……….}
*

LHS = RHS
Option 2) is correct.
Regular Expression, Grammar and Language

Sol: 1) LHS: r* + r+ = {∈, r, rr, ……} ∪ {r, rr, ……}

= {∈, r, rr, ……}
RHS: r = {∈, r, rr, ……}
*

LHS = RHS
2) LHS: r*. r* = {∈, r, rr, ……}. {∈, r, rr, ……}
= {∈, r, rr, ……}
RHS: r = {r, rr, rrr, ……}
+

LHS ≠ RHS
Option 2) is incorrect.

92
 Chapter 3
Sol: If r = f, then r* = f* = {∈}
If r = ∈, then r* = ∈* = {∈}
Option 1) True.

Sol: Given:
r1 = (a*b)* and r2 = (a+b*)*
L(r1) = {∈, b, ab, aab,…….}
L(r2) = {∈, a, b, aa, ab, ba, bb, aab,………….}
So, L(r1) ⊂ L(r2)
Option 2)

Rack Your Brain

Identify which of the following are identical?

Regular Expression, Grammar and Language

I) a* II) (aa)* III) (aa*)a IV) (a + ∈)a*
1) I and III only 2) I and IV only 3) I, III and IV only 4) None of these

Sol: Option 1) : a*(ba)* = {∈, a, ba, aba, baba, …………}

It cannot generate string containing ‘baa’ as a substring.
Option 2) : a*b*(ba)* a = {a, aa, ba, baa, …………}
It can generate string containing ‘baa’ as a substring.

93
Chapter 3

Option 3) : (ab*+ a)* (ab)* b*a* = {∈, a, b, aa, bb, ab, ba,
baa, abba,…..}
It can generate string containing ‘baa’ as a
substring.
Option 4) : (bba*+ b)* a = {a, ba, bba, bbaa, ……….}
It can also generate string containing ‘baa’
as a substring.

Previous Years’ Question

Which of the following statements is TRUE about the regular expression 01*0?
 (GATE IT-2005)
1) It represents a finite set of finite strings
2) It represents an infinite set of finite strings
3) It represents a finite set of infinite strings
4) It represents an infinite set of infinite strings
Sol: 2)
Equivalence between regular language and regular expression:
y For every regular language, there is a regular expression and for every
regular expression, there is a regular language.
Regular Language

Representator Generator Acceptor

Regular Expression Regular Grammar Finite Automata

Fig. 3.1
Regular Expression, Grammar and Language

Theorem
“Let r be a regular expression, then there exists some non-deterministic
finite acceptor that accepts L(r). Consequently, L(r) is a regular language.”
Example:
q0 q0

NFA accepts φ

q0 a q0

NFA accepts {a}

Examples of equivalence between Regular language and regular expression:

94
 Chapter 3
SOLVED EXAMPLES

Sol: i) L = {∈, a, b, aa, ab, ba, bb, …………}

= (a + b)*
RE

ii) L = {a, b, aa, ab, ba, bb, …………}

= (a + b)+
RE

Sol: i) L = {a, aa, ab, …………}

= a(a + b)*
RE
ii) L = {b, ab, bb, …………}

= (a + b)* b
RE

iii) L = {ab, aab, bab, …………}

Regular Expression, Grammar and Language

(a + b)* ab (a + b)*
RE =

Sol: i) L = {bab, bbb, aab, abba, baba, …………}

RE =(a + b)(a + b)b(a + b)*
ii) L = {aab, aba, abb, baba, …………}

RE =(a + b)* a(a + b)(a + b)

95
Chapter 3

Sol: i) L = {a, b, aa, aba, bb, bab, …………}

RE= a(a + b)* a + b(a + b)* b + a + b
ii) L = {ab, ba, aab, …………}
RE = a(a + b)* b + b(a + b)* a

Sol: i) L = {aa, ab, ba, bb}

RE = ab + aa + bb + ba = a(a+b)+b(a+b)
RE =(a + b)(a + b)
Similarly, set of all strings having length exactly 3 over ∑ = {a, b}
RE = (a + b) (a + b) (a + b)
ii) L = {aa, ab, ba, bb, aaa, aab,……..}
RE =(a + b)(a + b)(a + b)*
iii) L = {∈, a, b, aa, ab, ba, bb}
RE = ∈+ a + b + ab + aa + ba + bb
Regular Expression, Grammar and Language

RE= (a + b+ ∈)(a + b+ ∈)

A
A
A
A
A
A

96
 Chapter 3
Sol: i) Even length string
L = {∈, aa, ab, ba, bb, ……….}
RE =( (a + b)(a + b) )
∗

ii) Odd length string

L = {a, b, aaa, ……….}
*
RE =( (a + b)(a + b) ) (a + b)

iii) all the strings divisible by 3:

L = {aaa, aab, aba, ……….}
*
RE =( (a + b)(a + b)(a + b) )

iv) all the strings where w @ 2 (mod 3)

*
RE =( (a + b)(a + b)(a + b) ) (a + b)(a + b)

v) all the strings the where the number of a’s are exactly 2.
L={aa,aab,aba,baa.......}
RE = b*ab*ab*
vi) all the strings where the number of a’s are ‘at least 2’.
L = {aa, aab, aba, aaa, ……….}
=RE b*ab*a(a + b)*
vii) all the strings where the number of a’s are ‘atmost 2’.
L = {∈, a, ab, ba, aa, …….}
RE= b* (∈ +a)b* (∈ +a)b*
viii) all the strings where the number of a’s are even.
L = {∈, b, bb, aa, aab, aba …….}

Regular Expression, Grammar and Language

97
Chapter 3

Sol: i) L = {ambn | m + n = even}

Case 1 : m = even, n = even

Two cases

Case 2 : m = odd, n = odd

RE = (aa)*(bb)* + (aa)*a(bb)* b

Case 1 Case 2

ii) L = {ambn | m + n = odd}

Case 1 : m = odd, n = even

Two cases

Case 2 : m = even, n = odd

RE = (aa)*a(bb)* + (aa)*(bb)*b

Case 1 Case 2
Regular Expression, Grammar and Language

Sol: i) L = {aa, ab, …………… }

*
RE =a(a + b) ( (a + b)(a + b) )

ii) L = {a, aaa, aab, ……….}

RE = a ( ( a + b ) ( a + b ) )
*

Note:

98
 Chapter 3
Properties of regular expressions:
Let r, s and t be some regular expression.
i) Commutativity:
In this property, after changing the position of operands result will
remain the same.
r +s = s+r
r.s ≠ s.r

For some case:

r.s = s.r Example: r = a, s = a*

ii) Associativity:
Properties which allow us to regroup the operands when the operand
is applied twice.
r + (s + t) = (r + s) + t
r.(s.t) = (r.s).t

iii) Distributive:
Property which involves two operators and states that one operator
can be pushed down to be applied to each argument of the other
operator individually.
Left distributive : r(s + t) = rs + rt
Right distributive : (s + t)r = sr + tr

Note:

Regular Expression, Grammar and Language

iv) Identity:
When an operation is done between operand in the set and the identity
element it results in the operand itself.

φ + r = r + φ = r (φ is identity for union)

∈ .r = r. ∈ = r ( ∈ is identity for concatenation)

v) Annihilator:

φ.r = r.φ = φ (φ is annihilator for concatenation)

99
Chapter 3

vi) Idempotent:
An operator is idempotent; if we apply it to two same operands, the
output will be that operand itself.
r +r =r (Idempotence law for union)

vii) Closure:
*
� φ = ∈

� φ+ =φ

� ∈+ =∈
� ∈* =∈
� ∈ + rr* =r*

� (r* )* = r*
� r+ = rr* = r*r
� (r+)*= r*
� (r*)+= r*
� (r+)+= r+
� r*r* = r*
� r+r* = r+
� r*r+ = r+
(pq)* q ≠ p(qq)* 
� (pq)* p = p(qp)* but  * * 
(pq) r ≠ p(qr) 

Note:
Regular Expression, Grammar and Language

Previous Years’ Question

Which one of the following regular expressions represents the language; set of all
binary strings having two consecutive 0’s and two consecutive 1’s?(GATE-2016 (set-1))
1) (0+1)* 0011(0+1)*+ (0+1)*1100(0+1)*
2) (0+1)* (00(0+1)* 11+ 11(0+1)*00)(0+1)*
3) (0+1)* 00(0+1)*+ (0+1)*11(0+1)*
4) 00(0+1)* 11+11(0+1)*00
Sol: 2)

100
 Chapter 3
Rack Your Brain

Which of the following are equivalent?

A) (ab)*b B) a(bb)* C) a(ba)* D) (ab)*a
1) A) and C) only 2) A) and D) only
3) C) and D) only 4) B) and C) only

Rack Your Brain

Which of these are equivalent?

I) ∈ + r + rrr* II) ∈ + rr* III) r*
1) I and III only 2) II and III only
3) All are equal 4) None of these

Previous Years’ Question

Which one of the following languages over the alphabet {0,1} is described by the
regular expression :
(O+1)* 0(0+1)*0(0+1)*? (GATE-2009)
1) The set of all strings containing the substring 00
2) The set of all strings containing at most two 0’s
3) The set of all strings containing at least two 0’s

Regular Expression, Grammar and Language

4) The set of all strings that begin and end with either 0 or1
Sol: 3)

3.2 EQUIVALENCE BETWEEN FINITE AUTOMATA AND REGULAR EXPRESSION

y Regular Expressions and Finite Automata are equivalent in their
descriptive power.
y We can convert any Regular Expression into a finite automaton that
recognises the language it describes and vice-versa.
y Definition of Regular language itself says the regular language is one
that is recognised by some finite automaton.
y In other to show that the regular expressions define the same class of
languages (i.e. regular language) accepted by finite automata, we must
show that:

101
Chapter 3

i) For every language, for which we have finite automata, there exists a
regular expression also.
ii) Similarly, for every language, for which we have a regular expression
there exists a finite automata also.

State elimination method:

y State Elimination method can be applied for NFA, DFA, ∈ -NFA to
convert the finite machine into a regular expression.

Rules:
1) There should be only one initial and final state.

∈ ∈

∈ ∈
,then
∈
∈

2) Separate initial state and accepting (final) state using ∈ transition,

Start

∈
then
Regular Expression, Grammar and Language

3) Simplify parallel edge (parallel edge can be combined to a single edge),

r1

A B
r2

r3

Then,
r1 + r2 + r3
A B

4) Elimination of nodes/states.

102
 Chapter 3
Example:

i) q0 r1 q1 r2 q2 ⇒ q0 r1r2 q2

r2

r1 r3 r1r2*r3
ii) q0 q1 q2 ⇒ q0 q2

r1 (r1r2)

q0 q1
iii) ⇒ q0

r2

r2 r1r2*r3
r1

q0 q1 q0
iv) ⇒

r3

r1 r2 r3
r1 + r2r3*r4

v) q0 q1 ⇒ q0

r4
r1 r2
r1
r1r3
q1 q2
r3 q2
vi) q0 q1 ⇒

Regular Expression, Grammar and Language

r2

5) Continue to do the elimination of states till the transition graph takes

any of these from:

Finite Automata Regular Expression

r1

i) ⇒ r1*

103
Chapter 3

r1, r2

ii) ⇒ (r1 + r2)*

r1r2

iii) ⇒ (r1 r2)*

r
iv) ⇒ r
r1

r2
v) ⇒ r1*r2

r2

r1
vi) ⇒ r1r2*

r1 r3

r2
vii) ⇒ r1*r2r3*

Arden’s method:
Let P, Q be the regular expression over ∑.
If P does not contain ∈, then Regular expression R can be written as:
Regular Expression, Grammar and Language

R= Q + RP and it has a unique solution R = QP*

It means that if we get an equation in the form of R = Q + RP, then the

regular expression we get as a solution will be R = QP* .

Note:
If P contains , then regular expression R will have an infinite number of solutions.

Proof of arden’s theorem:

R = Q + RP
= Q + (Q+RP)P
= Q + QP + RPP

104
 Chapter 3
Put R = Q + RP again. On solving, it recursively
R = Q + QP + QP2 + QP3 + ………………………..
R = Q (∈ + P + P2 + ……………………………….)
R = QP*

Note
We can write equation for every other state and start state based on all incoming arrows.

SOLVED EXAMPLES

Sol: A=∈
B = Aa + Ba + Ca
C = Ab
A =∈
C=
∈ .b =
b
B = ∈ .a + Ba + ba (Put values of A and C in B’s equation)

Regular Expression, Grammar and Language

B = ∈ .a + ba + Ba
B
 =a + b
 a +B
a (P does not contain ∈ )
R Q RP
∴ B = QP*
= (a + ba)a*
B

105
Chapter 3

Sol: Write equations based on given Finite Automata:

A = ∈ + Aa
B = Ab + Ba
C = B(a + b) + Cb
⇒ A
=∈  + Aa
 (P does not contain ∈ )
R Q RP
A = ∈ a*
A = a*

*
⇒ B
 = Ab + Ba = a
b+B
a (P does not contain ∈ )
R Q RP

B = (a*b)a*
⇒ C = B(a+b) + Cb
*
=C
 (a b)a* (a + b) + Cb (P does not contain ∈ )
 
R Q RP

=C a*ba* (a + b)b*
Regular Expression, Grammar and Language

Sol: Write equations based on given Finite Automata:

A = ∈ + Ab + Ba
B = Aa + Bb
⇒ =B
 Aa  (P does not contain ∈ )
 + Bb
R Q RP
B = Aab*
⇒ A = ∈ + Ab + Ba

106
 Chapter 3
A = ∈ + Ab + Aab*a
A  + A(b
=∈ + ab*a) (P does not contain ∈ )

R Q RP

∈ (b + ab*a)*
A=

= (b + ab*a)* ab*
B

Sol: Write equations based on given Finite Automata:

A = ∈ + Aa + Ba
B = Ab
C = Ba + C (a + b)
⇒ A = ∈ + Aa + Ba
A = ∈ + Aa + Aba
A  + A(a
=∈ + ba) (P does not contain ∈ )

R Q RP

∈ (a + ba)*
A=

⇒ B = Ab

Regular Expression, Grammar and Language

= (a + ba)* b
B
⇒ C = Ba + C (a+b)
C
 =(a + ba) * ba + C(a + b)
  
R Q RP

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

C=

107
Chapter 3

Rack Your Brain

Rack YourRack
Brain
Your Brain

r r

Conversion of finite automata to regular expression and vice-versa:

Conversion from regular expression to finite automata:

Regular Expression Finite Automata

i) f

ii) a a

iii) b b

iv) ab a b
Regular Expression, Grammar and Language

v) a* ∈

∈ a ∈

vi) ab* b

108
 Chapter 3
Regular Expression Finite Automata

a
vii) (ab)*

viii) (ab + ba)* b

a
a b

Table 3.1

Conversion from Finite Automata to Regular Expression:

SOLVED EXAMPLES

Regular Expression, Grammar and Language

Sol: q0 ab*c
q2 RE = ab*c

109
Chapter 3

a a, b

Sol: q0 aba
q2

=RE a*aba(a + b)*

Sol: 1 0, 1

0 0
A B C

01 1
*

0, 1

01*0
⇒ A C
Regular Expression, Grammar and Language

01 1
*

=
⇒ RE (01* 1)* 01*0(0 + 1)*

110
 Chapter 3
Sol:
b ∈

a c ∈

d
∈

a b, c, d

RE= a(b + c + d)

Regular Expression, Grammar and Language

Sol: c

b d
A B C

ab

111
Chapter 3

c+ab

b d
A B C

b(c+ab)*d
A C

= b(c + ab)* d
RE

Sol: 0
1
0

A B

1
0

10 *1
Regular Expression, Grammar and Language

= (0 + 10* 1)*
RE

112
 Chapter 3
Sol:
0 0 0

1 1
A B C

10 *10*1

⇒ (0+10*10*1)*

(0 + 10 10 1)
*
* *
RE
=

Previous Years’ Question

Consider the regular expression:

R = (a + b)* (aa+bb) (a + b)*
which deterministic Finite Automaton accepts the language represented by the regular
expression R? (GATE (IT) 2007)

Regular Expression, Grammar and Language

1) 2)

3) 4)

Sol:

113
Chapter 3

Previous Years’ Question

Which regular expression best describes the languages accepted by the non-
deterministic automaton below? (GATE (IT) 2006)

1) 2)
1) (a + b)* a(a + b) b 2) (abb)*
3) 4)
3) (a+b)*a(a + b)*b (a+b)* 4) (a+b)*
Sol:Sol:
1)

3.3 REGULAR GRAMMAR

y Regular grammar and Regular languages are equal in power i.e., for
every Regular language there exists a Regular grammar and vice–versa.
y Types of regular grammar:

Regular Grammar

Right linear Left Linear

Regular Grammar Regular Grammar

Fig. 3.2
Regular Expression, Grammar and Language

Right and left linear regular grammar

Right linear regular grammar:
“A Grammar G = (V, T, S, P) is said to be right linear if all productions are in
the form of:
A → xB
A → x
where A, B ∈ V (Variables) and x ∈ T* (T = terminals)”

Left linear regular grammar:

“A Grammar G = (V, T, S, P) is said to be Left Linear Grammar if all productions
are in the form of:
A → Bx
A → x

114
 Chapter 3
where A, B ∈ V (Variables) and x ∈ T* (T = terminals)”

Note
A regular grammar is one that is either right linear or left linear.

Example 1: Grammar G1 = ({S}, {a, b}, S, P1) with P1 given as:

S → abS/a is right linear
Grammar G2 = ({S, S1, S2}, {a, b}, S, P2) with P2 given as:
S → S1ab
S1 → S1ab|S2
S2 → a
is left linear.
Both G1 and G2 are regular grammar.
Example 2: The Grammar G = ({S, A, B}, {a, b}, S, P) with productions:
S → A
A → aB/ ∈
B → Ab
Is not regular grammar.

Reason:
Even though here every production is in right or left linear form, but the
grammar itself is neither right linear nor left linear. So, it is not Regular
grammar.

Note
The above example is linear grammar.

Regular Expression, Grammar and Language

Linear grammar:
“A linear grammar is a grammar in which at most one variable can occur on
the right side of any production, without restriction on the position of this
variable.”

Grey Matter Alert!

A regular grammar is always linear, but not all linear grammars are regular

Note:
The language generated by the right linear grammar is always regular.
115
Chapter 3

Equivalence of regular grammar and regular language:

Theorem:
“A language L is regular if and only if there exists a regular grammar G such that
L = L(G)”
Regular expressions

DFA or NFA

Regularexpressions
Regular Grammar

Fig. Fig.
3.1 3.3 Conversion of
: Conversion of Regular
Regular expressions,
expressions,
Regular Grammar and Finite automata
Regular Grammar and Finite automata

Previous Years’ Question

Language L1 is defined by the grammar: (GATE 2016 (SET-2))

Language L2 is defined by the grammar:

Consider the following statements:

“TRUE”?
1) 2)
Regular Expression, Grammar and Language

2) 4)
Sol:

Rack Your Brain

Rack Your Brain

116
 Chapter 3
Rack
RackYour
YourBrain
Brain

SOLVED EXAMPLES

Sol: i) L = a*
S → Sa| ∈
(OR)
S → aS | ∈
ii) L = a+
S → Sa|a
(OR)
S → aS | a

Sol: ∑ = {a, b}
Regular expression = (a + b)* , L = { ∈ , a, b, aa, ab, ………}

Regular Expression, Grammar and Language

S → aS |bS| ∈

Sol: ∑ = {a, b}
Regular expression = (a + b)+ , L = {a, b, aa, ab, ………}
S → aS|bS|a|b

117
Chapter 3

Sol: Regular expression = a (a + b)*

L = {a, aa, ab, …………….}

Grammar:
S → aA
A → aA|bA| ∈
Conversion from finite automata to regular grammar:
a, b

a
A B

Regular Grammar Corresponding to the given Finite Automata:

A → aB (There will be one production for every outgoing edge.
B → aB | bB |∈ For the final state, we will add null production in the
grammar.)
It produces the Right Linear Grammar.
If we reverse the Right-Hand Side of the production of Right Linear Grammar,
we will get Left Linear Grammar.
A → Ba
B → Ba | Bb |∈ (Left Linear Grammar)
Right linear grammar to ∈ -NFA:
1) If S → α is a production, then [S] is a start/initial state and all the suffix
of RHS of the production will be the other states of ∈–NFA.
2) If S → α is a production, then δ (S, ∈) = [α]

∈
[α ]
Regular Expression, Grammar and Language

[S]

3) If S → α is a production, then δ (aα, a) = [α]

a
[aα] [α]

4) If S → α is a production, then for every terminal, a ∈ T

δ (a, a) = ∈ which is final state.

a
[a] [∈]

118
 Chapter 3
SOLVED EXAMPLES

Sol: Q(States) = {[S], [bbaS], [baS], [aS], [a], [E]}

Initial State = q0 = [S]
Final state = F = [E]
a

[S]
∈ [bbaS]
b
[baS]
b
[aS]

a
[a] [E]

δ ( S, ∈) =[bbaS]
δ ( S, ∈) =[a]
δ (bbaS,b ) =
[baS]
δ (baS,b ) =
[aS]
δ ( aS, a ) =
[S]
δ ( a, a ) =
[E]

Regular Expression, Grammar and Language

Sol: Q(States) = {[S], [01S], [E], [1], [1S]}
Initial State = [S]
Final state = [E] (End State)
1

[S]
∈ [01S]
0
[1S]

1
[1] [E]

119
Chapter 3

δ ( S, ∈) =[01S]
δ ( S, ∈) =[1]
δ ( 01S, 0 ) =
[1S]
δ ( 1S, 1) =
[S]
δ ( 1, 1) =
[E]

Left linear grammar to ∈ -NFA:

Step 1: Reverse the Right-hand side of every production.
Step 2: obtain ∈ –NFA.
Step 3: Interchange initial and final state.
Step 4: Change the direction of the edges.

SOLVED EXAMPLES

Sol: Step-1: Reverse the right-hand side of every production and get the right
linear Grammar.
S → 011S|0
Step-2: Obtain ∈–NFA
Q(States) = {[S], [011S], [11S], [1S], [0], [E]}

∈ 0 1
Regular Expression, Grammar and Language

[S] [011S] [11S] [1S]

0
[0] [E]

Step-3: 
Make the initial state as final state and the final state as initial
state.
Step-4: Change the direction of the edges.

120
 Chapter 3
1

[S]
∈ [011S]
0
[11S]
1
[1S]

[0] 0 [E]

Sol: Step-1 : Reverse the right-hand side of every production and get Right Linear
Grammar.
S → 001S|1
Step-2 : Convert to ∈ –NFA
Q(States) = {[S], [001S], [01S], [1S], [1], [E]}
1

∈ 001S
0
01S
0
1S
S

1 E
1

Regular Expression, Grammar and Language

δ (S, ∈ ) = [001S]
δ (S, ∈ ) = [1]
δ (001S, 0) = [01S]
δ (01S, 0) = [1S]
δ (1S, 1) = [S]
δ (1, 1) = [E]
Step-3 : Interchange initial and final states.
Step-4: Change the direction of edges:

121
Chapter 3

q2
∈ 001S
0
01S 0 1S
S

q3 q4 q5
∈

1
1 E

q1 q0

1 ∈ ∈ 0 0
q0 q1 q2 q3 q4 q5

3.4 REGULAR LANGUAGES

The language which is accepted by Finite Automata (or) the language which
is generated by regular expression (or) the language which is generated by
Regular grammar is called Regular Language.

Definition

A language L is called regular if and only if there exists some deterministic finite
acceptor M such that L = L(M).

Note:
Regular Expression, Grammar and Language

122
Note:

Chapter 3
Closure properties of regular language
Closure properties of regular languages are defined as the certain operation
on regular language, which when applied to the language, results into the
language of the same type.
i) Closure under union:
Theorem:
“If L1 and L2 are regular languages, then L1 ∪ L2 will also be a regular

Regular Expression, Grammar and Language

language only.”
Proof:
Since L1 and L2 are regular, they have regular expressions, say L1 =
L(R) and L2 = L(S), then L1 ∪ L2 = L (R + S) by the definition of the +
operator for regular expressions.
ii) Closure under complementation:
Theorem:
“If L is a regular language over alphabet ∑, then L =∑* − L is also a
regular language.”
Proof:
Let L = L(A) for some DFA A = (Q, ∑, δ, q0, F), then L = L(B) , where B is
the DFA (Q , ∑, δ, q0, Q – F) i.e., B is exactly like A, but the accepting
states of A become non-accepting states of B and vice-versa.

123
Chapter 3

iii) Closure under intersection:

Theorem:
“If L1 and L2 are regular languages, then so is L1 ∩ L2.”
Proof:
By Demorgan’s law:
L1 ∩ L2 = (L1 ∪ L2 )
If L1 and L2 are regular, then by closure under complementation, so
are L1 and L2 .
Using closure under union, L1 ∪ L2 is regular.
Using closure under complementation once more
(L1 ∪ L2 ) =L1 ∩ L2 is regular.

iv) Closure under difference:

Theorem:
“If L1 and L2 are regular languages, then so is L1 – L2.”
Proof:
L1 − L2 = L1 ∩ L2
As we know, L2 is regular, and using the closure of intersection L1 ∩ L2
is also closed. Thus L1 – L2 is also regular.

v) Closure under reversal:

Theorem:
“If L is a regular language, so is LR.”
Proof:
Let L is Regular Language. We can construct a Non-Deterministic
Finite Automata with a single final state for it.
In the transition graph for this Non-Deterministic Finite Automata,
a) Make the initial state as the final state.
Regular Expression, Grammar and Language

b) Make the final state as the initial state.

c) Reverse the direction of all the edges.
Now the modified Non-Deterministic Finite Automata accepts wR if
and only if the original Non-Deterministic Finite Automata accepts w.
vi) Closure under homomorphism:
Homomorphism:

Definition

A string homomorphism is a function on strings that works by substituting a particular

string for each symbol.

124
 Chapter 3
Example: The function h given by h(0) = abb and h(1) = ba is a
homomorphism which replaces each 0 by abb and each 1 by ba. Thus,
h(1011) = baabbbaba.
Theorem:
“If L is a regular language over alphabet ∑, and h is a homomorphism
on ∑, then h(L) is also regular.”

vii) Closure under Inverse homomorphism:

Inverse homomorphism:
We can apply homomorphism backwards also.
Regular languages are closed under this.
The inverse of homomorphic image of a language L is h–1 (L) = set of
strings w in ∑* such that h(w) is in L; if h is a homomorphism from
some alphabet ∑ to strings in another alphabet T, and L be a language
over alphabet T.

L h h(L)

h–1 (L) h L

Fig. 3.2 : A homomorphism applied

Fig. 3.4 A Homomorphism Applied in
thethe
in forwardand
Forward andInverse
inverse direction
Direction

Regular Expression, Grammar and Language

Example 1. Let ∑ = {0, 1, 2} and ∆ = {a, b}.
Defined h by h(0) = a, h(1) = ab, h(2) = ba.
Let L1 = {ababa}
h–1 (L1) = {110, 022, 102}
Example 2. Let ∑ = {0, 1} and ∆ = {a, b}.
Defined h by h(0) = aa, h(1) = aba.
Let L = (ab + ba)*a
= {a, aba, baa, ababa, …………….}
y Inverse homophoric image for a, is not possible.
y Inverse homophoric image for aba is possible.
h–1 (aba) = {1}

125
Chapter 3

Rack Your Brain

Consider the homomorphism h from the alphabet {0, 1, 2} to {a, b}

defined by : h(0) = ab, h(1)=b, h(2)=aa
a) What is h(2201)?
b) If L is the language 1*02, what is h(L)?

viii) Closure under quotient operation:

Regular languages are closed under Quotient operation.
Right quotient:
Let L1 and L2 be language on the same alphabet, then the right
quotient of L1 with L2 is defined as:
L1/L2 = {x : xy ∈ L1 for some y ∈ L2}
Example 1. L1 = {01, 001, 101, 0001, 1101}
L2 = {01}
L1/L2 = {∈, 0, 1, 00, 11}
Example 2. L1 = 10*1 ; L2 = 0*1
L1 = {11, 101, 1001, 10001, ……………..}
L2 = {1, 01, 001, 0001, ……………..}
L1/L2 = {1, 10, 100, 1000, ………………}
= 10*
Note:
Regular Expression, Grammar and Language

ix) Closure under INIT operation:

Regular sets are closed under INIT (all the prefixes of given language
L) operation.
Example: L = {a, ab, aabb}
INIT(L) = {∈, a, ∈, a, ab, ∈, a, aa, aab, aabb}
= {∈, a, aa, ab, aab, aabb}

x) Closure under substitution:

Substitution: Let ∑, ∆ two alphabets, then substitution is a mapping
defined over the alphabet ‘∑’ such that symbols of ∑ can be replaced

126
 Chapter 3
by regular language of another alphabet ‘∆’
Regular sets are closed under substitution.
Example: ∑ = {a, b}
f(a) = 0*
f(b) = 01*
L = a + b*
f(L) = 0* + (01*)*
which is again a regular expression, which will accepted by some
finite Automata.
Note:

Example: L1 = {ab}
L2 = {a2b2}
L3 = {a3b3} ………………..so on
L = L1 ∪L2∪L3 ∪ ……………………………….
= {anbn | n ≥ 1} which is not regular.
Note:

xi) Closure under symmetric difference:

L1 Å L2 = L1 D L2

Regular Expression, Grammar and Language

= (L1 ∪ L2) - (L1 ∩ L2)
= (L1 - L2) ∪ (L2 - L1)
As we know, Regular language is closed under union, intersection and
set-difference.
Therefore, It is also closed under symmetric difference.

Rack Your Brain

Rack Your Brain

127
Chapter 3

Regular language (L) is closed under:

Operations Yes/No

1) Union Yes

2) Substitution Yes

3) Complementation Yes

4) Set-difference Yes

5) Concatenation Yes

6) Reversal Yes

7) Kleene Closure Yes

8) Positive Closure Yes

9) Subset (L) No

10) Prefix (L) Yes

11) Suffix (L) Yes

12) Substring (L) Yes

13) Substitution Yes

14) Homomorphism Yes

15) Symmetric difference Yes

Regular Expression, Grammar and Language

Table 3.2 Closure Properties of Regular languages

Decision properties of regular language:

A decision property for a class of languages is an algorithm which takes a
formal description of a language and says whether some property holds or
not.
Example: Is language L empty?
Example: Is a particular string w in the described language?
Example: Do two descriptions of a language actually describe the same
language?

128
 Chapter 3
i) Testing emptiness of regular languages:
Emptiness problem of Regular Language is decidable.
EDFA = {<D>| D is a DFA and L(D) = φ}
Algorithm:
Step 1: Select the states which are not reachable from the
initial state and delete those states and corresponding
transitions.
Step 2: In the remaining finite Automata, if we find at least one
final state, then the language accepted by the given finite
Automata is non-empty otherwise, empty.

ii) Testing finiteness of regular language:

The finiteness problem of Regular language is decidable.
Algorithm:
Step 1: Remove the state which is not reachable from initial state
and corresponding transitions.
Step 2: Delete the states and corresponding transitions from
which we cannot reach the final state.
Step 3: In the remaining Finite Automata, if we find at least one
loop and one final state, which means it accepts infinite
language.
Note:

iii) Testing equality problem of regular languages:

The equality problem of Regular language is decidable.

Regular Expression, Grammar and Language

EQDFA = {<D1, D2 >| D1 and D2 are DFA and L(D1) = L(D2)}

Is L1 = L2 ?

FA 1 FA2

For regular language L1, we can make a Finite Automata FA1 and
similarly for regular language L2. We can make finite Automata FA2.
So, corresponding DFA will exist for both languages, which can be
further minimised.
Thus, whether two regular languages are equal or not is decidable.

129
Chapter 3

Note:

Pumping lemma:
y It is evident from the many examples that Regular languages can be
infinite.
y However, the regular language associated with automata having finite
memory imposes restrictions on the structure of Regular language.
y Pumping lemma is a theorem about regular languages which is used to
prove that some of the languages are not regular.

Theorem:
“If L is an infinite regular language. Then there exists some positive integer
n such that any w ∈ L , | w | ≥ n can be decomposed as:
w = xyz such that
i) | y |≥ 1
ii) |xy| ≤ n
iii) for all i ≥ 0 , the string xyiz is also in L.”
Regular Expression, Grammar and Language

Note:

Example: L = {anbn| n ≥ 1}
Sol: Let’s assume L is a regular language (proof by contradiction)
w∈L
w ∈ akbk
Choose a ‘k’ such that |akbk|. Here 2k ≥ n
w = akbk

130
 Chapter 3
z
x y bk
a
k–1
a
|xy| = |ak–1a| = |ak| (Here k ≤ 2k)
| y |≠ 0
Hence, xyiz ∈ L ; ∀ i ≥ 0
For i = 2, ak–1 a2bk = ak+1 bk ∉ L
∴ L is Non-Regular.

Note:

Which of the following languages are regular?

1) L = {a, ab, aba} → Finite set

Regular Expression, Grammar and Language

It is Regular Language.
2) L = {w ∈ {a, b}* ,|w| = 20} → Regular Language
3) L = {w ∈ {a, b}* ,|w| = r (mod n)} → Regular Language
4) L = {w ∈ {a, b}* ,|w| ≥ 20} → Regular Language
5) L = {ambn | m, n ≥ 0} → Regular Language
6) L = {ambn |m ≥ 2020, n ≥ 2021} → Regular Language
7) L = {ambn| 1 ≤m ≤ 200, 20 ≤ n≤ 400} → Regular Language
8) L = {ambn| m + n = 20} → Finite → Regular Language
9) L = {ambn| mn = Finite} → Regular Language
10) L = {ambn| 1 ≤ m ≤ n ≤ 40} → Regular Language
11) L = {anbn| n ≥ 1} → Non-Regular Language

131
Chapter 3

12) L = {ambn| m = n, m, n ≥ 0} → Non-Regular Language

13) L = {ambn| m < n} → Non-Regular Language
14) L = {ambn| m ≠ n, m, n ≥ 0} → Non-Regular Language
15) L = {ambn| m = n2} → Non-Regular Language
16) L = {ambn|gcd (m, n) = 1} → Non-Regular Language
17) L = {wcwR| w ∈ (a, b)*} → Non-Regular Language
18) L = {wxwR| w, x ∈ (0, 1)+} → Regular Language
19) L = {anbncn| n ≥ 1} → Non-Regular Language
20) L = {wxwR| w, x ∈ (0, 1)+, |x| = 5} → Non-Regular Language

Rack Your Brain

Rack Your Brain

Previous Years’ Question

1) 2)
3) 4)
Sol:
1) 2)
3) 4)
Sol:
Regular Expression, Grammar and Language

Rack Your Brain

Rack Your Brain

Myhill-nerode theorem
y Myhill-Nerode Theorem provides a necessary and sufficient condition
for a language to be a regular.
y The Myhill-Nerode Theorem states that L is regular if and only if RL has
a finite number of equivalence classes and moreover that the number

132
 Chapter 3
of states in the minimal DFA recognizing L is equal to the number of
equivalences classes in RL.
y The language L defines over the alphabet ‘ ∑ ’ is Regular iff the number
of equivalence classes with respect to ‘L’ is finite.
y In minimal finite automata, some language can be defined at each and
every state. These languages are mutual disjoint and they are known as
equivalence classes.
y Union of all these equivalence classes = ∑*
y Union of some of the equivalence classes = Language ‘L’ accepted by
finite automata.
Example 1:
a, b

a
A B

a, b

A = {∈} 

*
B a(a + b)  Equivalence Classes
=

C b(a + b)* 
=

Union of all these equivalence classes = A ∪ B ∪ C = ∑*

Union of some of the equivalence classes = A ∪ B
= language accepted by finite automata

Regular Expression, Grammar and Language

y The language ‘L’ is Regular if and only if ‘L’ is accepted by finite
automata.
⇔ The number of states is finite.
⇔ The number of equivalence classes with respect to ‘L’ is finite.
y The language ‘L’ is not regular ⇔ The number of equivalence classes
with respect to ‘L’ is infinite.
Example 2: Let L = ab*
The minimal DFA for the L = ab* is:

133
Chapter 3

a
A B

b a

a, b

The equivalence classes are:

A = {∈}

B = ab* (State B refers to the strings in the language)

C = b(a +b)* + ab*a(a+b)*
y L is regular (There are 3 equivalence class that and has a minimal DFA
with 3 states).
y L itself is contained entirely in one equivalence class that corresponds
to the fact that the minimal DFA has only one accepting state.
Regular Expression, Grammar and Language

134
 Chapter 3
Chapter Summary

y Regular expression: Regular expression is one way to describe the regular languages
via the notation.
y Operators of regular expression: Union, Concatenation, Closure (Kleene Closure/
Star Closure).
y Order of precedence of regular expression operators:

* > • > +

y Equivalence between regular language and regular expression: For every regular
language, there exists a regular expression and for every regular expression, there
is a regular language.
y Properties of regular expression: Commutativity, Associativity, Distributive, Identity,
Idempotent, Closure.
y Equivalence between regular expression and finite automata: Every language
defined by a regular expression and a regular expression is defined by Finite
Automata.
y Conversion of finite automata to regular expression: i) State Elimination Method
and ii) Arden’s Method.
y Regular grammar: Another way of describing the regular languages. It is also known
as Type 3 grammar in Chomsky Hierarchy.
y The Grammar ‘G’ is said to be type 3 or Regular if every production is in the form:
A → xB | x or A → Bx|x, where A, B ∈ V, x ∈ T*
y Types of regular grammar: Right linear Grammar and left linear Grammar.
y Regular Language: The language which is accepted by finite Automata, generated
by Regular expression and generated by Regular Grammar is known as Regular

Regular Expression, Grammar and Language

language.
y Myhill-nerode theorem: “Myhill-Nerode Theorem provides a necessary and
sufficient condition for a language to be a regular.

135
 4 Context-Free Language and
Pushdown Automata

Chapter 4
4.1 CONTEXT-FREE GRAMMAR
y Context-free grammars are a more powerful method of describing
languages.
y The productions in a regular grammar are restricted in two ways:
The left side must be a single variable, while the right-hand side of the
production has a constraint as we know for RLG: A → xB|x and for LLG:
A → Bx|x where A, B∈V and x∈T*.
y To create grammars which are more powerful, we must relax some of
these restrictions.
y By retaining the restriction on the left side but permitting anything on
the right, we get context-free grammar.

Definition:
y A grammar G = (V,T,S,P) is said to be context-free if all productions in P
have the from:
A→x
Where, A ∈ V and x ∈ (VUT)*

Where,
T = Terminals.
V = Non-Terminals or variables.
S = Start symbol.
P= Finite set of rules or productions that represent the recursive
definition of a language.
y Each production consists of:
a) A variable that is being (partially) defined by the production. This

Context-Free Language and Pushdown Automata

variable is often called the head of the production.
b) The production symbol →.
c) A string of zero or more terminals and variables. This string is called
the body of the production.
Note:

A language is said to be context free if and only if there is a context free

grammar G such that L = L(G).
Example: The Grammar G = ({S}, {a,b}, S,P) with productions:
S → aSa,
S → bSb,
S→∈
is context-free.

137
Chapter 4

A typical derivation in this grammar is:

S ⇒ aSa
⇒ aaSaa
⇒ aabSbaa
⇒ aabbaa
i.e., L(G) = {wwR | w∈{a,b}*} which is context-free language.

Derivation of string: left most derivation and right most derivation

y In a grammar that is not linear, a derivation may involve sentential forms
with more than one variable.
y In such cases, the variables can be replaced in order of choice
Example: The grammar G = ({A,B,S} , {a,b}, S, P) with productions.
S → AB
A → aaA
A→∈
B → Bb
B→∈
The above grammar generates the language L(G) = {a2nbm |n ≥ 0, m ≥ 0}.

Left most derivation for the string “aab”

Step 1 : S ⇒ AB
Step 2 : S ⇒ aaAB
Step 3 : S ⇒ aaB
Step 4 : S ⇒ aaBb
Step 5 : S ⇒ aab
Context-Free Language and Pushdown Automata

Right most derivation for the string “aab”

Step 1 : S ⇒ AB
Step 2 : S ⇒ ABb
Step 3 : S ⇒ Ab
Step 4 : S ⇒ aaAb
Step 5 : S ⇒ aab

Definition

A derivation is said to leftmost if in each step, the leftmost variable in the sentential form is
replaced. If in each step, the rightmost variable is replaced, derivation is known as rightmost.

138
 Chapter 4
Previous Years’ Question

Identify the language generated by the following grammar, where S is start variable.
 (GATE-2017 (Set-2))
S→XY
X→zX|a
Y→aYb|∈
1) {ambn|m ≥ n, m > 0} 2) {ambn|m ≥ n, n ≥ 0}
3) {ambn|m > n, m ≥ 0} 4) {ambn|m ≥ n, n > 0}
Sol: Option 3)

Previous Years’ Question

Which of the following languages is generated by the given grammar?

 (GATE-2016 (Set-1))
S→aS|bS|∈
1) {anbm}|n, m ≥ 0}
2) {w∈{a, b}* |w has equal number of a’s and b’s}
3) {an |n ≥ 0} ∪ {bn |n ≥ 0} ∪ {anbn |n ≥ 0}

Context-Free Language and Pushdown Automata

4) {a, b}*
Sol: Option 4)

Derivation trees:
A second way of showing derivations, independent of the order in which productions are
used; is by a derivation tree or parse tree.

Definition

A derivation tree is an ordered tree in which nodes are labelled with the left sides of
production and in which the chileren of a node represent its corresponding right sids

139
Chapter 4

Example: A → abABc

a b A B c

Grey Matter Alert!

Let G = (V, T, S, P) be a context free grammar. An ordered tree is a derivation tree for G
if and only if it has the following propertie:
a) The root is labeled S.
b) Every leaf has a label from T∪{∈}.
c) Every interior vertex (a vertex that is not a leaf) has a label from V.
d) If a vertex has label A ∈ V, and its children are labelled (from left to right) a1, a2, ..........
an, then P mustcontain a production of the form.
A → a1, a2, ........... an
e) A leaf labeled ∈ has no siblings, that is a vertex with a child labeled ∈ can have no
other children.

Example: consider the grammar G, with productions-

S → aAB,
A → bBb,
B → A|∈
Context-Free Language and Pushdown Automata

Parse tree for “abbbb”:

S

a A B

b B b A

∈ b B b

140
 Chapter 4
Rack Your Brain

Which language is generated by grammer S → aSb|SS|∈

Previous Years’ Question

A CFG G is given with the following productiions where S is the start symbol, A is non-
terminal and a and b are terminals. (GATE-IT-2008)
S→aS|A
A→aAb|bAa|∈
Which of the following strings is generated by the grammar above?
1) aabbaba 2) aabaaba
3) abababb 4) aabbaab
Sol: Option 4)

Ambiguity in grammar:
When a grammar fails to provide a unique structure, it is sometimes possible
to redesign the grammar to make the structure unique for each string in
the language; but sometimes we cannot. That is known as ambiguity in

Context-Free Language and Pushdown Automata

grammar.

Ambiguous grammar:

Definition

A context free grammar G is said to be ambiguous if there exists some

w∈L(G) that has atleast two distinct derivation trees (Parse trees).

Note:
Ambiguity implies the existence of two or more leftmost or rightmost
derivations.
Example: E → E+E | E * E
Consider the sentential form E + E * E.
It has two derivations from E:

141
Chapter 4

1st 2nd

E⇒E+E E⇒E*E
⇒E+E*E ⇒E+E*E
E E

E E E E
+ *
E E E E
* +
(a) a) b) (b)
Fig. 4.1 Two Parse Trees with the Same Yield.

y Derivation 1st says that the second and third expressions are multiplied
and the result is added to the first expression.
y Derivation 2nd adds the first two expressions and multiplies the result
by the third.
Example: 1+2*3
1st derivation gives output = 1+(2*3)=7
2nd derivation gives output = (1+2)*3 = 9
y Hence, we can say that there is an ambiguity.

Rack Your Brain

Context-Free Language and Pushdown Automata

Causes of ambiguity in the grammar:

There are two causes of ambiguity in the grammar:
1) The precedence of operators is not respected.
Example: As explained in figure 4.1, both are valid parse trees, and ambiguity
comes only because precedence is not followed. We need to force only the
structure of figure 4.1 (a) to be legal in unambiguous grammar.
2) A sequence of identical operators can group either from the left or from
the right.
Example: Two different parse tree exists for the string E+E+E. Since
addition is associative, doesn’t matter whether we group from left or right,
but to eliminate ambiguity, we must pick one.

142
 Chapter 4
Example of an unambiguous grammar:
Example 1: Example 2: Example 3:
E→E+T S → aAB X → AB
T→T*F A → bBb A → Aa|a
F → id B → A|∈W B→b

Rack Your Brain

Grey Matter Alert!

Context free languages, generated only by ambiguous grammars, is known as

inherently ambiguous.

Previous Years’ Question

A CFG G is given with the following productions where S is the start symbol, A is non-
terminal and a and b are terminals. (GATE-IT-2008)
S→aS|A
A → aAb|bAa|∈
For the string, “aabbaab” how many steps are required to derive the string and how

Context-Free Language and Pushdown Automata

many parse trees are there?
1) 6 and 1 2) 6 and 2
3) 7 and 2 4) 4 and2
Sol: Option 1)

Previous Years’ Question

A context free grammar is ambiguous if: GATE (CS)-1987)

a) The grammar contains useless non-terminals
b) It produces more than one parse tree for some sentence.
c) S
 ome production has two non-terminals side by side on the right-hand side.
d) None of the above
Sol: Option b)

143
Chapter 4

Conversion of CFG into simplified CFG:

To get the Chomsky Normal Form, we need to make a number of preliminary simplifications,
i.e. we need to convert CFG into simplified CFG.
i) We must eliminate ∈-productions, those of the form A → ∈ for some variable A.
ii) We must eliminate unit productions, those of them from A→B for variables A and B.
iii) We must eliminate useless symbols, those variables, or terminals that do not appear
in any derivation of a terminal string from the start symbol.
∈ productions:

Definition

Any production of a context free grammar of the form A → ∈ is called as

∈-production

Note:
A variable is nullable if it can derive E directly or indirectly.

Eliminating ∈ productions:
y A grammar may generate a language not containing ∈ , but can have some
∈ -production or nullable variables. In such a case, the ∈ -productions can be removed.
Example: S → ABC
A → BC|a
B → bAC|∈
C → cAB|∈
contains ∈–productions.
Context-Free Language and Pushdown Automata

Step 1: Find all the nullable variables or null variables. Remove all the null production
from the grammar.
Step 2: Replace the right-hand side of the production with and without ∈ ; wherever
nullable variables or null variables are present on the RHS of production.
Step 3: After this, whatever grammar we get, that grammar is without ∈ - production.
Note:
If start symbol (S → ∈) contain ∈ - production i.e.
if the language contain ∈, then we cannot eliminate ∈ - productions, totally.

144
 Chapter 4
Sol: Step 1: Nullable or null Variable = {B, C, A}
B contains ∈ production, so it is a nullable variable, similarly C is also a nullable
variable.
A contains production A → BC, where B and C both are null variables. Thus A is
also deriving epsilon. Hence A is also a nullable variable.

Remove B ® ∈ , C ® ∈ productions from the given grammar.

Step 2: S ® AbaC
S ® Aba [Substitute C ® ∈ ]
S ® baC [Substitute A ® ∈ ]
S ® ba [Substitute A ® ∈ , C ® ∈ ]

A ® BC
A ® B [Substitute C ® ∈ ]
A ® C [Substitute B ® ∈ ]
B ®b
C ®D
D ®d

Context-Free Language and Pushdown Automata

Step 3: The final Grammar is:
S ® AbaC | Aba | baC | ba
A ® BC | B | C
B ®b
C ®D
D ®d

145
Chapter 4

Sol:   Step 1: Nullable and null variables = {A,B,C}

B contains ∈ production, so it is a nullable variable, similarly C is
also nullable variable.
A contains production A → BC, where B and C both are null variables.
Thus A is also deriving epsilon. Hence A is also a nullable variable.
Step 2: S ® ABC
S ® AB [Substitute C ® ∈ ]
S ® BC [Substitute A ® ∈ ]
S ® AC [Substitute B ® ∈ ]
S ® A [Substitute B ® ∈ , C ® ∈ ]
S ® B [Substitute A ® ∈ , C ® ∈ ]
S ® C [Substitute A ® ∈ , B ® ∈ ]
A ® BC
A ® B [Substitute C ® ∈ ]
A ® C [Substitute B ® ∈ ]
A®a
B ® bAC
B ® bA [Substitute C ® ∈ ]
B ® bC [Substitute A ® ∈ ]
B ® b [Substitute A ® ∈ , C ® ∈ ]
C ® cAB
C ® cA [Substitute B ® ∈ ]
C ® cB [Substitute A ® ∈ ]
C ® c [Substitute A ® ∈ , B ® ∈ ]
Step 3: Final Grammar is:
S ® ABC | AB | BC | AC | A | B | C
Context-Free Language and Pushdown Automata

A ® BC | B | C | a
B ® bAC | bA | bC | b
C ® cAB | cA | cB | c

Rack Your Brain

Find a context free grammar without ∈-production equivalent to the

grammar defined by:
S → ABaC
A → BC
B → b|∈
C → D|∈
D→d

146
 Chapter 4
Eliminating unit productions:

Definition

Unit Production: Any production of a context-free grammar of the

form A → B, where A, B ∈ V (variables), is called a unit production.

To remove unit production, we use the substitution rule:

Step 1: Write the given grammar without unit production.
Step 2: Write the given grammar’s all those production which goes to the unit
production and further unit production produce terminals.
Step 3: Add all those new productions in the grammar obtained in step 1.
Note:
Meaning of Grammar should not be changed while doing elimination of unit production.

SOLVED EXAMPLES

Q1 S → Aa | B
B → A | bb
A → a | bc | B
Eliminate unit-production from the given grammar.

Sol: Step 1: Grammar without unit production.

Context-Free Language and Pushdown Automata

S → Aa
B → bb
A → a | bc
Step 2: Productions which gives unit production:

S  B  bb
a
S BA
bc

a add these productions in

BA
bc grammar obtained in step 1.

add these productions in

A  B  bb
grammar obtained in step 1.

147
Chapter 4

Step 3: Final grammar without unit production.

S → Aa | bb | a | bc
B → bb | a | bc
A → a | bc | bb

Q2 S → AB
A→a
B → C|b
C→D
D→E
E→a
S, A, B, C, D, E E Variables and T = {a, b}
Eliminate Unit - Productions from the given grammar.

Sol: Step 1: Productions without unit production.

S → AB
A → a
B → b
E → a
Step 2: Productions which give unit – production.

i) B  C D E a
Add all this production in grammar
ii) C  D E a
obtained in step 1
iii) D  E a
Context-Free Language and Pushdown Automata

Step 3: Grammar without unit productions

S → AB
A→a
B→b|a

Ca Here C, D, E are not reachable from the start ‘S’.

Da So, these are useless symbols which will be
Ea removed.

Final Grammar will be:

S → AB
A→a
B→b|a

148
 Chapter 4
Eliminating useless symbols:
y Symbol X is a useless symbol for a grammar G = (V,T,P,S) if that symbol can never take
part in any derivation.
Example: S → aSb|∈|A
A → aA
y Here, the production S → A is useless as A cannot be transformed into a terminal string.
y Removing this production S → A leaves the language unaffected and is a simplification
by any definition.
Note:
A variable is useful if it is reachable from the start state and is also able to derive some
terminal or some strings of terminals.

SOLVED EXAMPLES

Sol:   Here, we can remove B → bA, since B is not reachable from the start state.
Final grammar is
S→A
A → aA|Î

Context-Free Language and Pushdown Automata

Sol:    � Initially, only B and C be the non-terminal symbols that directly generates
terminal strings; hence useful symbol.
� S is useful because the rule S → aBC
� A is useful because the rule A → aS
� D does not generate terminal strings; thus, it is a useless symbol.
� Eliminate D and those productions involving D, we get grammar:
S → aAa|aBC

149
Chapter 4

A → aS
B → aBa | b
C → abb

Sol:   Another way

Terminals are always useful symbols. Since here, a and b are terminal. So,
� 
they are useful.
Combination of terminal symbols generated by any rules then non-terminals
� 
also useful.
� As A → a, so, A is useful, B → bbA which produces B → bba so, B also useful.
Similarly, S → AB is a combination of two useful symbols A and B. So, S is also
� 
useful.
A useful symbols = {a, b, A, B, S}
� C and D must be removed because they are not producing terminals.
So, remove S → AC, C → abCA | aDb, D→ bD | aC from the grammar.
Final grammar:
S → AB
A → aAb | bAa | a
Context-Free Language and Pushdown Automata

B → bbA | aaB| AB
All are reachable from the start symbol S.

Rack Your Brain

What will be the final grammar after removing the useless symbols
from the given grammar:
S → aS|A|C
A→a
B → aa
C → aCb

150
 Chapter 4
Theorem:
Let G = (V,T,S,P) be a context-free grammar. Then there exists an equivalent
grammar G ˆ = (V,
ˆ T, ˆ ˆ that does not contain any useless variables or
ˆ S,P)
productions.
Note:
When we want to convert any CFG into an equivalent CFG that has no
useless symbols, ∈-productions and unit-productions. Some care must be
taken in order of application of the consturction.
A safe order is:
i) Eliminate E-production.
ii) Eliminate unit production.
iii) Elminiate useless-symbols.

Rack Your Brain

Does removal of Î-productions introduces previously non-existent

unit-productions?

Normal forms:
When working with context-free grammar, it is often
convenient to have them in simplified form. There are two
types of normal forms of context-free grammar.

Normal Forms

Context-Free Language and Pushdown Automata

Chomsky Normal Griebach Normal
Form Form
Fig. 4.2 Types of Normal Forms

Chomsky’s normal form:

151
Chapter 4

Definition

A context free grammar is in Chomsky Normal Form, if every rule is of

the form:
A → BC
OR
A→a
where A, B, C are in V (variables) and a is any terminal.

Note:
In addition, we permit the rule S → ∈, where S is the start symbol in
Chomsky Normal Form.

Example: S → AS | a
A → SA | b
is in Chomsky Normal Form.
Whereas the grammar:
S → AS | AAS
A → SA | aa
is not in Chomsky Normal Form; both productions S → AAS and A → aa
violate the condition of the definition of Chomsky Normal Form.
Theorem:
Any context-free language is generated by a context-free grammar in
Chomsky’s normal form.
Context-Free Language and Pushdown Automata

Advantages of Chomsky’s normal form:

i) Length of each production is restricted.
ii) Derivation tree (parse tree) obtained from CNF is always a binary tree.
iii) The number of steps required to derive a string of length |w| is (2|w|-1).
Example: S → AB
A→a
B→b
Let us have to derive the string w = ab.
So, |w| = length of string = 2.
S ⇒ AB
⇒ aB
⇒ ab
3 steps are needed. Thus a number of steps are required to derive a
string ‘ab’ in the given grammar

152
 Chapter 4
= 2|w| – 1
= 2×2 – 1 = 3
iv) It is easy to apply the CYK membership algorithm, which is of the
polynomial type having time complexity = O(n3)

Note:
Given any Chomsky Normal Form Grammar, CYK membership algorithm
can parse it.

Previous Years’ Question

If G is a context free grammar and w is a string of length l in L(G), how long is a

derivation of w in G, if G is in Chomsky Normal Form? (GATE - 1992)
1) 1) 2l 2) 2l+1
3) 2l – 1 4) l
Sol: Option 3)

CYK algorithm:
This algorithm is only applicable if the given grammar is in CNF.
Check whether the string “baaba” is a valid member of the following CFG.
S → AB|BC
A → BA|a
B → CC|b
C → AB|a

Context-Free Language and Pushdown Automata

Let’s see how to fill the above table:

1) (1,1) → Starting with ‘1’ (‘b’) and ending with ‘1’ (‘b’)
‘b’ is generated by B.
Similarly we can compute for (2,2), (3,3), (4,4) (5,5)
2) (1,2) → Starts with 1(‘b) and ends with 2(‘a’)
(1,2) = (1,1) (2,2)
= {B} {A,C}
= {BA, BC}

153
Chapter 4

‘BA’ is generated by ‘A’

‘BC’ is generated by ‘S’
3) (2,3) = (2,2) (3,3)
= {A,C} {A,C}
= {AA, AC, CA, CC}
| | | |
X X X generated by ‘B’
4) (3,4) = {3,3} {4,4}
= {A,C} {B}
= {AB, CB}
| |
generated X
by ‘S’ and ‘C’
5) (4,5) = {4,4} {5,5}
= {B} {A,S}
= {BA, BC}
/ \
generated generated
by ‘A’ by ‘S’
6) (1, 3) = = {1,1} {2,3} or {1,2} {3,3}
= {B} {B} = {A,S} {A,C}
= {BB} = {AA, AC, SA, SC}
| | | | |
X X X X X
Context-Free Language and Pushdown Automata

\ (1,3) = f
Similarly, we can fill the other entries in the table.
(1,5) can be generated by ‘S’ (Starting symbol)
\ baaba can be generated by grammar.
What is the substring of “baaba” that can be derived from this grammar?
From the table entries, we select the entries that have ‘S’ (starting symbol)
(1, 2) ® ‘S’ can generate ‘ba’
(2, 5) ® ‘S’ can generate ‘aaba’
(3, 4) ® ‘S’ can generate ‘ab’
Time complexity:
We are filling n2 cells.
For each cell, in the worst case, we might need O(n) time.

154
 Chapter 4
Total complexity
= O(n2 ) × O(n)
= O(n3 )

Greibach normal form:

A context-free grammar is in GNF (Greibach Normal Form) if all the productions are of the
form:
A→a∝
where ∝ ∈ v* (non-terminal)
a ∈ T (Terminals), A ∈ V
Example: A → aBCDE
A → a

Note:
Every context free grammar can be transformed into an equivalent
grammar in Greibach Normal Form.

Advantages of Greibach normal form:

1) The number of steps required to generate a string of length |w| is |w|.
Example: A → aB
B → b

Let we have to derive the strings w = ‘ab’, |w| = length of strings = 2

Step 1: A ⇒ aB
Step 2: A ⇒ ab

Context-Free Language and Pushdown Automata

So, the number of steps required to derive the string w = ‘ab’ in the given form is 2
2) Greibach Normal Form (GNF) is useful in order to convert a CFG into PDA.

Converting context-free grammar to Chomsky’s normal form:

SOLVED EXAMPLES

155
Chapter 4

Sol: As required, the grammar does not have any ∈ -productions or any
unit productions.
Step 1: Introduce new variables Na, Nb, Nc and replace a with Na, b
with Nb, c with Nc.
S → ABNa
A → NaNaNc
B → ANc
Na → a
Nb → b
Nc → c
Step 2: Introduce additional variables to get the first two
productions into Normal form:
S → AD1
D1 → BNa
A → NaD2
D2 → NaNb
B → ANc
Na → a
Nb → b
Nc → c

Note:
CNF produces the same language which is generated by CFG (Context
Free Grammar).
Context-Free Language and Pushdown Automata

Q2 Convert the following grammar with production:

S → bA | aB
A → bAA | aS| a
B → aBB | bs | b
to Chomsky Normal Form.

Sol: As required, the grammar does not have any ∈ -productions or any
unit productions.
Step 1: Introduce new variables Na, Nb.
S → NbA | NaB
A → NbAA | NaS | a
B → NaBB | NbS | b

156
 Chapter 4
Na → a
Nb → b
Step 2: Introduce additional variables C1 and C2.
S → NbA | NaB
A → NbC1 | NaS | a
B → NaC2 | NbS | b
Na → a
Nb → b
C1 → AA
C2 → BB

Note:
For a given grammar, more than one CNF can be possible.

Grey Matter Alert!

Given a grammar G of length n, we can find an equivalent Chomsky Normal Form

Grammar for G in time O(n2), the resulting grammar has length O(n2).

Converting context-free grammar to Greibach normal form conversion

(CFG → GNF)
Variable → Terminal
Variable → Terminal variable

Context-Free Language and Pushdown Automata

Variable → Terminal variable variable variable..

SOLVED EXAMPLES

Sol: In GNF:
S → aSB | aB
B→b

157
Chapter 4

Sol: In GNF:
S → bAB | cB
A→b|c
B→c

Sol: In GNF:
S → mSA | mA
A→n
Context-Free Language and Pushdown Automata

Sol: In GNF:
S → aBX | bCY
B → bBY | b
C → bCY | a
X→b
Y→a

158
 Chapter 4
4.2 PUSHDOWN AUTOMATA
Definition
A pushdown Automata is a non-deterministic finite automaton coupled with a stack that
can be used to store a string of arbitrary length. The stack can be read and modified only
at its top.
(OR)
The automaton which defines context-free languages is known as pushdown Automata.
A Non-deterministic pushdown Acceptor (NPDA) is defined by the set tuples:
M (Q, Σ,τ, δ, q0, Z, F)
Where,
Q : A finite set of states,
Σ : A finite set of input symbols.
τ : A finite stack alphabet.
(set of symbols that we are allowed to push into the stack)
δ : Q × (Σ ∪ {∈}) × τ → set of finite subsets of Q × τ* is the transition function.
q0 ∈ Q is the initial state of the control unit.
Z0 : Z0 ∈ τ is the stack start symbol.
F : F ⊆ Q is the set of final states.

Finite State
Control

Context-Free Language and Pushdown Automata

Fig. 4.3 Pushdown Automata

y Pushdown Automata is basically a finite Automaton with a stack.

y A pushdown Automata can write symbols on the stack and read them back later.
y Writing a symbol on the stack is referred to as pushing the symbol.
y Removing a symbol is referred to as popping it.

159
Chapter 4

Grey Matter Alert!

A stack is valuable part of Pushdown Automata because it can hold an unlimited

amount of information.

Example: L = {anbn | n ≥ 1}
We cannot construct the finite Automata corresponding to this language.
L is context-free language.
We can construct a push down Automata for Language L.

(a, z0 | az0 ) (b, a| ∈)

(b, a | ∈) (∈, Z0 |z0)

q0 q1 qf

(a, a | aa)

Consider a string w = aabb

Context-Free Language and Pushdown Automata

δ(q0 , b, a) = (q,1 ∈) a
Z0
pop ‘a’

δ(q1 , b, a) = (q,1 ∈)
Z0
pop ‘a’

160
 Chapter 4
Pushdown automata acceptance can be done in 2 ways:
1) acceptance by final state:
Let P = (Q, ∑, τ, δ, q0, z0, F) be a PDA.
Then language accepted by P is the set
L(P) = {W | (q0, w, z0) (qf, ∈, s)}

Where qf is a final state and s is any stack string.

i.e. language accepted by P is the set of all strings that can put P into a final state at the
end of the string.

2) Acceptance by empty stack:

An NPDA P = (Q, ∑, τ, δ, q0, z0, F) is said to accept the language N(P) by empty stack if,
N(P) = {W | (q0, w, z0) (q, ∈, ∈)} for any state q.
That is, N(P) is a set of inputs W that P can consume, and when the end of the input string
is reached, PDA has emptied the stack.

Deterministic and non deterministic pushdown automata:

y Deterministic pushdown Automata and Non-Deterministic pushdown differ in terms of
their expressive power.
y Non-Deterministic pushdown automata are more powerful than Deterministic
pushdown Automata.

Context-Free Language and Pushdown Automata

y Transition function (δ) for Deterministic Pushdown Automata:
δ: Q×{∑∪∈} × τ → Q × τ*
y Transition function (δ) for Non-Deterministic Pushdown Automata:
δ : Q×{∑∪∈} × τ → set of finite subsets of Q × τ * is the transition function.

161
Chapter 4

SOLVED EXAMPLES

Sol: (b,z0 | bz0 )

(a, z0 | az0 )

(∈, z0 |z0 )
q0 qf

(a, a | aa)
(b, b | bb)
(a, b | ∈)
(b, a | ∈)

Consider a string w = abbbaa

Here, number of a’s in w = number of b’s in w

δ(q0, a, z0) = (q0, az0) a

z0
push ‘a’

δ(q0, b, a) = (q0, ∈)
z0
pop ‘a’
Context-Free Language and Pushdown Automata

δ(q0, b, z0) = (q0, bz0) b

z0
push ‘b’

b
δ(q0, b, b) = (q0, bb) b
z0
push ‘b’

δ(q0, a, b) = (q0, ∈) b
z0
pop ‘b’

162
 Chapter 4
δ(q0, a, b) = (q0, ∈)
z0
pop ‘b’

δ(q0, ∈, z0) = (qf, z0)

Sol:
(a, a | aa)
(a, z0 | az0 ) (b, a | a) (c, a |∈)

(b, a | a ) (c, a |∈ ) (∈, z0 | z0)

q0 q1 q2 qf

Consider a string w = aabcc

δ (q0, a, z0) = (q0, az0) push ‘a’ onto the stack
δ (q0, a, a) = (q0, aa) push ‘a’ onto the stack
δ (q0, b, a) = (q1, a) Do Nothing (skip)
δ (q1, c, a) = (q2, ∈) pop ‘a’
δ (q2, c, a) = (q2, ∈) pop ‘a’
δ (q2, ∈, z0) = (qf, z0)

Context-Free Language and Pushdown Automata

Sol:
(a, a | aa)
(a, z0 | az0 ) (b, a | ∈) (c, a |∈)

(b, a | ∈) (c, a |∈ ) (∈, z0 | z0)

q0 q1 q2 qf

163
Chapter 4

Consider a string w = aaabbc

We can write L = {am+nbmcn | m, n ≥ 1}
as L = {anambmcn | m, n ≥ 1}
δ (q0, a, z0) = (q0, az0) push ‘a’ onto the stack
δ (q0, a, a) = (q0, aa) push ‘a’ onto the stack
δ (q0, a, a) = (q0, aa) push ‘a’ onto the stack
δ (q0, b, a) = (q1, ∈) pop ‘a’
δ (q1, b, a) = (q1, ∈) pop ‘a’
δ (q1, c, a) = (q2, ∈) pop ‘a’
δ (q2, ∈, z0) = (qf, z0)

Rack Your Brain

Construct a PDA for the language: L = {an+1 b2n | n ≥ O}

Previous Years’ Question

Consider the transition diagram of a PDA given below with input alphabet ∑ = {a, b} and
stack alphabet τ = {X, Z}, Z is the initial stack symbol.
Let L denote the language accepted by the PDA.
Context-Free Language and Pushdown Automata

Which one of the following is TRUE?  (GATE 2016 (Set-1))

1) L = {a b | n ≥ O} and is not accepted by any Finite Automata.
n n

2) L = {an | n ≥ O} ∪ {anbn | n ≥ O} and is not accepted by any Deterministic PDA.

3) L is not accepted by any Turing Machine that halts on every input.
4) L = {an | n ≥ O} ∪ {anbn | n ≥ O} and is deterministic context free.
Sol: Option 4)

164
 Chapter 4
Sol: Push 2 a’s onto stack on seeing 1 a in input
(a, z0 | aaz0) (b, a | ∈)

(b, a | ∈) (∈, z0 | z0 )
q0 q1 q2

(a, a | aaa)

Consider a string w = aabbbb

δ (q0, a, z0) = (q0, aaz0) Push 2 a’s on seeing 1 a in input
δ (q0, a, a) = (q0, aaa) Push 2 a’s onto stack
δ (q0, b, a) = (q1, ∈) Pop One a on input b
δ (q1, b, a) = (q1, ∈) Pop One a on input b
δ (q1, b, a) = (q1, ∈) Pop One a on input b
δ (q1, b, a) = (q1, ∈) Pop One a on input b
δ (q1, ∈, z0) = (q2, z0)
Method: 2
(a, z0 | az0 )

(b, a | a ) (b, a | ∈) (∈, z0 | z0 )

q0 q1 q2 q3

Context-Free Language and Pushdown Automata

(b, a | a )
(a, a | aa)

Consider a string w = aabbbb

δ(q0, a, z0) = (q0, az0) a Push ‘a’

z0

a
δ(q0, a, a) = (q0, aa) a Push ‘a’
z0

a
δ(q0, b, a) = (q1, a) a Do Nothing (Skip)
z0

165
Chapter 4

δ(q1, b, a) = (q2, ∈) a Pop ‘a’

z0

δ(q2, b, a) = (q1, a) a Do Nothing (Skip)

z0

δ(q1, b, a) = (q2, ∈) Pop ‘a’

z0

δ(q2, ∈, z0) = (q3, z0)

Sol: On input ‘a’ perform push operation onto the stack. On input ‘c’, skip (i.e., do nothing).
On input ‘b’ and ‘a’ on top of stack, perform pop operations.
(a, z0 | az0) (b, a | ∈ )

(c, a | a) (∈, z0 | ∈ )
q0 q1 q2

(a, a | aa)
Context-Free Language and Pushdown Automata

Consider a string w = aacbb.

δ(q0, a, z0) = (q0, az0) a

z0

a
δ(q0, a, a) = (q0, aa) a
z0

a
δ(q0, c, a) = (q1, a) a Do Nothing
z0

δ(q1, b, a) = (q1, ∈) a Pop ‘a’

z0

166
 Chapter 4
δ(q1, b, a) = (q1, ∈) Pop ‘a’
z0

δ(q1, ∈, z0) = (q2, z0)

Sol:
(a, a | aa)
(a, z0 | az0) (a, a | ∈ )
(c, z0 | z0 )
(c, a | a) (∈, z0 | z0 )
q0 q1 q2
(c, b | b)

(b, z0 | bz0) (b, b | ∈ )

(b, b | bb)
(a, b | ab)
(b, a | ba)

ab c ba
Consider a string =
w c wR

δ(q0, a, z0) = (q0, az0) a Push ‘a’

z0

Context-Free Language and Pushdown Automata

b
δ(q0, b, a) = (q0, ba) a Push ‘b’
z0

δ(q0, c, b) = (q1, b) Do Nothing

δ(q1, b, b) = (q1, ∈) a Pop ‘b’

z0

δ(q1, a, a) = (q1, ∈) Pop ‘a’

z0

δ(q1, ∈, z0) = (q2, z0)

167
Chapter 4

Previous Years’ Question

Consider the Pushdown Automaton (PDA) below which runs over the input alphabet
(a, b, c). It has stack alphabet {z0, x} where z0 is the bottom-of-stack marker. The set
of states of the PDA is (s, t, u, f) where s is the start state and f is the final state. The
PDA accepts by final states. The transitions of the PDA given below are depicted in a
standard manner. For example, the transition (s, b, x) → (t, xz0) means that if the PDA
is in state s and the symbol on the top of the stack is x, then it can read b from the
input and move to state t after popping top of stack and pushing the symbols z0 and x
(in that order) on the stack. (GATE IT 2006)
(s, a, z0) → (s, xxz0)
(s, ∈, zo) → (f, ∈)
(s, a, x) → (s, xxx)
(s, b, x) → (t, ∈)
(t, b, x) → (t, ∈)
(t, c, x) → (u, ∈)
(u, c, x) → (u, ∈)
(u, ∈, z0 ) → (f, ∈)
The language accepted by the PDA is:
1) {albmcn | l = m = n}
2) {albmcn | l = m}
3) {albmcn | 2l = m + n}
4) {albmcn | m = n}
Context-Free Language and Pushdown Automata

Sol: Option 3)

Rack Your Brain

Construct PDA that accepts the following language on Σ = {a, b, c}

L = {an bm cn+m |n ≥ 0, m ≥ O}.

168
 Chapter 4
Sol: We cannot construct deterministic pushdown Automata for the
given language L = {wwR | w∈{a, b}*}.
Here Non-determinism comes into picture since on same state, on
same input more than one transition will be defined.

(b, z0 | bz0 ) (a, a | ∈ )

(a, z0 | az0) (b, b|∈)

(b, b|∈) (∈, z0 | z0 )

q0 q1 q2
(a, a|∈)

(b, a | ba) (∈, z0 | z0 )

(b, b | bb)
(a, b | ab)
(a, a | aa)

δ (q0, a, z0) = (q0, az0)

δ (q0, b, z0) = (q0, bz0)
δ (q0, a, a) = (q0, aa) or (q1, ∈)
δ (q0, b, b) = (q0, bb) or (q1, ∈)

Context-Free Language and Pushdown Automata

δ (q0, a, b) = (q0, ab)
δ (q0, b, a) = (q0, ba)
δ (q1, ∈, z0) = (q2, z0)
δ (q0, ∈, z0) = (q2, z0)
δ (q1, a, a) = (q1, ∈)
δ (q1, b, b) = (q1, ∈)

169
Chapter 4

Sol:

Difference between DPDA and NPDA:

Deterministic pushdown Non-deterministic pushdown

automata automata

1) Transition function for 1) Transition function for non-

deterministic pushdown deterministic pushdown
automata: Automata:

δ : Q × {Σ  ∈} × τ → Q × τ * δ : Q × {Σ  ∈} × τ → set of

finite subsets of Q × τ *
Context-Free Language and Pushdown Automata

2) Only one transition is 2) More than one transition can

defined from a state on be defined from a state on
an input symbol and stack an input symbol and stack
symbol. symbol.

3) DPDA is less powerful than 3) NPDA is more powerful than

NPDA. DPDA.

Table 4.1 Differences

Rack Your Brain

Construct NPDA’s that accepts the language L = {anbm | n ≥ 0, n ≠ m}.

170
 Chapter 4
Previous Years’ Question

Consider the NPDA < Q = {q0, q1, q2}, ∑ = {0, 1}, τ = {0, 1, ⊥}, δ, q0, ⊥, F = {q2} >
Where (as per usual convention) Q is the set of states, ∑ is the input alphabet, τ is the
stack alphabet, δ is the state transition function, q0 is the initial state, ⊥ is the initial
stack symbol, and F is the set of accepting states. The state transition is as follow:
 ( GATE 2015 (Set-1))

Which one of the following sequences must follow the string 101100 so that the overall
string is accepted by the automaton?
1) 10110 2) 10010
3) 01010 4) 01001
Sol: Option 2)

Rack Your Brain

Construct NPDA on ∑ = {a, b, c} that accepts the language

Context-Free Language and Pushdown Automata

L = {w1cw2 |w1, w2 ∈ {a, b}*, w1 ≠ w2}.

Equivalence between CFL and CFG

1) L = {ambn | m = n}
Grammar corresponding to given CFL:
S → aSb|∈
2) L = {ambn | m = 2n}
Grammar Corresponding to given CFL:
S → aaSb|∈
3) L = {ambncn | m, n ≥ 1}
Grammar Corresponding to given CFL:
S → AB
A → a|aA
B → bBc|bc
171
Chapter 4

4) L = {anbpcn | p, n ≥ 1}
Grammar Corresponding to given CFL:
S → aSc|aAc
A → bB|b
5) L = {ambn | m > n; m,n ≥ 1}
Grammar Corresponding to given CFL:
S → aSb|aAb
A → aA|a
6) L = {ambn | m ≠ n; m,n ≥ 1}
Cases: m > n or m < n
S → S1 | S2
S1 → aS1b|aAb
A → aA |a
S2 → aS2b|aBb
B → bB|b
7) L = {w| |wa| = |wb|, w∈{a, b}*} (number of a’s and number of b’s should be
equal)
Grammar Corresponding to given CFL:
S → SaSbS | SbSaS | ∈

Closure properties of CFL’s

The context-free languages are closed under:
y Union:
Let L1 and L2 be CFL’s, then L1 ∪ L2 is also context-free language.
y Concatenation:
Context-Free Language and Pushdown Automata

Let L1 and L2 be CFL’s, then L1.L2 is also context-free language.

y Kleen-closure:
If L1 is a CFL, then L*1 is also context-free language.
y Reversal:
The CFL’s are also closed under reversal.
If L is a CFL, then so is LR.
y The family of context-free languages is not closed under intersection,
set difference, and complementation.
y If CFL is not closed under intersection means there exist two CFL
languages for which CFL ∩ CFL2 ¹ CFL.
Example: Consider the two languages:
L1 = {anbncm | n ≥ 0, m ≥ 0} and L2 = {anbmcm | n ≥ 0, m ≥ 0}, then
L1 ∩ L2 = {anbncn| n ≥ 0} which is not context-free.

172
 Chapter 4
Thus, context-free language is not closed under intersections.

Again, L1 ∩ L2 = L1 ∪ L2
If the family of context-free languages was closed under complementation,
then the right side of the above expression would be a context-free language
for any context-free L1 and L2.

But this contradicts since we have shown, the intersection of two context-
free languages is not necessarily context-free. Thus, the family of context-
free languages is not closed under complementation.

Note:
If L is a CFL and R is a regular language, then L ∩ R is a context free
language.

Rack Your Brain

Is the language L = {anbn| n ≥ 0, n ≠ 100} is context free?

Previous Years’ Question

Let L1 be a regular language and L2 be a context free language. Which of the following

Context-Free Language and Pushdown Automata

languages is/are context free? (GATE 2021 (Set-2))
–
1) L1 ∩ L2
– –
2) L1 ∪ L2
–
3) L1 ∪ (L2 ∪ L2)
–
4) (L1 ∩ L2) ∪ (L1 ∩ L2)
Sol: Option 2) 3), 4)

173
Chapter 4

Previous Years’ Question

Let L1, L2 be any two context free languages and R be any regular language, then which
of the following is/are CORRECT? (GATE 2017 (Set-2))
I) L1 ∪ L2 is context free.
–
II) L1 is context free.
III) L1 – R is context free.
IV) L1 ∩ L2 is context free.
1) I, II and IV only 2) I and III only
3) II and IV only 4) I only
Sol: Option 2)

y CFLs are closed with the following operations:

1) Union
2) Concatenation
3) Kleene closure
4) Substitution
5) Homomorphism
6) Inverse Homomorphism
7) Reversal
8) Intersection with a regular set
9) INIT (L)
� CFL are not closed under the following operations:
  i) Intersection
  ii) Complement
Context-Free Language and Pushdown Automata

  iii) Set difference

iv) Quotient
v) Inverse substitution

Deterministic Context-Free Languages (DCFLs)

Definition

The language that are recognized by deterministic pushdown Automata

(DPDAs) are called as Deterministic Context free languages (DCFLs).

y This subclass of context-free languages is relevant to practical

applications, such as the design of parsers in compilers for programming
languages.

174
 Chapter 4
y In DPDAs, at each step of its computation, the DPDA has at most one
way to proceed according to its transition function.
Example: L = {0n1n | n ≥ 0} is DCFL.

Note:
Every language accepted by DPDA is also accepted by NPDA but converse
need not to be true.

Closure properties of DCFL

y The class of DCFLs is closed under complementation.
y The class of DCFLs is closed under Intersection with Regular set.
If L1 = DCFL and L2 = Regular language
Then L1 ∩ L2 is DCFL

y The class of DCFLs is closed under Inverse Homomorphism.

y DCFLs are not closed under the following operations:
1) Union
2) Concatenation
3) Kleene closure
4) Homomorphism
5) Intersection
6) Substitution
7) Reversal
8) ∈ -free Homomorphism

Context-Free Language and Pushdown Automata

Rack Your Brain

Is the language L = {anbmIm > n + 2} is deterministic?

Grey Matter Alert!

• If a Grammar G is an LL(K) grammar, then L(G) is a deterministic context free

language.
• A grammar is an LL(K) grammar if we can uniquely identify the correct
production, given the currently scanned symbol and a ‘look-ahead’ of the next
K-1 symbols.

175
Chapter 4

Previous Years’ Question

If L1 and L2 are context free languages and R a regular set, one of the languages below
is not necessarily a context free language? (GATE -1996)
Which one?
1) L1.L2 2) L1 ∩ L2 3) L1 ∩ R 4) L1 ∪ L2
Sol: Option 2)

Previous Years’ Question

Let L be a context free language and M a regular language. Then the language L ∩ M is:
 (GATE-2006)
1) always regular
2) never regular
3) always a deterministic context free language
4) always a context free language
Sol: Option 4)

Decision properties of CFL’s

The following problems are decidable under CFL’s:
1) Emptiness problem
Context-Free Language and Pushdown Automata

2) Finiteness problem
3) Membership problem

Emptiness problem:
Given a context-free grammar G = (V, T, S, P), there exists an algorithm for
deciding whether L (G) is empty or not; hence this is a decidable problem.
ECFG = { <G> | G is a CFG and L(G) = φ }

Finiteness problem:
Given a context-free grammar G = (V, T, S, P), there exists an algorithm for
determining whether L(G) is infinite or not.

Membership problem:
Given a context-free grammar G = (V, T, S, P), there exists an algorithm, for
deciding whether a given word w is in the language defined by a context-
free grammar.

176
 Chapter 4
Proof:
y Start by converting whatever representation of L is given into a CNF
grammar for L.
y As the parse trees of a Chomsky-normal form grammar are binary
trees, if w is of length n then there will be exactly 2n-1 nodes labelled
by variables in the tree.
y The number of possible trees and node-labellings is thus only
exponential in n. List them all and check if any of them yields w.

Note:
There is much more efficient technique based on the idea of dynamic
programming, known as table filling algorithm or tabulation.
This algorithm is CYK algorithm; used to test membership in a context
free language.

Grey Matter Alert!

The Cocke-Younger-Kasami (CYK) algorithm tells whether a given string is in a

given context free language. For a fixed CFL, this test takes time O(n3), if n is the
length of the string being tested.

Undecidable CFL problems

1) Is a given CFG G ambiguous?

Context-Free Language and Pushdown Automata

2) Is a given CFL inherently ambiguous?
3) Is the intersection of two CFL’s empty?
4) Are two CFL’s the same?
Is a given CFL equal to Σ* , where Σ is the alphabet of this language?

Rack Your Brain

Does L(G) contain atleast 100 strings, for a given CFG G?

Is the given problem is decidable?

177
Chapter 4

Previous Years’ Question

Which of the following problems is undecidable?  (GATE 2014 (Set 3))

1) Deciding if a given context free grammar is ambiguous.
2) Deciding if a given string is generated by a given context free grammar.
3) Deciding if the language generated by a given context free grammar is empty.
4) Deciding if the language generated by a given context free grammar is finite.
Sol: Option 1)

Rack Your Brain

Which of the following problem is undecidable?

a) Completeness problem for CFGs
b) Equivalence problem for CFGs

Pumping lemma for context-free language:

Let L be an infinite context-free language. Then there exists some
positive integer m such that any w ∈ L with |w| ≥ m can be decomposed
as
w = uvxyz,
with |vxy| ≤ m,
Context-Free Language and Pushdown Automata

and |vy| ≥ 1
Such that
uvi xyiz ∈ L
for all i = 0, 1, 2, …
This is known as the pumping lemma for context-free languages.

Note:
Pumping lemma for context free language are used negatively to show
that a given language does not belong to context free language family.

Show that the language:

Example: L = {anbncn | n ≥ 0} is not context-free language.
Sol.: Let’s assume L is context-free language
∃m ≥ 1

178
 Chapter 4
such that
w ∈ L with |w| ≥ m
w = akbkck
Here 3k ≥ m
Now, split akbkck in uvxyz.

|vxy| = k + 1 ≤ m
Hence, uvixyiz ∈L ∀ i = 0, 1, 2, …
for i = 2, ak–1 a2 bk ∈ ck
⇒ ak+1 bk ck which does not belong to given language
\ L = {anbncn | n ≥ 0} is not context-free language.

Note:
If Σ = {a} i.e. singleton set and language L is defined over L then Lis context free language
if and only if the length of strings in L are in arithmetic progression.

eg. 1: L = {a3n-1| n ≥ 1}
={aaaa, aaaaaaa, ........}
context free language. (Following arithmetic progression)

eg. 2: L ={a°|p is a prime}

Context-Free Language and Pushdown Automata

={aa, aaa, aaaaa, ........}
Not context free language. (Not following arithmetic progression)

eg. 3: L ={an2In ≥ 1}
={a, aaaa, .........}
Not context free languages (Not following arithmetic progression)

eg.4: L={an1In ≥ 1}
={a, aa, aaaaaa, ........}
Not context free langauge (Not following arithmetic progression)

179
Chapter 4

4.3 CSL AND GRAMMAR

Context-sensitive grammar:

Definition

A grammar G = (V, T, S, P) is said to be context sensitive if all productions

are of the form,
x → y,
where x, y ∈ (VUT)* and |x| ≥ |y|

Grey Matter Alert!

The definition shows clearly that this grammar is non contracting in the sense
that the length of successive sentential forms can never decrease.
All such grammars can be rewritten in a normal form in which all productions
are of the form:
xAy → xvy
This is equivalent to saying that the production
A→ v
can be applied only in the situation where A occurs in a context of the string x
on the left and the stringy on the right.
eg. : S → abc/aAbc
Ab → bA
Ac → Bbcc
bB → Bb
Context-Free Language and Pushdown Automata

aB → aa/aaA is an example of context sensitive grammar.

Context-sensitive languages:
The language generated by the context-sensitive grammar is known as
context-sensitive languages.

Definition

A language L is said to be context sensitive if there exists a context

sensitive grammar G such that
L = L(G) or, L = L(G)U{∈}

Here, in this definition, we reintroduce the empty string:

y Definition of context-sensitive grammar implies that x ® ∈ is not

180
 Chapter 4
allowed so that a context-sensitive grammar can never generate a
language containing the empty string.
y Every context-free language without ∈ can be generated by a special
case of a context-sensitive grammar, say by one in Chomsky or
Greibach’s normal form. Both satisfy the condition of context-free
grammar defined earlier.

Note:
By including the empty string in the definition of a context sensitive
language. We can claim that the family of context free language is a
subset of the family of context sensitive languages.

Example 1: The language L = {anbncn |n ≥ 1} is a Context-Sensitive language.

Context-Sensitive grammar exists for this language is:
S → abc|aAbc
Ab → bA
Ac → Bbcc
bB → Bb
aB → aa|aaA
Look at a derivation of a3b3c3.
S ⇒ aAbc
⇒ abAc
⇒ abBbcc
⇒ aBbbcc
⇒ aaAbbcc

Context-Free Language and Pushdown Automata

⇒ aabAbcc
⇒ aabbAcc
⇒ aabbBbccc
⇒ aabBbbccc
⇒ aaBbbbccc
⇒ aaabbbccc

Note:
The language in the previous example is not context free, we can say
that the family of context free languages is a proper subset of the
family of context sensitive languages.

181
Chapter 4

Example 2 : T
 he language L={anbmcndm |n,m ≥ 1} is a Context-Sensitive
language. Context-Sensitive grammar exists for this language
is:
S → aAB | aB
A → aAX | aX
B → bBd | bYd
Xb → bX
XY → Yc
Y → c
Derivation of string aabbbccddd as follows:
S ⇒ aAB
⇒ aaXB
⇒ aaXbBd
⇒ aaXbbBdd
⇒ aaXbbbYddd
⇒ aabXbbYddd
⇒ aabbXbYddd
⇒ aabbbXYddd
⇒ aabbbYcddd
⇒ aabbbccddd

Example of Context-Sensitive languages

L1 = {anbncn | n ≥ 1}
L2 = {an! | n ≥ 0}
n
L3 = {a
= | n m2 ,m ≥ 1}
Context-Free Language and Pushdown Automata

L4 = {an | n is a prime number}

L5 = {an | n is not a prime number}
L6 = {ww | w ∈ (a,b)+ }
L7 = {wn | w ∈ (a,b)+ ,n ≥ 1}
L8 = {wwwR | w ∈ {a,b} + }

Rack Your Brain

Find context sensitive grammars for the languages:

a) L = {w | na(w) = nb(w) = nc(w)}
b) L = {w | na(w) = nb(w) < nc(w)}

182
 Chapter 4
Theorem:
For every Context-Sensitive language L not including ∈, there exists some
linear bounded automaton M such that L = L(M).

Theorem:
If a language L is accepted by some linear bounded automaton M, then
there exists a Context-Sensitive grammar that generates L.

Relation between recursively enumerable and context-sensitive languages:

Every Context-Sensitive language is accepted by some Turing machine and
is therefore recursively enumerable.

Theorem:
Every Context-Sensitive language is recursive.

Theorem:
There exists a recursive language that is not Context-Sensitive.

Note:

• There exists a recursive language that is not context-sensitive. This

theorem indicates that linear bounded automata are indeed less
powerful than Turing Machines. Since, they accept only a proper
subset of the recursive languages.
• It follows from the same result that linear bounded automata are
more powerful than Pushdown Automata.

Context-Free Language and Pushdown Automata

Note:

• Context free languages, being generated by context free grammars,

are a subset of the context-sensitive languages.
• ny language accepted by a Pushdown Automata is also accepted by
A

some linear bounded automaton but there are languages accepted
by some linear bounded automata for which there are no Pushdown
Automata.

183
Chapter 4

Previous Years’ Question

Which one of the following language over Σ = {a, b} is NOT context free?
 (GATE (CSE) -2019)
1) {wwR I W∈{a, b}*}
2) {wanbnwR Iw∈{a, b}*, n ≥ O}
3) {wanwRbn Iw∈{a, b}*, n ≥ O}
4) {anbi |i ∈{n, 3n, 5n}, n ≥ O}
Sol: Option 3)

Closure properties of context-sensitive language:

The family of Context-Sensitive languages is closed under
1) Union.
2) Intersection.
3) Complementation.
4) Concatenation
5) Kleene star.
6) Reversal.
7) Inverse Homomorphism.

Note:
The family of context sensitive language is not closed under
Homomorphism.
Context-Free Language and Pushdown Automata

Closure properties of DCFL, CFL and CSL:

Property DCFL CFL CSL

Union No Yes Yes

Intersection No No Yes

Set-difference No No Yes

Complement Yes No Yes

Concatenation No Yes Yes

184
 Chapter 4
Kleene closure No Yes Yes

Homomorphism No Yes No

Reversal No Yes Yes

Substitution (Î-free) No Yes Yes

Inverse homomorphism Yes Yes Yes

Intersection with a regular

Yes Yes Yes
language

Table 4.2 Closure Properties

y Context-free grammar: A grammar G = (V, T, S, P) is said to be context-

free if all productions in P have the form:
A→x
where A ∈ V and x ∈ (VUT)*
y Derivation of string: Left Most derivation and Right Most Derivation.
y A derivation is said to be left most if in each step, the leftmost variable
in the sentential form is replaced.
y A derivation is said to be right most if in each step, the rightmost
variable in the sentential form is replaced.
y Ambiguity in grammar: A Context-Free Grammar G is said to be

Context-Free Language and Pushdown Automata

ambiguous if there exists some w ∈ L(G) that has at least two distinct
derivative trees (parse tree).

Conversion of CFG into simplified context-free grammar:

A safe order is:
i) Eliminate ∈ - productions
ii) Eliminate Unit - productions
iii) Eliminate useless symbol
y Chomsky normal form: A Context-Free Grammar is in Chomsky Normal
Form if every rule is of the form: A → BC (OR) A → a
where A, B, C are in variables and a is any terminal.
y We can convert Context-Free Grammar to Chomsky Normal Form as
well as to Greibach Normal Form.
y Pushdown automata: The automaton which defines the Context-Free
languages is known as Pushdown Automata.

185
Chapter 4

Chapter Summary

y Deterministic and non-deterministic pushdown automata: Non-Deterministic

Pushdown Automata is more powerful than Deterministic Pushdown Automata.
y Closure properties of CFLs: The Context-Free Languages are closed under: 1) Union
2) Concatenation 3) Kleene-Closure 4) Reversal.
y Decision properties of CFLs: Following problems are decidable under CFLs:
Emptiness problem, Finiteness problem, Membership problem
y Context-sensitive languages: Language generated by Context-Sensitive Grammar
is known as Context-Sensitive Languages.
Context-Free Language and Pushdown Automata

186
 5 Turing Machine

Chapter 5
5.1 BASICS OF TURING MACHINE
Introduction:
y A Turing machine is a control unit with a finite number of states and
unbounded tape(s).
y Although, the Turing machine seems to be very simple from the
structural point of view, it is as powerful as simple it looks.
y There are so many problems that are unsolvable by push down
automaton. Such problems are solved using a Turing Machine.
y According to the Turing thesis, the only general type of automaton
whose power almost matches with a computer is nothing but the
Turing machine.

Standard turing machine:

y Turing machine uses the tape as a buffer, in other words, we can say
that it is a temporary storage area.
y There is a read-write head which is a part of the Turing machine, and it
is associated with the tape to read and write one symbol at a time onto
the tape at the time of traversing the tape in the right or left direction.

Fig. 5.1 Diagram of a Turing Machine

If M is a Turing machine, then the definition of M should be

M = (Q, ∑, Γ, δ, q0, B, F)

Where
Q is the set of finite states,
∑ is the set of input alphabets,
Γ is a finite set of symbols called the tape alphabet,
δ is the transition function, defined as
δ: Q × Γ → Q × Γ × {L, R}
where L = left movement & R = right movement,
B ∈ Γ is a special symbol called the blank,
Turing Machine

q0 ∈ Q is the initial state,

F ⊆ Q is the set of final states.

187
Chapter 5

Note: In the definition of a Turing machine, we assume that E Σ ⊆ Γ- {B}, that

the input alphabet is a subset of the tape alphabet, not including the blank.
y The interpretation of the transition function δ on Q × Γ states the
working principle of the Turing machine.
y The present state and the recent tape symbol, which is being read, are
passed as the arguments of the transition function.
y As a result, the control of the Turing machine will move to a new state,
the previous tape symbol may be changed with a new one, and the read
write head will be shifted to the left or to the right.
y The shift or move symbol will decide about the movement of the read
write head after the write of the new symbol in the place of the old one,
whether to shift left or right by one cell.
Note: Turing machine can’t accept epsilon.

Turing machine as acceptor:

SOLVED EXAMPLES

Sol:

Transition diagram
Turing Machine

188
 Chapter 5
The transition means q0 by getting ‘a’; it is replacing ‘a’ with
‘X’ & going to state q1 and read-write head move one cell right.
We can even give transition table for L = anbn/n ≥ 1 as shows below:
δ(q0, a) → (q1, X, R)
δ(q0, Y) → (q3, Y, R)
δ(q1, a) → (q1, a, R)
δ(q1, Y) → (q1, Y, R)
δ(q1, b) → (q2, Y, L)
δ(q2, a) → (q2, a, L)
δ(q2, Y) → (q2, Y, L)
δ(q2, X) → (q0, X, R)
δ(q3, Y) → (q3, Y, R)
δ(q3, B) → (q4, B, L)
If the string will be in language then it will get accepted and halt at state q4
otherwise it will either go dead state or dead configuration.

Note: The transition table and transition diagram both are equivalent in power.

Sol:

Transition diagram
Turing Machine

The transition table for L = {anbncn | n ≥ 1} is given below:

δ(q0, a) → (q1, X, R)

189
Chapter 5

δ(q0, Y) → (q4, Y, R)
δ(q4, Y) → (q4, Y, R)
δ(q4, Z) → (q4, Z, R)
δ(q4, B) → (qf, B, L)
δ(q1, b) → (q2, Y, R)
δ(q1, a) → (q1, a, R)
δ(q1, Y) → (q1, Y, R)
δ(q2, b) → (q2, b, R)
δ(q2, Z) → (q2, Z, R)
δ(q2, c) → (q3, Z, L)
δ(q3, b) → (q3, b, L)
δ(q3, Z) → (q3, Z, L)
δ(q3, Y) → (q3, Y, L)
δ(q3, a) → (q3, a, L)
δ(q3, X) → (q0, X, R)

Transducer:
This is a more general automaton,which is able to produce strings of symbols as output and
it is called a transducer.

Turing machine as transducer:

SOLVED EXAMPLES

Sol:
Turing Machine

190
 Chapter 5
Sol:

Note: Always, the read-write head of Turing machine will point to starting of the input.

Sol: Ex.: 3 + 4 can be represented as input tape as BB00010000BB and the output will
be BB0000000BB.
So, it is the same as a concatenation of two numbers.

Sol: Here, we have three cases:

Case 1:
When a = b, it means that it should halt in a state which will indicate both are
equal.
Case 2:
When a > b, it means that it should halt in a state which will indicate ‘a’ is greater
than b.
Case 3:
When a < b, it means that it should halt in a state which will indicate ‘b’ is
Turing Machine

greater than ‘a’.

191
Chapter 5

Note:

y Turing machine is capable of doing addition and comparison.

y So, if we could do addition and comparison we could do any other mathematical
operation. So, every mathematical function either multiplication, division, logarithm or
exponential can be written in terms of comparison and addition.
y So, Turing machine can implement any mathematical function. Therefore, Turing machine
is mathematical complete.
y Turing machine can compute mathematical function even using any other number system.

Sol:
Turing Machine

192
 Chapter 5
Rack Your Brain

1) For ∑ = {0, 1}, design a Turing machine that accepts the language
denoted by the regular expression 00*.
2) What language is accepted by the Turing machine whose transition
graph is in the figure below?

Main features of standard turing machine:

Apart from all the different descriptions of a Truing machine, the standard
one can be defined as
y As δ defines at most one move always for each configuration, the Turing
machine becomes deterministic by default.
y The definition doesn’t incorporate any specific input or output file.
There is an assumption that- initially, the tape holds some characters.
A specific number of these characters can be treated as an input. In
a similar manner, a definite series of characters belonging to the tape
maybe visualized as the output.

Turing machine as language accepters:

The Turing machine M (Q, ∑, Γ, δ, q0, B, F) will accept the language called
L(M) = {w∈∑+ : q0w x1qfx2 for some qf∈F,x1,x2 ∈Γ*}

Computable:
The necessary condition of Turing computable or computable for a function
with a given domain is, there should be some Turing machine M(Q, ∑, Γ, δ,
q0, B, F) such that,
Turing Machine

q0w qff(w), qf ∈F, for all w ∈ D.

M

193
Chapter 5

Halting problem:
y There are some Turing machines which never halt. It may go into infinite
loop.
Example:

y In a Turing machine, the not halting issue i.e whether the TM is ever
halted or not, which is commonly known as the halting problem.
y This type of problem does not occur either in Finite Automata and
Pushdown Automata because there we have only one move in a forward
direction.
y So, when input gets over, either the FA or PDA will definitely halt, but in
the case of TM it can go either forward or backwards.

Variations of turing machines:

Equivalence of classes of automata:
If two automatons have acceptance for the same language, then they are
called equivalent. For example, suppose there are two automata classes,
C1 and C2 and two automatons M1 and M2. If for every M1 in C1 there is an M2
in C2 such that L(M1) = L(M2) then we can equalize the power of both the
classes. And, if the vice versa is also hold then the automata classes, i.e. C1
and C2 are equivalent.

Turing machines with a stay-option:

y The standard Turing machine definition says that the movement of the
read-write head must be to the left or to the right.
y Another most convenient option provided, is to do nothing or to stay at
the current place even after updating the symbol.
y Hence, the Turing machine with a do-nothing or stay option can be
defined by modifying δ
δ : Q × Γ → Q × Γ × {L,R, S}

S represents do-nothing or no movement of the R/W head.

Turing Machine

y Anyway, this option will not add extra power to the automaton.

194
 Chapter 5
Turing machines with semi-infinite tape:
y The tape is bounded only in one direction.
y Let’s visualize a tape with a left boundary.

Fig. 5.2 Diagram of Turing machine with Semi-Infinite Tape

The off-line turing machine:

y Here, input is given in a separate file, and we are not allowed to modify
the input.
y In case, we have to do some modification on input, then we have to 1st
copy entire input into the tape, and then we have to do modifications
to the tape.
y Even after computation is over, the input is going to remain intact on
the input file.

Fig. 5.3 Diagram of The off-Line Turing Machine

y This modified TM is also equivalent in power to standard TM.

Multitape turing machines:

y More than one tape is there in the case of a multitape Turing machine,
and the most important part is every tape has its dedicated R/W head.
y We define an n-tape machine by M=(Q,∑,Γ,δ,q0,B,F) where Q, ∑, Γ, q0, F
Turing Machine

are the same as standard TM, but where

n
δ : Q × Γn → Q × Γn × {L,R}

195
Chapter 5

Fig. 5.4 Diagram of Multitape Turing Machines

y Multitape turing machine is also equivalent to standard turing machine.

Multidimensional turing machines:

y In such Turning architecture, infinite extension of the tape is allowed in any direction.

Fig. 5.5 A Diagram Of A Two-Dimensional Turing Machine Is Shown Above.

y The transition function δ of a 2D Turing machine can be defined as

δ : Q × Γ → Q × Γ × {L,R,U,D}

where, U represents the up movement of the read-write head and D represents the down
movement.
Turing Machine

y Multidimensional Turing machine is equivalent to the standard Turing machine.

196
 Chapter 5
Jumping turing machine:
y In this jumping TM, instead of moving just one step ahead either to the
left or to the right, it can move many steps in one go.
y Here, the δ is given below

δ : Q × Γ → Q × Γ × {L,R} × {n}

↑
Here, ‘n’ number of steps.
y This jumping TM is also equivalent in power to standard TM.

Non erasing turing machine:

y In non-erasing TM, on the input symbol, we are not allowed to write
Blank(B) but we can write any other symbol.
y This non-erasing TM is also equivalent in power to standard TM.

Always writing TM:

y In always writing Turing machine, it is always needed to
modify the input with different symbols whenever the Turing
Machine sees any input. Turing Machine cannot leave it as it is.
Example: if TM get ‘a’ as input, then it will write something which is not ‘a’.
y This Turing machine is also equivalent to standard TM.

Multihead TM:
y This modified TM have more than 1 read-write head.
y Multiple heads simultaneously look after the scanned symbol and make
the needful, i.e. move or write onto the tape independently.
y A Single head Turing machine can simulate a multi head Turing machine.

Automata with a queue:

y If there are finite Automata, and if we are adding a queue, then it is
equivalent to standard TM.

Turing machine with only 3 states:

y Any Turing machine can be minimized to a Turing machine which has
only 3 states.
y If a Turing machine has only three states, then it is also equivalent to a
standard Turing machine.
Turing Machine

197
Chapter 5

Multitape TM with stay option and atmost 2 states:

y Any Turing machine can be as multitape TM with stay option and almost
2 states.
y This modified TM also have the same power as standard TM.

Non deterministic turing machine:

y A non deterministic Turing machine is an automaton is defined by
M
= (Q, Σ, Γ, δ, q0 ,B,F)

Where
Q = finite set of internal states
∑ = finite set of input alphabets
Γ = Finite set of symbols or tape alphabets
δ = the transition function

δ : Q × Γ → 2QxΓ×{L,R}

B = blank space (special symbol) from tape symbol.

q0 = initial state ∈ Q
F = Set of final states ⊆ Q
y In a non-deterministic machine, the range of δ is a set of all possible
paths, so the machine can take any path out of all possible paths.
y The deterministic Turing machines classes are equivalent to the non
deterministic Turing machines classes.
y If at least one configuration of a non deterministic Turing machine
accepts a string w belongs to L then that language L is said to be
accepted by the same Turing Machine.
y “A non deterministic Turing machine M is said to decide a language L if,
for all w ∈ ∑*, There is a path that leads either to the acceptance or
rejection.”

Note: A NPDA with one extra independent stack. The δ is given below:-
δ: Q × (U{∈}) × Γ × Γ 2Q×Γ*×Γ*
This is also equivalent to standard TM.

Multistack machines:
y The tapes of a multi tape Turing machine in such a way, that it starts
behaving like a stack.
y A one-stack machine is a DPDA, while a machine with two stacks is a
Turing Machine

Turing Machine.

198
 Chapter 5
Grey Matter Alert!

Simulating a Turing Machine by a real computer

y It is possible, in principle, to simulate a TM by a real computer if we accept that
there is a potentially infinite supply of a removable storage device such as a disk,
to simulate the non-blank will be better portion of the TM tape.
y Since the physical resources to make disks are not infinite, this argument is
questionable.
y However, since the limits on how much storage exists in the universe are unknown
and undoubtedly vast, the assumption of an infinite resource, as in the TM tape,
is realistic in practice and generally accepted.

Simulating a computer by a turing machine:

y A Turing Machine can simulate the storage and control of a real computer
if it uses one tape to store all the locations and their contents registers,
main memory, disk and other storage devices.
y Thus, we can surely say that something that cannot be done by a TM
also cannot be done by a real computer.

Rack Your Brain

Consider the nondeterministic Turing machine

M = ({qo, q1, q2, qf}, {O, 1}, {O, 1, B}, d, qo, B, {qf})
Informally but clearly describe the language L(M) if 8 consists of the
following sets of rules:
d(q0, O) = {(q0, 1, R), (q1, 1, R)}
d(q1, 1) = {(q2, 0, L)}
d(q2, 1) = {(q0, 1, R)}
d(q1, B) = {(qf, B, R)}

Universal turing machine:

y In a universal Turing machine Mu, a standard Turing machine(M) will
be given as input along with an input string w. We can simulate the
computation of M on w.
y To give a standard Turing machine as an input, first, a standard
representation of a Turing machine is required.
Turing Machine

y Assume Q = {q1, q2,......,qn}

y where, q1 = initial state, q2 = single final state, and

199
Chapter 5

Γ = {a , a ,......,a },
1 2 m

Where, a1 represents the blank symbol.

y Suppose, there is an encoding where q1 can be represented as 1, q2 can
be represented as 11 and so on.
y Similarly, the tape input symbols can be encoded as a1 = 1, a2 = 11, and
so on.
y To separate the 1’s or the strings of 1’s can be distinguished using 0 as
a symbol.
y Any Turing machine can be defined by the transition function δ along
with the initial, final state and the blank symbol defined.
y “The transition function is encoded according to this scheme, with the
arguments and result in some prescribed sequence”. For example, δ
(q1,a2) = (q2,a3,L) might appear as
…10110110111010…….

Fig. 5.6

Note:
y It follows from this that any turing machine has a finite encoding as
a string on {0,1}+ and that, given any encoding of M, we can decode it
uniquely.
y But any combination of strings will not represent any Turing machine
(e.g. the string 00011).
Turing Machine

200
 Chapter 5
Working procedure of universal turing machine:
y The encoded definition of M will be kept in the tape 1, given an input M
and w.
y The tape symbols of M will be placed in the tape 2 and tape 3 will
contain the states of M.
y The universal Turing machine identifies the configuration of M by looking
at the tape 2 and tape 3.
y The tape 1 will help for the transition by seeing tape 2 and tape 3.
y Finally, the changes will be reflected on the tape 2 and tape 3, the
results will be reflected in tape 2.
y As it can be implemented using any programming language, we can
implement the same using any standard Turing machine also.

Previous Years’ Question

A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting
state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}.
The symbol B is the blank symbol used to indicate end of an input string. The transition
function of M is described in the following table. (GATE-2003)

The table is interpreted as illustrated below.

The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1
on the current page square, then it writes 1 on the same tape square, moves its tape
head one position to the right and transitions to state q1.
Which of the following statements is true about M?
1) M does not halt on any string in (0 + 1)+
2) M does not halt on any string in (00 + 1)*
3) M halts on all strings ending in a 0.
4) M halts on all strings ending in a 1.
Sol: Option 1)
Turing Machine

201
Chapter 5

Note:
y FA + tape = FA + 2stack = FA + queue = TM
y TM = FA+ 2 stack
  = FA +3 stack
  = FA + 4 stack
.
.
.
  = FA+ n stack (n ≥ 2)

Recursively enumerable:
y To ensure a language L is recursively enumerable, we have to find a
Turing machine for it.
y Recursive Enumerable can be defined as a Turing machine M, where, for
every w ∈ L,
q0w |-*M x1 qf x2,
with qf a final state.
y If string w is not in the language, then the definition doesn’t say whether
it will go in a non-final state and halt or it may go into an infinite loop.

Fig. 5.7

Recursive language:
1) A formal language for which a standard Turing machine exists, i.e., any
Turing Machine

strings from that language will be accepted by the Turing machine and
the machine halts as well is called recursive language.

202
 Chapter 5
2) “The Turing machine that always halt is called Halting TM/decider/Total
Turing machine.”

Fig. 5.8

Conclusion

Fig. 5.9

“Recursive Language is a subset of recursively enumerable language”.

Turing Machine

203
Chapter 5

Chomsky hierarchy:
1) All formal languages are divided into 4 classes by Chomsky and those
class hierarchy known as “Chomsky Hierarchy”.

Fig. 5.10

2) Actually Type 0 represents recursively enumerable language, type 1

represents context-sensitive language, type 2 represents context free
language and type 3 represents regular language.

Note:
Recursive language is not type (0) language. Only recursively enumerable
language is type (0) language.
Turing Machine

204
 Chapter 5
Extended Version of Chomsky Hierarchy:

Fig. 5.11

Language and their corresponding grammar:

Turing Machine

Fig. 5.12

205
Chapter 5

Theorem 1:
“If a language L and its complement L are both recursively enumerable
then both languages are recursive.”

Theorem 2:
“If L is recursive, then L is also recursive and consequently both are
recursively enumerable.”

Unrestricted grammar/type 0 grammar:

When all the productions in a grammar are of the form X → Y
where X ∈(V + T)+ and Y ∈ (V + T)*
[Here, V indicate set of variables and ‘T’ indicate set of terminals]
y Unrestricted grammar can be defined ‘∈’ but TM is not configured in
order to accept a ‘∈’ string. So, we assume that we don’t consider
language deriving ‘∈’.

Ex.: S → S1B
S1 → aS1b
bB → bbB
aS1B → aa
B→∈
Closure properties of Recursive and Recursive Enumerable Language
Turing Machine

206
 Chapter 5
l

Table 5.1 Cosure Properties

Theorem 1:
“For all recursive language ‘L’ there is an enumeration technique for it.”
Proof:
m
Turing Machine

Fig. 5.13

207
Chapter 5

~
If the alphabet is {a, b} then M enumerate strings as follows:
‘a’
‘b’
‘aa’
‘ab’
‘ba’
‘bb’
‘aaa’
‘aab’
…

Enumeration Procedure
Repeat:
~
M generates a string w
M checks if w ∈ L
Yes: Print w to output
No: Ignore w
End of proof.

Example: L = {b, ab, bb, aaa, …}

~
M L(M) Enumeration Output

b b b

aa

ab ab ab

ba

bb bb bb

aaa aaa aaa

Turing Machine

aab

208
 Chapter 5
Note:
Theorem 2:
“A language is recursively enumerable if and only if there is an enumeration
procedure for it.”

Previous Years’ Question

Define languages L0 and L1 as follows: (GATE-2003)

L0 = {<M, w, 0> | M halts on w}
L1 = {<M, w, 1> | M does not halts on w}
Here <M, w, i> is a triplet, whose first component M is an encoding of a Turing
Machine, second component w is a string, and third component i is a bit.
Let L = L0 U L1. Which of the following is true?
1) L is recursively enumerable, but L′ is not.
2) L′ is recursively enumerable, but L is not.
3) Both L and L′ are recursive.
4) Neither L and L′ is recursively enumerable.
Sol: Option 4)

Previous Years’ Question

Consider the following languages. (GATE-2016 (set 2))

y L1 = {<M> | M takes at least 2016 steps on some input},
y L2 = {<M> | M takes at least 2016 steps on all inputs} and
y L3 = {<M> | M accepts ∈},
where for each Turing machine M, <M> denotes a specific encoding of M.
Which one of the following is TRUE?
1) L1 is recursive and L2, L3 are not recursive
2) L2 is recursive and L1, L3 are not recursive
3) L1, L2 are recursive and L3 is not recursive
4) L1, L2, L3 are recursive
Sol: Option 3)

Linear bound automata:

y We can limit the power of a Turing machine by restricting the way in
which we are going to use tape.
Turing Machine

y If we limit the Non-deterministic TM in such a way that it can use the

tape like a stack then it converges to a PDA.

209
Chapter 5

y If we limit the Turing machine to use only finite amount of cell and only
unidirectional tape movement is allowed then it can converges into
finite automata.
y If we limit tape of Turing machine to use only that part of the tape
where the input is present and not beyond it, then it converge to LBA
(Linear Bounded Automata).
y A linear bounded automata is designed with an unbounded tape. It
extents up to which the tape needs to be made use of purposely, with
an instant of the input. Practically, the unbounded tape is restricted by
the input string.
y To enforce this, we can envision the input as bracketed by the two
special symbols, the left-end marker and the right-end marker.
y LBA is less powerful than TM and it is more powerful than PDA. Ex.:
anbncn | n ³ 1 is accepted by LBA but not by PDA.
y Here, we don’t know whether the deterministic LBA are equivalent in
power to non-deterministic LBA. It is undecidable.
y Complement of the CFL is CSL.
y Language accepted by LBA is called context sensitive language.
y LBA is halting, Turing machine as context sensitive language is also a
recursive language.

Countability

y Countable set definition: “A set ‘s’ is said to be countable, if the

elements of the set can be put in one to one correspondence with the
set of natural numbers.”
y By this we mean that the elements of the set can be written in some order,
say, x1, x2, x3, …, so that every element of the set has some finite index.
for ex.: E = set of even number = {0, 2, 4, 6, 8…}
For any element in E of form 2i (i starts with 0) we give a corresponding
element (i + 1) in N (Natural Number). So, for every element in even number
set we can associate a natural number as a correspondence. Therefore, we
can say that set of even number is countable.
eg.: O = set of odd number
= {1, 3, 5, 7, 9, 11, …}
Turing Machine

Here, we can represent set of odd number in terms of (2i + 1) (i ³ 0). We

can map every odd number of the form (2i + 1) with (i + 1) (Natural number).

210
 Chapter 5
Hence, the set of odd number is countable.
Uncountable set definition: “A set is uncountable if it is infinite and not
countable.”

Rack Your Brain

Given R = set of real number. Is R countable set?

Alternative definition of countability:

y A set is said to be countable if there exists an enumeration method
using which all the elements of the set can be generated and for any
particular element, it takes only a finite number of steps to generate it.
y The finite number of steps taken to generate an element can be used
as its index and hence a mapping into a natural number set.
for ex.:
i) Set of even number
Enumeration procedure: for (q = 0 to ¥)
printf (2 × q);

Output : 0 2 4 6 8 ...
Steps : 1 2 3 4 5 ...

So, the index for (0, 2, 4, 6, 8, … ) is (1, 2, 3, 4, 5, …).

Hence, set of even number is countable.
Similarly;
ii) Set of odd number
for (q = 0 to ¥)
printf (2 × q + 1)

Output : 1 3 5 7 9 11 ...
Steps : 1 2 3 4 5 6
Turing Machine

211
Chapter 5

SOLVED EXAMPLES

Sol: T he set S is countable since we are having an enumeration procedure for set S.
 ere, we don’t go either in increasing order of numerator or denominator, we just
H
add numerator and denominator and we just go in the increasing order of sum.
Here, the smallest number is 1/1.
So, the 1st sum is 2.
Within the sum we can enumerate in increasing order.
1 1 2 1 2 3
So, the enumeration order is , , , , , , ...
1 2 1 3 2 1
Hence, it is countable.

Lexicographic ordering:
y Lexicographic ordering is nothing but the alphabetical order, i.e., the sequence of letters
present in the dictionary.
y Suppose we have a set S = {a, b} and S* in lexicographical order will be {∈, a, b, aa, ab,
ba, bb, aaa, aab, …}

Rack Your Brain

Given a set S = set of all string over {a, b} is

1) Countable
2) Uncountable
3) Finite
4) Neither countable nor uncountable

Note:
y Set of all string possible over any alphabet is countable.
y So, Σ* = set of all string over Σ is countable.
y Every subset of countable set is either finite or countable.
y Since every language is a subset of Σ*. Therefore, every language is countable.
y It means given any language it is definitely either countable language or finite language.
Turing Machine

212
 Chapter 5
Sol: Since every Turing machine can be encoded as a string of 0’s and 1’s.
Let S = {0, 1} then S* = set of all strings over {0, 1}.
Since, S* is countable and T is subset of S*.
Hence, T = set of all Turing machines.

Implication of the fact that the set of all turing machines are countable:
y Since we know that the set of Turing machines are countable, then the set of recursively
enumerable language are also countable.
y Since the set of recursive language is subset of the set of recursively enumerable
language. Hence, a set of recursive languages is countable.
y Similarly, a set of context free language, a set of context sensitive language, and the set
of regular language are also countable.
y We can also modify a turing machine in such a way that it can act as
PDA. Therefore, if set of TM is countable it implies that the set of PDA is also countable.
y Since, all machines are subset of set of Turing machine. So, the set of LBA, and set of
FA are also countable.

Theorem: Set of all languages possible are uncountable.

Implication from theorem:
y Set of TM is countable, and the set of all languages possible is
uncountable.
y Therefore, there are some languages for which there are no machines
yet. It means there are some languages which are not even recursively
enumerable.

Turing Machine

Fig. 5.14

213
Chapter 5

Theorem:
“set of all languages are uncountable”.

Proof:
Suppose there is a set S = {a, b}.
We need to prove that, 2S* is uncountable.
Let us assume, 2S* is countable.
As, S = {a, b}
S* = {∈, a, b, aa, ab, ba, bb, aaa, aab,....}

Let us represent each string using 0 or 1, if the string is present in the

language ∈ 2S* then mark that string using ‘1’ otherwise ‘0’.

Now, if we consider the diagonal, then we will find a string S = 0 0 1 1 1 ......

Complement of the diagonal 00111... will be S’ = 1 1 0 0 0..... which is not
in the language.
This particular language S is not included in that list as it is a different
form all the languages by at least one string.
So, our assumption was incorrect.
Hence, 2S* is uncountable. (Proved)

Note:
This kind of argument, because it involves a manipulation of the diagonal
elements of a table is called diagonalization.
Turing Machine

214
 Chapter 5
Note:
Theorem:
“There exists a recursively enumerable language whose complement is not
recursively enumerable.”
Theorem:
“There exists a recursively enumerable language that is not recursive i.e., the
family of recursive languages is a proper subset of the family of recursively
enumerable languages.”
y Diagonalization method is used to prove that a language is not
recursively enumerable because if for a language, we proved that it
is not countable then it means there is no enumeration procedure for
that language.
And theorem says that a language is Recursive Enumerable Language if
and only if there is enumeration procedure for it. Hence, that language
is not recursively enumerable.
Theorem:
“If S1 and S2 are countable sets, then S1 U S2 and S1 × S2 are countable and
union and cross-product can be extended to any number of finite sets.”
Theorem:
“The set of all languages that are not recursively enumerable is uncountable.”

Proof:
The set of all languages is 2S* (set of all subsets of S*), and out of that some
languages are already recursive enumerable, because if there is TM for a
language then that language is recursively enumerable and we already know
that the number of TM is countable. Therefore, the number of languages in
the total language which is recursively enumerable are countable and that
will be equal to a number of Turing machines.
And in the remaining set, we don’t know anything, so we are just assuming
that it is countable. So, the resulting set is the union of a countable set;
therefore overall, that should be countable. And if that is true, then our
*
initial proof that 2Σ is uncountable is a failure as we know that set of
*
all languages 2Σ is uncountable. Therefore, our assumption that, the
remaining language i.e., the set of all languages that are not- recursively
enumerable is countable, is false. So, set of all languages which are not
recursively enumerable, must be uncountable.
Turing Machine

215
Chapter 5

Previous Years’ Question

Consider the following sets:

S1: Set of all recursively enumerable languages over the alphabet {O, 1}
S2: Set of all syntactically valid C programs
S3: Set of all language over the alphabet {O. 1}
S4: Set of all non-regular languages over the alphabet {O, 1)}
Which of the above sets are uncountable? (GATE-2019)
1) S1 and S2
2) S3 and S4
3) S2 and S3
4) S1 and S4

Previous Years’ Question

Let N be the set of natural numbers. Consider the following sets,

P: Set of Rational numbers (positive and negative) (GATE-2018)
Q: Set of functions from {O, 1} to N
R: Set of functions from N to {O, 1}
S: Set of finite subset of N
Which of the above set are countable?
1) Q and S only
2) P and S only
3) P and R only
4) P, Q and S only
Turing Machine

216
 Chapter 5
Grey Matter Alert!

Function

y A function is a rule that assigns to elements of one set a unique element of

another set.
OR
In mathematics, a function is a relation between sets, that associates every
element of a first set with exactly one element of the second set.
Ex.: X = {1, 2, 3} & Y = {A, B, C, D}
t = {(1, D), (2, C), (3, C)}

y If f denotes a function, then the first set is called the domain of f and the second
set is its range. We write
f : S1 → S2
to indicate that the domain of f is a subset of S1 and that the range of f is a subset
of S2.
y If the domain of f is all of S1, we say that f is a total function on S1, otherwise f is
said to be a partial function.

Turing Machine

217
Chapter 5

SOLVED EXAMPLES

Sol: 1) Explanation: It is accepting L = {a b

n n
| n ³ 1}. So, (1) is the correct option.

Sol: 1) E xplanation: It is a CSL because we can give a linear bound automata. We cannot
compare number of X’s and number of Y’s using one stack here.
Turing Machine

218
 Chapter 5
Sol: 2) E xplanation: Statement S1 is incorrect because set of all irrational number are
uncountable.
Statement S2: Since L is finite language. So, it is regular. All regular language
are recursively enumerable language and recursively enumerable language are
closed under Kleene closure. Hence, L* is recursively enumerable language.

Sol: 3) Explanation:
S1 : L2 − L1 =
L2  L1
= REL  Rec L
= REL  Rec L
= RE L.
So, statement S1 is correct.
S2 : L = {wwwk | w∈ (a, b)+} is CSL because for this we can give a LBA.
It needs more than one stack to accept this language L, so it is CSL.
Turing Machine

219
Chapter 5

Sol: 1) E xplanation: Recursive language is closed under complementation. Hence, L1

is
also recursive language. Recursively enumerable language is not closed under
complementation. Hence, L2 may or may not recursively enumerable language.

So, we can’t say L2 is recursively enumerable language.

Sol: 3) Explanation:
L = (L2  L1 ) − L3
= (Rec L  REL) − CFL
= (Rec L ∩ REL) – CFL
= REL  (CFL)
= REL ∩ CSL = REL.
[Here, Rec L means recursive language,
REL means recursively enumerable language,
CFL means context free language,
Turing Machine

CSL means context sensitive language]

220
 Chapter 5
Sol: 1) Explanation: The given grammar is in the form of u → v
where u belongs to (V+T)+ v belongs to (V+T)*
here, V is set of non-terminals and T is set of terminals
Hence, it is unrestricted grammar or type-0 grammar.

Sol: 1) E xplanation:
Recursively enumerable language is not closed under
“complementation” and it is closed under “union”, “intersection”, “concatenation”,
etc.

Sol: 1) E xplanation: In the definition of Turing machine, ‘Q’ represents the “Set of finite
number of states”. Turing Machine

221
Chapter 5

Chapter Summary

y A Turing machine M is defined by M = (Q, S, G, d, q0, B, F) where Q is the set of

internal states, S is the input alphabets, G is a finite set of symbols called the tape
alphabet, d is the transition function, defined as
d: {Q × G → Q × G × {L, R}} where L = left and R = right, B ∈ G is a special symbol
called the blank, q0 ∈ Q is the initial state, F ⊆ Q is the set of final states.
y Turing machine can’t accept epsilon.
y Turing machine can act both as a transducer as well as acceptor.
y Turing machine is mathematically complete. It can do any mathematical function.
y Halting Problem: Some times Turing machine goes into an infinite loop. This
problem of not halting of Turing machine is called the halting problem in the Turing
machine.
y There are different variations of Turing machines as shown below:
i) Turing machine with a stay option.
ii) Turing machine with semi-infinite tape.
iii) The off-line Turing machines.
iv) Multitape Turing machines.
v) Multidimensional Turing machines
vi) Jumping Turing machine
vii) Non Erasing Turing machine
viii) Always writing Turing Machine
ix) Multi head Turing Machine
x) Turing machine with only 3 states.
xi) Multitape Turing Machine with stay option and at most 2 states.
xii) Non-deterministic Turing machine
All these variations of the Turing machines are equivalent in power to the standard
Turing machines.
y We can represent any Turing machine in terms of 0’s and 1’s but any combination
of 0’s and 1’s is not a Turing machine.
y Finite Automata + n stack (n ³ 2) = TM
y Finite automata + queue = TM.
y Recursively Enumerable Language: For a language L, if there is a Turing machine
that can accept L, then the language L is known as recursively enumerable.
y Halting TM: Turing machine that always halts is called Halting TM/decider/Total
Turing machine.
y Chomsky Hierarchy: All formal languages are divided into 4 classes by Chomsky
Turing Machine

and those class hierarchy known as “Chomsky Hierarchy”.

222
y Unrestricted Grammar/Type 0 Grammar: A grammar is called unrestricted if all Chapter 5
the productions are of the form X → Y
y where X is in (V + T)+ and Y is in (V + T)*
[Here, V indicates set of variables and T indicates set of terminals]
y Closure Property of Recursive and Recursively Enumerable Language
Turing Machine

223
Chapter 5

y Linear Bound Automata: If we limit the tape of the Turing machine to use only
where the input is present and not beyond it, then it converges to LBA.
y In LBA, whether deterministic LBA is equivalent to non-deterministic LBA is not
known.
y Language accepted by LBA is called context-sensitive language.
y Countable Set: If there persists a one-to-one mapping from the elements of a set
to the set of positive integers, such a set is classified as countable.
y Uncountable Set: A set S is uncountable if it is infinite and not countable.
Turing Machine

y Set of all strings possible over any alphabet is countable.

224
 Chapter 5
y Set of all languages possible is uncountable.
y There exists a recursively enumerable language whose complement is not
recursively enumerable.
y There exists a recursively enumerable language that is not recursive i.e., the family
of recursive language is a proper subset of the family of recursively enumerable
language.
y If S1 and S2 are countable sets, then S1 U S2 and S1 × S2 are countable, and union
and cross-product can be extended to any number of finite sets.
y The set of all languages that are not recursively enumerable is uncountable.

Turing Machine

225
 6 Decidability

Chapter 6
What is a decision problem:
A decision problem is a set of related statements, each of which must be
either true or false.
For example:
“For context-free grammar (G), the language L(G) is ambiguous or not?
For some context-free grammar (G), this is true, and for some, it is false.
But we can clearly say that the statement is either true or false.
Basically, we have two kinds of problems:

Fig. 6.1 Decidability

Note:
y For decidable problem, the Halting Turing Machine (HTM) exist.
y For undecidable problem\s, the Halting Turing Machine (HTM) does
not exist, but Turing Machine (TM) may or may not exist.
y If a problem is not recursive enumerable (RE), then no Turing Machine
exists for that problem.

Language:
The set of all strings that can be generated from the grammar.
Language can be finite or infinite. If a language consists of a finite number
Decidability

227
Chapter 6

of strings, then it is called a Finite Language; otherwise, we can say it is an

infinite language.

Fig. 6.2

Example:
Consider a String w and a language L
1) If

For both the cases, we have logic, then the language is decidable.

2) If

Logic exists for valid strings. So, the language is Recursively Enumerable
but not Recursive.

3) If

For both the cases, we do not have logic, then the language is not
Recursively Enumerable.
Encoding a turing machine (TM):
Each Turing Machine with input alphabet {0, 1} may be thought of as a
binary string.
To represent a Turing Machine (M)= (Q, Σ, Γ, δ, q,B,F) as a binary string where
Decidability

Σ ={0, 1} .

228
 Chapter 6
First, assign integer to the tape symbols, states and directions Left (L) and Right (R).
Let the states be: q1, q2, q3, q4 …qk.
Here q1 is a Starting state, q2 is a Final State and q3, q4 … qk are other states.
Let tape symbols are: X1, X2, X3, …Xm.
X1 = 0
X2 = 1
X3 = B (Blank)
Let the direction left be D1 and the direction Right be D2.

Encoding of transition function ( δ ):

one transition rule is,

δ(qi , X j ) =
(qk , Xl ,Dm ) for some integers i, j, k, l and m.
Now, code this rule by the string- 0i10j10k10l10m
where i, j, k, l, m should be greater than 0 (i, j, k, l, m > 0).
There should not be two consecutive 1’s within the code for a single transition.
The code for the entire Turing Machine will be:
Q1 11 Q2 11 Q3 11 … Qn
Each transition is separated by two consecutive 1’s and Q1,Q2…Qn are the transition of Turing
Machine.

Example:
Consider the Turing Machine (TM)
M = ({q1, q2, q3, q4, q5}, {0, 1}, {0, 1, B}, δ , q0, B, {q2})
where δ consists of the rules:
δ(q1 ,B) =
(q5 ,B,L)

δ(q4 , 1) =
(q3 ,B,R)

δ(q5 ,B) =
(q4 , 1,R)

δ(q3 , 1) =
(q2 , 1,L)

Codes for each transition:

(qi, Xj, qk, Xi, Dm)

1)δ(q1 ,B) = (q5 ,B,L)

(q1, X3, q5, X3, D1)
So,
01103105103101
01000100000100010
Decidability

229
Chapter 6

2) δ(q4 , 1) = (q3 ,B,R)

(q4, X2, q3, X3, D2)
So,
04102103103102
000010010001000100
3) δ(q5 ,B) = (q4 , 1,R)
(q5, X3, q4, X2, D2)
So,
05103104102102
00000100010000100100

4) δ(q3 , 1) = (q2 , 1,L)

(q3, X2, q2, X2, D1)
So,
03102102102101
00010010010010
A code for Turing Machine (M):
01000100000100010110000100100010001001100000100010000100100110
0010010010010
Here, two consecutive 1’s are used as Separators.

The diagonalization language (ld):

It is the set of strings (wi) such that wi is not in L(Mi).

Ld = {w ∈ (0 + 1)
i
+
}
| wi ∉ L(Mi )

Let,
∑ ={a,b}
*
And we know, ∑* is countable; now we must prove 2∑ is uncountable.

Prove by contradiction:
*
Let 2∑ is countable and it has one-one mapping.
We know,
Σ* =∈, a,b, aa, ab,ba,bb, aaa 
Let,

L1 = {∈, a}
L2 = {a,b}

= {∈, a, aa}
Decidability

L3

230
 Chapter 6
L4 = {b, ab,ba}

L5 = {aa,ba,bb}

L6 = {∈, aaa} and so on.

Now, mapping L1, L2, L3, L4, L5 and L6 with ∑* .

Fig. 6.3 The Table That Represents M Accepts W

To construct Diagonal Language (Ld), we complement the diagonal.

Complement of diagonal would begin:
0 0 1 1 1 1…
∈ a b aa ab ba…
Thus, Ld would contain wi = {b, aa, ab, ba…} except ‘ ∈ ’ and ‘a’.
Since Ld is not present in Diagonal Matrix or given set of languages. So, the initial assumption
was wrong.
*
By contradiction, 2∑ is uncountable.

Proof that Ld is not Recursively Enumerable (RE):

By the above intuition, there is no Turing Machine that accepts the language Ld. So, Ld is not
Decidability

Recursive Enumerable (RE).

231
Chapter 6

An undecidable problem that is recursively enumerable (RE):

It has been already established that diagonal languages are not recognized
by Turing machines.
Let’s have insight into the area of recursively enumerable languages.

Case 1:
A Turing machine will necessarily halt for strings that are not inclusive to a
given language. However, it may or may not enter into an accepting state.

Case 2:
Let us consider a scenario where recursively enumerable languages are
involved. The Turing machine will necessarily halt if the input string is
inclusive to the language. However, for excluded input strings, the Turing
machine may get inter-wined into an infinite loop or halt.

Recursive languages:
A recursive language L If L = L(M) for some Turing Machine (M) such that:
1) w ∈ L ⇒ Halts and accepts
2) w ∉ L ⇒ Halts and rejects

Note:
Recursive language is always decidable. If language is not recursive, then
it is undecidable/semi decidable.

Compliment of recursive and recursive enumerable language (RE):

If a language L is Recursive Enumerable but the complement of recursive
enumerable language (L) is not Recursive Enumerable (RE), then we can
say L can not be Recursive.
()
If L is Recursive, then the complement of L L would also be recursive,
which implies L is Recursive Enumerable(RE).
Decidability

232
 Chapter 6
Fig. 6.4 Relationship between recursive and RE and not RE languages

Note:
The Recursive languages are closed under complement.

If L is language that is Recursive, so complement of L ( L ) is also recursive:

Proof:
Let,
L = L(M) for some Turing Machine (M) that always halts. Now, we will
construct another Turing Machine (M1) such that:
L = L(M1 )
where M1 behaves just like M, we will have to modify M to create M1:
1) All accepting states of M are changed as non-accepting states of M1
with no transition. It means M1 will halt without accepting.
2) M1 has a new accepting state R; there is no transition from R.
3) For each combination of a non-accepting state of the Turing Machine (M)
and a tape symbol of M such that M has no transition, add transitions to
R.

M is guaranteed to halt. So, we can say M1 will also halt. M1 accept only
those strings that M will never accept.

So, M1 accepts the

Decidability

233
Chapter 6

complement of L (L ) .

Fig. 6.5 Construction Of A Tm Accepting The Compliment Of Recursive Language.

If both the language L and its complement are Recursive Enumerable (RE),
then language L is Recursive.
Proof as consider:
M1 and M2 are Turing Machines which are simulated in parallel by a Turing
Machine (M).
Let,
L = L(M1) and L = L(M2 )

Fig. 6.6 Construction Of A Turing Maschine Accepting

A Compliment Of A Recurisve Language

We can make Turing Machine (M) a two-tape Turing Machine and then it is
converted into a single tape Turing Machine for simplicity.
Tape one of the Turing machines (M) simulate the tape of M1, while tape two
of the Turing machine (M) simulate the tape of M2.
If
Input w ∈ L(M) → M1 will accept → M accepts and halts

Input w ∉ L(M) → L → M2 will accept → M halts without accepting

Thus, for all inputs, M halts, and L(M) is the same as L. Since M always halts, and
L(M) = L. So, we can say that L is Recursive.
Decidability

234
 Chapter 6
Turing machine halting problem:
“Does a Turing Machine (M) halt on input w?”
OR
“Is w ∈ L(M)?”
We know that Turing Machine has three possibilities.

If w ∈ L(M). So, it will halt on accepting states.

If w ∉ L(M). So, it may halt on the non-final state, or it can get into an
infinite loop.
Halt: The program/algorithm on certain input will halt on accepting state
or halt on the non-final state, but it would never go into an infinite loop.
“Can we design an algorithm that tells whether the given program will halt
or not?”
“The Answer will be NO”. Because we cannot design any generalized
algorithm which can surely say that a given program will halt or not.”
Only a single way we have, just run the program and check whether it will
halt or not.
So,
“Halting problem is an undecidable problem because we cannot have
any algorithm that tells whether the given program will halt or not in a
generalized way.”
Table for decidable and undecidable problems:

Problems FA DPDA PDA LBA/HTM TM

Halting D D D D UD
Membership D D D D UD
Emptiness D D D UD UD
Finiteness D D D UD UD
Totality D D UD UD UD
Equivalence D D UD UD UD
Disjoint D UD UD UD UD
Set containment D UD UD UD UD
Table 6.1
Decidability

D ⇒ Decidable
UD ⇒ Undecidable

235
Chapter 6

Note:
y For Regular Languages, all the given problems are decidable.
y For Recursive Enumerable Language (REL), all given problems are
undecidable.

Rice theorem part-I:

• Any non-trivial property of Recursively Enumerable Language (REL) is
undecidable.
• It is a negativity test. It does not prove if the language is Recursive or
Recursive Enumerable.
• It Proves If a language is not recursive, it may or may not be recursively
enumerable.

Definitions

Property : A property of language is simply a set of languages. We say ‘L’ satisfies

the property ‘P’ is L ∈ P .

Examples:
• {<M>|M has 15 states}
This is a Property of Recursive Enumerable Language (REL) but not a
language.
• {<M>|L(M) is infinite}
• {<M>|L(M) is regular.}

Trivial and non-trivial properties:

We know that set of all Turing Machines a (string of 0’s and 1’s) are countably
infinite.
∴ Recursive Enumerable (RE) set is countably infinite like Recursive
Enumerable Language (REL) set (RE1, RE2, RE3, …}

Trivial property:
A property is trivial if it is satisfied by all Recursive Enumerable Languages
or it is not satisfied by any Recursive Enumerable Language (REL).
• If all the elements of the Recursive Enumerable Language (REL) set have
the property → Trivial property
Decidability

236
 Chapter 6
• If all the elements of the Recursive Enumerable Language (REL) set do
not have the property → Trivial property

Non-trivial property:
A property is non-trivial if it is satisfied by some Recursive Enumerable
Languages (REL) and are not satisfied by others.
• If at least one Recursive enumerable language (REi) has the property and
one Recursive enumerable language (REi) does not have the property,
then the property is said to be non-trivial.

Example:

L = {<M> | L(M) is infinite}

Here, ‘M’ is the arbitrary Turing Machine Code which acts as an input to the
Universal Turing Machine (UTM).
Let’s find a Recursive Enumerable Language (RE) that has the property:
{L(REi) is infinite}
REi _Yes = {1, 11, 111, …}.

Turing Machine accepts languages:

=L {W | W ∈ 1 *}
Let’s find a REj that does not have the property:
{L(REj) is finite}
REj_NO = {1},
Turing Machine accepts language,

=L {W | W ∈ 1}
∴ Hence, we can find REi_YES (REi that has the property) and REi_NO(REi
that does not have the property).
Hence, it is a Non-Trivial property of Recursively Enumerable Language. So,
by Rice Theorem, we can say that the language is undecidable.

Rice theorem part-II:

Any Non-Monotonic property of Recursively Enumerable Language is not
Decidability

even semi-decidable.

237
Chapter 6

Note:

y Recursive ⇒ Decidable
y Semi decidable ⇒ Recursive Enumerable but not REC.

This theorem is used for proving if the language is not semi-decidable (Not
Recursive Enumerable).
Let’s discuss the non-monotonic properties.
A property of recursively enumerable language is non-monotonic if any set
(REi) having the property is PROPER SUBSET of any set (REj) that does not
have the property.

Example:

where <M> is the arbitrary Turing Machine code.

Language of the Universal Turing Machine (UTM) can be defined as:
L(Universal Turing Machine) = {M | L(M) has at most 10 strings}
Let’s see
If we can find Recursive Enumerable Language (RELi); from REL_Set that
has the property.

RELi_YES = { φ } (Turing Machine accepts language ⇒ L = { φ })

Can we find RELj from REL_Set that does not have the property?
“Answer is YES”
RELj_NO = {0, 1, 00, 000, 1111, …0011,…}

(Turing Machine accepts language L ⇒ L = {∑ } , ∑ ={0, 1} })

+

We can observe now,

RELi _ YES ⊂ REL j _ NO

So, it is a non-monotonic property.
Hence, By Rice Theorem, the language is not even semi-decidable.
Decidability

238
 Chapter 6
Example:
L = {<M>|L(M) is infinite}
This is monotonic property since an infinite set can never be a subset of a
finite set. So, we cannot apply Rice Theorem Part-II here.
We can use reduction to prove language is not Recursive Enumerable (RE).
It proves RICE Theorem Part-II is not the necessary condition for language
to be NOT Recursive Enumerable (RE). It is a sufficient condition.

Reducibility:
Let us have two problems, A and B. If we have an algorithm to convert
instance of problem A to instance of problem B that have the same answer,
then we say
A reduces to B
or
A is polynomially reduced to B
or
A is many to one reducible to B
or
A ≤B
or

A ∝p B
or
A ≤m B
or
B is at least as hard as A.

Fig. 6.7 A Is Reducible To B With The Help Of Mapping

Let, L 1 ≤ L2
Decidability

239
Chapter 6

Fig. 6.8 Every Member Of L1 Is Also Mapped

To Some Member Of L2

Fig. 6.9 Every Instance Of L1 Is Mapped To

Some Instance Of L,

Grey Matter Alert!

Let L1 reducible to L2 (L1 £ L2)

y If L2 is decidable, then L1 is decidable.
y If L1 is undecidable, then L2 is undecidable.
y If L2 is Recursive Enumerable (RE), then L1 is Recursive Enumerable
(RE).
y If L1 is not Recursive Enumerable (RE), then L2 is not Recursive
Enumerable (RE).
y If L 1 = θ(n2 ) , then L2 = Ω(n2 ) .

y If L2 = θ(n2 ) , then L 1 = O(n2 ) .

Decidability

240
 Chapter 6
Note:

• If A ≤ B and B ≤ C , then A is also reducible to C (A ≤ C) .

• If A ≤ B and C ≤ B , then
— If B is decidable, then A and C both are decidable.
— If A is decidable, then we cannot answer about B and C.
• If A ≤ B and B ≤ C , then
— If C is decidable, then B is decidable as well as A is decidable.
— If B is decidable, then A is also decidable but we cannot answer
about C.
— If A is undecidable, then B and C are also undecidable.
— If B is undecidable, then C is also undecidable.

Decidability

241
Decidability Chapter 6

242
 Chapter 6
SOLVED EXAMPLES

Q1 Membership problem is decidable on (More than one maybe

correct option):
a) Regular language
b) Context-free language
c) Context-sensitive language
d) Deterministic context-free language.

Sol: a), b), c) & d)

Explanation:
Membership problem is decidable for all languages except
recursively enumerable language because all the machine
always halts except Turing machine.

Q2 Consider the following statement:

S1: Recursive language is also called decidable language.
S2: Recursively Enumerable languages are also called as
semi-decidable language.
S3: Partially decidable and semi-decidable both are the
same.
Number of correct statement(s) is/are_____.

Sol: 3 to 3
Explanation:
All the statements is correct.
Recursive language is called decidable language because, for
the recursive language, we have halting Turing Machines.
For recursively enumerable language, we have a Turing machine
and Turing machine may or may not halt, but TM always halts for
string belongs to the language.
Hence, Recursively enumerable languages are semi-decidable.
Partially decidable and semi decidable means the same only.
Decidability

243
Chapter 6

Q3 CFL are decidable on:

a) Membership problem only b) Emptiness problem only
c) Finiteness Problem only d) All the above

Sol: d)
CFL are decidable on membership problem, emptiness problem, finiteness
problem because we have analgorithm for all the problems.
Push down automata or CYK is analgorithm for membership problems.
For Emptiness problem algorithm is the simplification of CFG.
The Dependency tree lets us know whether the grammar is finiteness or not.
Hence, d) is the correct option.

Chapter Summary

y Decision problem:
A decision is a set of related statements, each of which must be either true or
false.
i) For decidable problems, Halting Turing Machine (HTM) exists.
ii) For undecidable problem, Halting Turing Machine (HTM) does not exist, but
Turing Machine (TM) may exist.
iii) If a problem is not recursive enumerable (RE), then no Turing Machine exists for
that problem.
Decidability

244
 Chapter 6
y Language:
The set of all strings that can be generated from the grammar.

Fig. 6.10

y Encoding a Turing Machine (TM)

Each Turing Machine with input alphabet {0, 1} may be thought of as a binary string.

y The diagonalization language (Ld):

It is the set of strings (wi) such that wi is not in L(Mi).

Ld = {w ∈ (0 + 1)
i
+
}
| wi ∉ L(Mi )

y An undecidable problem that is recursive enumerable (RE):

We have already seen that there is no Turing machine for Diagonal Language (Ld)
to accept it.

y Recursive languages:
A recursive language L If L = L(M) for some Turing Machine (M) such that:
1) w ∈ L ⇒ Halt and accept
2) w ∉ L ⇒ Halt and reject

y Compliment of recursive and recursive enumerable language (RE):

If a language L is Recursive Enumerable but the complement of recursive
enumerable language (L) is not Recursive Enumerable (RE), then we can say L
can not be Recursive.
Decidability

245
Chapter 6

Fig. 6.11 Relationship between Recursive and Recursive Enumerable (RE)and

not Recursive Enumerable (RE) language.

y T uring machine halting problem:

“Does a Turing Machine (M) halt on input w?”
OR
“Is w ∈ L(M)?”
We know that Turing Machine has three possibilities.

If w ∈ L(M). So, it will halt on accepting states.

If w ∉ L(M). So, it may halt on the reject state, or it can get into an infinite loop.

y Rice theorem part-I:

Any non-trivial property of Recursively Enumerable Language (REL) is undecidable.

y Trivial property:
A property is trivial if either it is satisfied by all Recursive Enumerable Languages
or it is not satisfied by any Recursive Enumerable Language (REL).
Decidability

246
 Chapter 6
y Non-trivial property:
A property is non-trivial if it is satisfied by some Recursive Enumerable Languages (REL)
and are not satisfied by others.

y Rice theorem part-II:

Any Non-Monotonic property of Recursively Enumerable Language is not even Semi-de-
cidable.

y Reducibility:
Let us have two problems, A and B. If we have an algorithm to convert an instance of
problem A to instance of problem B that has the same answer, then we say A reduce
to B

Decidability

247