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. I needed to thank you for this great read!! I absolutely loved every little bit of it.
    I’ve got you book marked to check out new stuff you post…

  2. Thank you for any other excellent post. Where else may anyone get that kind of information in such an ideal way of writing?
    I’ve a presentation subsequent week, and I’m at the look for such
    info.

  3. I’ve read several excellent stuff here. Definitely value bookmarking for revisiting.
    I surprise how much effort you set to create any such magnificent informative website.

  4. Hi! I just finished reading your blog post, and I must say, it was excellent. Your ability to explain complicated concepts in a simple and engaging way is truly remarkable. Thank you for providing such valuable content. I can’t wait to read more from you in the future.

  5. I take pleasure in, cause I found exactly what I was
    having a look for. You’ve ended my four day lengthy hunt!
    God Bless you man. Have a great day. Bye

Leave a Comment