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 am sure this piece of writing has touched all the internet viewers, its really really good post on building up
new web site.
I love what you guys are usually up too. This kind of clever work and coverage!
Keep up the fantastic works guys I’ve included you guys to
blogroll.
Hi there to every , because I am truly eager of reading this weblog’s post to be updated on a regular basis.
It contains good data.
Attractive portion of content. I just stumbled upon your weblog and in accession capital to claim that I acquire in fact enjoyed account your blog posts.
Any way I will be subscribing to your feeds and
even I fulfillment you get right of entry to persistently quickly.
Nice blog here! Also your web site loads up very fast!
What web host are you using? Can I get your affiliate link to your host?
I wish my web site loaded up as quickly as yours lol