B.E/B.Tech DEGREE EXAMINATION APRIL/MAY 2008
Fifth Semester
Computer Science and Engineering
(Regulation 2004)
PART A (10 x 2 =20 marks)
2.What is the principle of mathematical Induction?
3.Construct a DFA for the regular expression aa*/bb*..
4.Construct a DFA over ∑=(a,b) which produces not more than 3 a’s.
5.Let S-> aB/bA
A->aS/bAA/a
B->bS/aBB/b
Derive the string aaabbabba as left most derivation.
6. What is meant by empty production removal in PDA.?
7.State the Pumping lemma for CFG.
8. Define turing machine
9.What is meant by halting problem.
10.What is post correspondence problem?
PART B (5 x 16 = 80)
(ii)construct a DFA that will accept strings on{a,b}where the number of b’s divisible by 3
(or)
(b) (i) Construct a finite automaton that accepts the set of all strings in {a,b,c}* such that the last symbol in input string appears earlier in the string
12 (a) (i) Construct the regular expression to the transition diagram.
(or)
(b)Construct a NFA for regular expression (a/b)*abb and draw its equivalent DFA.
13. (a) Construct a CFG accepting L={ambn/n
(or)
(b)Convert the grammar with productions into CNF A->Bab/λ.
14.(a) Design a deteministic turing machine to accept the language L={aibici/i>=0}
(or)
14. (b)Determine whether the language given byL={An2/N>=1} is a context free or not.
15. (a)Prove that the function fadd (x,y)=x+y
is a primitive recursive
(or)
15. (b)Show there exists aTM for which the halting problem is unsolvable
