Gujarat Technological University 2010 M.C.A Theory of computation - Question Paper
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA Sem-II Examination July 2010
Seat No. Enrolment No.
Subject Name: Theory of Computation Date: 09 / 07 /2010 Time: 11.00 am - 01.30 pm
Total Marks: 70
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
4.
Q.1 (a) Define surjection , injection and bijection. 05
(b) Explain : p q and pq. 05
(i) Only two 0 and 1 in any order.
(ii) String doesnt end with 11.
Q.2 (a) Give recursive definition for 04
Set of all strings in {0,1}* containing substring 00 .
( i ) (0+1)*(110)
( ii ) Language containing string of exactly two zeros.
OR
(i) S aSa | bSb | A
(ii) S aS | bS | a
(iii) S aSb | bSa | a
Q.3 (a) Given that L1 = {x e (0,1)* | x ends with 01} 07
L2 = {x e (0,1)* | x ends with 11}
Give FA for L1 , L2 and L1 U L2.
OR
Q.3 (a) Find minimal FA for following FA. 07
|
Q={1,2,3,4,5,6} A= {3,6} and q0 =1 State input - a input -b | ||||||||||||||||||
|
(b) Explain NFA - a . What are different kind of non-determinism possible in 07 NFA - a ? Also define a closure.
1
Q.4 (a) Let M = (Q, X, q0 , 6, A) where Q= {a,b,c,d}, q0 = a and A={d} and 6 is given as follows.
State input - 0 input -1
07
{b,d}
{b}
{d}
O
{c,d}
{d}
{c}
O
a
b
c
d
Give transition diagram for above NFA & find whether string 100101 will be accepted by it or not.
(b) Give transition table for deterministic PDA recognizing following languages. 07 {x e (a,b)* | Na(x) > Nb(x)}
OR
07
