**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) ScBA, SA, AcB, AAbbS, Baaa (6) NOV/DEC 2012

(ii) Sa|AAB, Aab|aB| ε, Baba| ε (8) APR/MAY 2011

(iii) SA|CB, AC|D, B1B|1, C0C|0, D2D|2 (16) APR/MAY 2010

(iv) SaAD AaB|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) SAA | 1, ASS |0 (10) MAY/JUNE 2012

(iii) Sa|AB, Aa|BC, Bb, Cb (4) APR/MAY 2011

(iv) SAA|0, ASS|1 (8) NOV/DEC 2010

(v) A1A2A3, A2A3A1|b, A3A1A2|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**