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
I have been exploring for a bit for any high-quality articles or weblog posts in this kind
of space . Exploring in Yahoo I finally stumbled upon this website.
Studying this information So i’m satisfied to convey that I’ve a very
good uncanny feeling I came upon just what I needed. I such a lot indisputably will make certain to don?t fail to remember this site and provides it a
glance on a constant basis.
Hey very interesting blog!
Hey there! Quick question that’s completely off topic.
Do you know how to make your site mobile friendly? My web site looks weird
when browsing from my iphone. I’m trying to find
a theme or plugin that might be able to fix this problem.
If you have any suggestions, please share. Thanks!
Pretty nice post. I just stumbled upon your blog
and wanted to say that I’ve truly enjoyed surfing around your blog posts.
After all I will be subscribing to your feed and I hope you write again very soon!
whoah this weblog is excellent i like studying your posts.
Stay up the good work! You understand, a lot of individuals are searching around for this info, you can aid them greatly.