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. Thanks , I have recently been searching for information about this subject for a long time
    and yours is the best I have came upon so far. But, what in regards to the conclusion? Are you certain in regards to the source?

  2. Hello, constantly i used to check webpage posts
    here in the early hours in the dawn, because i like to learn more and more.

  3. Pretty section of content. I just stumbled upon your site and in accession capital to assert that I acquire in fact enjoyed account your blog posts.
    Any way I’ll be subscribing to your augment and even I achievement you
    access consistently fast.

  5. Today, I went to the beachfront with my kids. I found a sea shell and gave it to my 4 year old
    daughter and said “You can hear the ocean if you put this to your ear.” She put the
    shell to her ear and screamed. There was a hermit crab inside and it pinched
    her ear. She never wants to go back! LoL I know this is totally off topic but
    I had to tell someone!

Leave a Comment