RGPV June 2020 TOC

CS-501-CBGS
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 i>=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.

Ans. 

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

Ans.

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

71 thoughts on “RGPV June 2020 TOC”

  1. Magnificent beat ! I would like to apprentice while you amend your website, how
    could i subscribe for a blog web site? The account aided me a acceptable deal.
    I had been tiny bit acquainted of this your broadcast offered bright clear idea

  2. I take pleasure in, cause I discovered just what
    I was looking for. You have ended my four day lengthy hunt!
    God Bless you man. Have a nice day. Bye

  3. I really like your blog.. very nice colors & theme. Did you make this website yourself or did
    you hire someone to do it for you? Plz respond as I’m looking to
    construct my own blog and would like to know where u got this from.

    cheers

  4. May I simply just say what a comfort to uncover somebody who truly knows what they are discussing on the
    internet. You certainly realize how to bring an issue to light
    and make it important. More and more people have to look at
    this and understand this side of the story. I was surprised that you are not
    more popular because you surely have the gift.

  5. Greetings! Very helpful advice in this particular post!
    It’s the little changes that make the largest changes.
    Many thanks for sharing!

Leave a Comment