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
Thanks a lot for sharing this with all of us you really recognise what you’re speaking about!
Bookmarked. Please also visit my web site =). We will have a link trade agreement among us
This piece of writing gives clear idea in favor of the new users of blogging, that actually how to do blogging.
Undeniably believe that which you stated. Your favorite justification appeared to
be on the web the easiest factor to take note of. I say to you, I certainly get annoyed at the same time as other folks think about issues that they just don’t
recognize about. You controlled to hit the nail upon the top and outlined out the whole thing with no need side-effects ,
folks could take a signal. Will likely be again to get more.
Thanks
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!!