CS6503 Question Bank Theory of Computation

CS6503 Question Bank Theory of Computation Regulation 2013 Anna University free download. Theory of Computation TOC CS6503 Question Bank pdf free download.

Sample CS6503 Question Bank Theory of Computation:

1. Convert the following grammar into CNF
(i) ScBA, SA, AcB, AAbbS, Baaa (6) NOV/DEC 2012
(ii) Sa|AAB, Aab|aB| ε, Baba| ε (8) APR/MAY 2011
(iii) SA|CB, AC|D, B1B|1, C0C|0, D2D|2 (16) APR/MAY 2010
(iv) SaAD AaB|bAB B b D d (6) NOV/DEC 2014

2. State and prove the pumping lemma for CFL. What is its main application? Give two examples. (10) NOV/DEC 2012, NOV/DEC 2011, MAY/JUNE 2013 CS6503 Question Bank Theory of Computation

3. Design a Turing machine for the following
(i) Reverses the given string {abb}. (8) NOV/DEC 2012
(ii) L={1n0n1n|n>=1} (10) MAY/JUNE 2012
(iii) L={anbncn} (8) APR/MAY 2011 CS6503 Question Bank Theory of Computation TOC
(iv) To perform proper subtraction (8) APR/MAY 2011 (v) To move an input string over the alphabet A ={a} to the right one cell. Assume that the tape head starts somewhere on a blank cell to the left of the input string. All other cells are blank, labeled by ^. The machine must move the entire string to the right one cell, leaving all remaining cells blank. (10) APR/MAY 2010

4. Write briefly about the programming techniques for TM. (8) NOV/DEC 2012,MAY/JUNE 2013 CS6503 Question Bank Theory of Computation TOC

5. Find Greibach normal form for the following grammar
(ii) SAA | 1, ASS |0 (10) MAY/JUNE 2012
(iii) Sa|AB, Aa|BC, Bb, Cb (4) APR/MAY 2011
(iv) SAA|0, ASS|1 (8) NOV/DEC 2010
(v) A1A2A3, A2A3A1|b, A3A1A2|a (10) NOV/DEC 2014

6. Explain any two higher level techniques for Turing machine construction. (6) MAY/JUNE 2012, NOV/DEC 2011

7. Discuss the closure properties of CFLS. (6) MAY/JUNE 2012, NOV/DEC 2011,NOV/DEC 2010, MAY/JUNE 2013

8. Prove that every grammar with ε productions can be converted to an equivalent grammar without ε productions. (4) APR/MAY 2011, NOV/DEC 2013

9. Explain the different models of Turing machines. (10) NOV/DEC 2011 CS6503 Question Bank Theory of Computation

10. Define Pumping Lemma for Context Free Languages. Show that L={ai bj ck : i<j<k}is not context free grammar (6) APR/MAY 2010

11. construct the following grammar in CNF
A->BCD/b
B->Yc/d
C->gA/c
D->dB/a
y->f

Subject Name	Theory of Computation
Subject code	CS6503
Regulation	2013

CS6503 Question Bank Theory of Computation click here to download 

CS6503 Syllabus Theory of Computation

---

CS6503 Notes Theory of Computation

---

CS6503 Important Questions Theory of Computation

---