toc-Apr 2008

Category: Education

Presentation Description



Presentation Transcript

slide 1:

Anna University B.E/B.Tech DEGREE EXAMINATION APRIL/MAY 2008 Fifth Semester Computer Science and Engineering CS1303—THEORY OF COMPUTATION Regulation 2004 Time: 3 hours Maximum marks: 100 Answer ALL questions PART A 10 x 2 20 marks 1.Define Automaton 2.What is the principle of mathematical Induction 3.Construct a DFA for the regular expression aa/bb.. 4.Construct a DFA over ∑ab 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 11. a i Prove that for every integer n0 the number 42n+13n+2 is a multiple of 13 iiconstruct a DFA that will accept strings onabwhere the number of b’s divisible by 3 or b i Construct a finite automaton that accepts the set of all strings in abc such that the last download from

slide 2:

symbol in input string appears earlier in the string 12 a i Construct the regular expression to the transition diagram. Diagram or bConstruct a NFA for regular expression a/babb and draw its equivalent DFA. 13. a Construct a CFG accepting Lambn/n or bConvert the grammar with productions into CNF A-Bab/λ. 14.a Design a deteministicturing machine to accept the language Laibici/i0 or 14. bDetermine whether the language given byLAn2/N1 is a context free or not. 15. aProve that the function fadd xyx+y is a primitive recursive or 15. bShow there existsaTM for which the halting problem is unsolvable download from

authorStream Live Help