# CS6503 Question Bank Theory of Computation

## 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