**CS-501-CBGSB.Tech., V SemesterExamination, June 2020Choice 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 { a^{i}b^{i }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

Hey there! I realize this is sort of off-topic but I had to ask.

Does running a well-established blog like yours take a lot of

work? I am completely new to running a blog however I do write in my journal

everyday. I’d like to start a blog so I can share my experience and

feelings online. Please let me know if you have any recommendations or tips for new aspiring

blog owners. Thankyou!

Excellent web site you’ve got here.. It’s hard to find high quality writing like

yours nowadays. I truly appreciate people like you!

Take care!!

Ahaa, its good discussion on the topic of this post

here at this web site, I have read all that, so now me also commenting at this place.

Yes! Finally someone writes about have a peek at this web-site.

I enjoy what you guys are usually up too. This type of clever work and exposure!

Keep up the superb works guys I’ve included you guys to blogroll.