RGPV TOC June 2020

B.Tech., V Semester
Examination, June 2020
Choice Based Grading System (CBGS)
Theory of Computation

1. a) Differentiate Mealy machine and Moore machine with diagram.

Ans. Click here

b) Design Turing machine to add two number a and b.

2. a) State Pumping Lemma and show that L 1 { aibi>=1} is not a regular language. 

b) Explain types of Turing machine in detail. 

3. a) Prove that CFL are not closed under intersection. 

Ans. Click here.

b) Construct Moore machine for the following Mealy machine.

Ans. Click here.

4. a) Explain P class problems in detail.

b) What is a trap state in FA? Explain the properties of transition function.


5. a) Define DFA, List three household applications of finite automata. 


b) What are leftmost and rightmost derivations? Explain with suitable example. 

Ans. Click here.

6. a) What is PDA? Explain instantaneous description of PDA.

b) Show that the following grammar is ambiguous. 

S → aSbS|bSaS|∈

Ans. Click here

7. a) How can we construct regular grammar from regular expression

Ans. Click here.

b) Write given CFG for R.E (011 + 1)*(01)*. 

Ans. Click here.

8. Write short note on any three of the following.

i) Undecidable problem

ii) Two way finite automata

iii) UTM

iv) Multitape

v) Recursively enumerable set

Read other years TOC papers.

RGPV TOC May 2018 solved paper

More topics to read in TOC

  1. Definition of DFA
  2. DFA notations
  3. How DFA process inputs
  4. DFA solved examples
  5. Definition of NFA
  6. Moore machine
  7. Mealy machine
  8. Regular expression
  9. Regular expression examples
  10. Arden’s Law
  11. NFA with ∈ moves
  12. NFA with ∈ to DFA Indirect method