Question Paper Code : P 1213
B.E B.Tech DEGREE EXAMINATION, NOVEMBER / DECEMBER 2009
Seventh Semester
(Regulation 2004)
Information Technology
CS 1303 - THEORY OF COMPUTATION
(Common to FIFTH SEMESTER B.E. Computer Science Engineering)
Answer ALL questions.
PART A - (10 x 2 = 20 marks)
1. what do you mean by expressive power of a grammar.
2. Construct a PDA to accept the language {(ab) ^ n =.1}.
3. When does a Turning machine become an algorithm?
4. Give a semi-Thue grammar generating {a ^ i | i is a positive power of 2 }
5. What is {10, 11}* (Write atleast first seven terms).
6. State Greback Normal Form.
7. For a PDA M = (Q,, S, G, d, q0, Z0, F), define the language accepted by final state.
8. When do you say a problem is NP-Hard?
9. State pumping lemma for context-free languages.
10. State two languages, which are not recursively enumerable.
PART B - (5 x 16 = 80 marks)
11 (a) (i) Prove that for any language L recognized by an NFA with ? - transitions, there exists an NFA without ? -transitions to recognize (8)
(ii) Construct an NFS without ? - transitions for the following NFA. (8)
see the state diagram Image on attachment 1
(b) (i) For a given regular expression r, prove that there exists an NFA with ? -transitions that accepts L(r). (8)
(ii) Find the regular expression corresponding to the following automata. (8)
see the state diagram Image on attachment 2
12 (a) (i) Prove that a CFL can be recognized by a PDA by expty stack. (9)
(ii) Construct a PDA exuivalent to the following grammar. S ? aAA A ? aS|bS|a (7)
OR
(b) (i) Prove that every language recoginized by a PDA is Context-free. (8)
(ii) Construct a PDA for the set of palindrome over the alphabet {a, b}. (8)
13 (a) (i) Prove that every non-empty CFL is generated by a CFG with no useless symbols. (9)
(ii) State and prove Chomsky normal form for CFL. (7)
OR
(b) (i) State an prove pumping lemma for context free languages (10)
(ii) Using pumping lemma prove that the language {a^ib^ic^i | i = 1} is not context free (6)
14 (a) Design a Turing Machine to recognize each of the following languages.
(i) {0n 1n|n = 1} (8)
(ii) {ww^R | w ? (0 + 1)*} (8)
(b) (i) Prove that the Turing machines with one-way infinite tape and two-way infinite tape are equivalent (8)
(ii) Design a Turing machine to compute n². (8)
15 (a) Prove that the Universal language is recursively enumerable but not recursive. (16)
(b) State and prove Rice's theorem for recursively enumerable index sets. (16)
KEYWORDS:INFORMATION TECHNOLOGY,CS 1303 - THEORY OF COMPUTATION,THEORY OF COMPUTATION,2009 ANNA UNIVERSITY CHENNAI B.E COMPUTER SCIENCE P 1218 - THEORY OF COMPUTATION NOV / DEC 2009 QUESTION PAPER,ANNA UNIVERSITY INFORMATION TECHNOLOGY QUESTION PAPER,ANNA UNIVERSITY,ANNA UNIVERSITY CHENNAI,ANNA UNIVERSITY COIMBATORE,ANNA UNIVERSITY TRICHY,ANNA UNIVERSITY TIRUNELVELI,ANNA UNIVERSITY MADURAI,ANNA UNIVERSITY SYLLABUS,ANNA-UNIVERSITY RESULTS,ANNA UNIVERSITY DISTANCE EDUCATION,ANNA UNIVERSITY MBA-CENTRE FOR DISTANCE EDUCATION,ANNA UNIVERSITY SCHEDULE OF EXAMINATIONS,ANNA UNIVERSITY ADMISSION,ANNA UNIVERSITY COURSES,ANNA UNIVERSITY ACADEMIC,ANNA UNIVERSITY DEPARTMENTS,ANNA UNIVERSITY RESEARCH,ANNA UNIVERSITY MAIL,ANNA UNIVERSITY QUESTION PAPERS,ANNA UNIVERSITY COUNSELLING DATES,ANNA UNIVERSITY RE-EVALUATION RESULTS
B.E B.Tech DEGREE EXAMINATION, NOVEMBER / DECEMBER 2009
Seventh Semester
(Regulation 2004)
Information Technology
CS 1303 - THEORY OF COMPUTATION
(Common to FIFTH SEMESTER B.E. Computer Science Engineering)
Answer ALL questions.
PART A - (10 x 2 = 20 marks)
1. what do you mean by expressive power of a grammar.
2. Construct a PDA to accept the language {(ab) ^ n =.1}.
3. When does a Turning machine become an algorithm?
4. Give a semi-Thue grammar generating {a ^ i | i is a positive power of 2 }
5. What is {10, 11}* (Write atleast first seven terms).
6. State Greback Normal Form.
7. For a PDA M = (Q,, S, G, d, q0, Z0, F), define the language accepted by final state.
8. When do you say a problem is NP-Hard?
9. State pumping lemma for context-free languages.
10. State two languages, which are not recursively enumerable.
PART B - (5 x 16 = 80 marks)
11 (a) (i) Prove that for any language L recognized by an NFA with ? - transitions, there exists an NFA without ? -transitions to recognize (8)
(ii) Construct an NFS without ? - transitions for the following NFA. (8)
see the state diagram Image on attachment 1
(b) (i) For a given regular expression r, prove that there exists an NFA with ? -transitions that accepts L(r). (8)
(ii) Find the regular expression corresponding to the following automata. (8)
see the state diagram Image on attachment 2
12 (a) (i) Prove that a CFL can be recognized by a PDA by expty stack. (9)
(ii) Construct a PDA exuivalent to the following grammar. S ? aAA A ? aS|bS|a (7)
OR
(b) (i) Prove that every language recoginized by a PDA is Context-free. (8)
(ii) Construct a PDA for the set of palindrome over the alphabet {a, b}. (8)
13 (a) (i) Prove that every non-empty CFL is generated by a CFG with no useless symbols. (9)
(ii) State and prove Chomsky normal form for CFL. (7)
OR
(b) (i) State an prove pumping lemma for context free languages (10)
(ii) Using pumping lemma prove that the language {a^ib^ic^i | i = 1} is not context free (6)
14 (a) Design a Turing Machine to recognize each of the following languages.
(i) {0n 1n|n = 1} (8)
(ii) {ww^R | w ? (0 + 1)*} (8)
(b) (i) Prove that the Turing machines with one-way infinite tape and two-way infinite tape are equivalent (8)
(ii) Design a Turing machine to compute n². (8)
15 (a) Prove that the Universal language is recursively enumerable but not recursive. (16)
(b) State and prove Rice's theorem for recursively enumerable index sets. (16)
KEYWORDS:INFORMATION TECHNOLOGY,CS 1303 - THEORY OF COMPUTATION,THEORY OF COMPUTATION,2009 ANNA UNIVERSITY CHENNAI B.E COMPUTER SCIENCE P 1218 - THEORY OF COMPUTATION NOV / DEC 2009 QUESTION PAPER,ANNA UNIVERSITY INFORMATION TECHNOLOGY QUESTION PAPER,ANNA UNIVERSITY,ANNA UNIVERSITY CHENNAI,ANNA UNIVERSITY COIMBATORE,ANNA UNIVERSITY TRICHY,ANNA UNIVERSITY TIRUNELVELI,ANNA UNIVERSITY MADURAI,ANNA UNIVERSITY SYLLABUS,ANNA-UNIVERSITY RESULTS,ANNA UNIVERSITY DISTANCE EDUCATION,ANNA UNIVERSITY MBA-CENTRE FOR DISTANCE EDUCATION,ANNA UNIVERSITY SCHEDULE OF EXAMINATIONS,ANNA UNIVERSITY ADMISSION,ANNA UNIVERSITY COURSES,ANNA UNIVERSITY ACADEMIC,ANNA UNIVERSITY DEPARTMENTS,ANNA UNIVERSITY RESEARCH,ANNA UNIVERSITY MAIL,ANNA UNIVERSITY QUESTION PAPERS,ANNA UNIVERSITY COUNSELLING DATES,ANNA UNIVERSITY RE-EVALUATION RESULTS