Total No. of Questions : 8] SEAT No.

8
23
PA-1499 [Total No. of Pages : 3

ic-
[5926]-119

tat
6s
T.E. (Information Technology)

6:0
THEORY OF COMPUTATION

02 91
3:3
(2019 Pattern) (Semester - I) (314441)

0
31
Time : 2½ Hours]
3/0 13 [Max. Marks : 70
0
1/2
Instructions to the candidates:
.23 GP

1) Solve Q.1 or Q.2, Q.3 or Q.4, Q.5 or Q.6, Q.7 or Q.8.

2) Neat diagrams must be drawn wherever necessary.
E
81

8
3) Figures to the right indicate full marks.
C

23
4) Assume suitable data, if necessary.

ic-
16

tat
8.2

6s
Q1) a) What is a Regular Grammar? Explain types of regular grammar. [5]
.24

6:0
91
49

b) Simplify the following CFG. [6]

3:3
30

S → ABA
31
01
02

A → aA | ε
1/2
GP

B → bB | ε
3/0
CE

c) What is ambiguous grammar? Show that the following grammar is

81

8
23
ambiguous and find the equivalent unambiguous grammar. [7]
.23

E → E + E|E * E | (E) | I ic-

16

tat
8.2

6s

I→a|b
.24

6:0
91

OR
49

3:3
30

Q2) a) Write CFG for the language L= {ai bj ck | i = j + k & j, k >= l}. [6]
31
01
02

b) Check whether the given language is CFL or not L={anbncn | n>=0}. [6]
1/2
GP

c) Covert the following RLG to FA. [6]

3/0

S → 0A | 1B | 0 | 1
CE
81

A → 0S | 1B | 1
.23

B → 0A |1S
16
8.2
.24

P.T.O.
49

[5926]-119 1
Q3) a) Define Post machine. [3]

8
23
Design a PDA for accepting language L= { w c wR | w ∈ (a, b)*}. [6]

ic-
b)

tat
c) Define Push down Automata. Explain different types of PDA. Explain

6s
any two applications of PDA. [8]

6:0
02 91
3:3
OR

0
31
Q4) a)
3/0 13
Design a Pushdown Automata for the following language [7]
0
1/2
.23 GP

L = {an c bn | n > l}
E
81

8
b) Convert the grammar [6]
C

23
ic-
S → 0S1 | A
16

tat
8.2

6s
A → lA0 | S | ε
.24

6:0
91
49

3:3
to PDA that accepts the same language by empty stack.
30
31

c) Compare Finite Automata and Pushdown Automata. [4]

01
02
1/2
GP
3/0

Q5) a) Write a note on Universal turing Machine. [5]

CE
81

8
23
.23

b) Explain post correspondance problem with a suitable example. [6]

ic-
16

tat
c) Construct a Turing machine to find 2’s complement of a binary number.[7]
8.2

6s
.24

6:0

OR
91
49

3:3

Q6) a) Design a Turing Machine to increment value of binary number by one.[8]

30
31
01
02

b) Write short notes on [6]

1/2
GP

i) Unsolvable problems
3/0
CE
81

ii) Applications of Turing Machine

.23

c) What are recursive and recursively enumerable languages? [4]

16
8.2
.24
49

[5926]-119 2
Q7) a) What is a Traveling Salesman Problem? Justify that it is a NP-class

8
23
problem. [8]

ic-
tat
b) Write short notes on [9]

6s
6:0
02 91
i) A Simple Un-decidable problem

3:3
0
31
ii) 3/0 13
Measuring Complexity
0
1/2
.23 GP

OR
E
81

8
Q8) a) Explain Cook’s theorem in detail.
C

[8]

23
ic-
16

tat
b) Explain in detail the Node-Cover Problem. [9]
8.2

6s
.24

6:0
91
49

3:3

  
30
31
01
02
1/2
GP
3/0
CE
81

8
23
.23

ic-
16

tat
8.2

6s
.24

6:0
91
49

3:3
30
31
01
02
1/2
GP
3/0
CE
81
.23
16
8.2
.24
49

[5926]-119 3