Reg. No.
Question Paper Code:50903
B.E./[Link]. DEGREE EXAMINATIONS, APRILMAY 2024.
Fourth Semester
Computer Science and Engineering
CS 3452-THEORY OF COMPUTATION
(Common to : Computer Science and Engineering (Artificial Intelligence and
Machine Learning)/Computer Science and Engineering (Cyber Security)/
Information Technology)
(Regulations 2021)
Time: Three hours Maximum: 100 marks
Answer ALL questions.
PART A -(10 x 2 = 20 marks)
1 How will you prove the group of statements together? Justify.
2 Draw the transition diagram to recognize a constant.
3 Write the regular expression for the language L= {Set of string with even
number of 1's followed by odd number of O's).
4 Let E={0, 1} and 2= {a, b, c} with h(0)=ab, h(1)=ac. Find homomorphic image
of L={010, 0010, 1010},.
5. Write the Chomsky hierarchy of grammar.
6. Mention the language accepted by empty stack and final state.
7. What is meant by reachable symbol?
List any four closure properties of CFL.
9. When do you say a problem is decidable? Give example.
10 What is intractable problem? Give example.
( 6 mark)
(a) () l'rove that the ntatement "f 6 then n can be written as a sum
ofs and ' by inductive prineiple. (7)
(u) Construet a DEA hat accepts the string over an alphabet (0,1).
number of O's is multiples of 3. (6)
Or
(b) (i) ln Fig. l1(b), find the cquivalent DFA for the following NFA. (7)
0,1
Fig. 11(b)
(ii) Prove that the language L is accepted by NFA with ɛ-transition,
then there exist DFA also accept the same language L. (6)
12. (a) (i) From Fig. 12(a), find the regular expression for the following DFA. (8)
Fig. 12(a)
(Gi) Construct an NFA for the regular expression (01+10)* 10*. (5)
(b) (i) Show that the language L = 0"12" |n> 0 is not regular. (8)
(i) Prove if L and M are regular language, then so is L-M. (5)
13. (a) (i) Construct PDA that accept the language
L =a"b'c"d" I n, n > 1 by empty stack.
(7)
L(P) = L(G).
(ii) Prove that if PDA P is constructed from CFG G, then (6)
50903
(b) )
Construt a (R G whheh Avvpts the language LM) whe
(7)
Grammar G:s SIS I0,. ls this granmar G is ambiguous?
Justify. (6)
14. (a ) Convert the CFG into (NF (S)
S→AB
B → bBB|
(i) Prove that L = ja' | nis perfect square} is not eontext free. 5Y
Or
(b) Design a Turing Mlachine to compute (8)
f(m.n)= [Link] m >n
=0, if m <n
(1i) Explain the programming techniques for Thuring Machine. (5)
15. (a) (i) Let S = (o.1}. Let A and B be the list of string defined as
List A List B
1 1 10
2 110
3 0 11
Find the instance of MPCP. (7)
(ü) Show that 3-CNF SAT is NP oomplete. 6)
Or
(b) Find the following languages are recursively enumerable.
Union of recursively enumersble languages. 7)
(11) L and complement of L are recursively enumerable. (6)
50903
PART C-(| x 13 = 15 marks)
16 (a)
Construct a minimal state DFA and find the regular expression for the
DFA. (15)
Or
(b) Construct a Turing Machine to implement the multiplication operation
f(m,n) = m*n, where m and n are positive numbers and simulate their
action as input 5*4. (15)
50903