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. You need to be a part of a contest for one of the finest
    sites on the net. I’m going to recommend this web site!

  2. If some one wishes expert view about blogging after that i suggest him/her to visit this web site, Keep up the good job.

  3. bromo77 bromo77 bromo77
    When I initially commented I clicked the “Notify me when new comments are added” checkbox and now each time
    a comment is added I get four e-mails with the same comment.
    Is there any way you can remove me from that service?
    Thank you!

  4. kitab4d
    I just could not leave your web site prior to suggesting that I actually enjoyed the standard info a person provide on your visitors?
    Is going to be back steadily to investigate cross-check new
    posts

  5. sssinstagram
    A fascinating discussion is definitely worth comment.

    I believe that you should publish more about
    this topic, it may not be a taboo matter but typically people don’t talk about these topics.
    To the next! Kind regards!!

Leave a Comment