Twitter Facebook Delicious Digg Stumbleupon Favorites More

Thursday, 4 May 2017

IPU BTech Semester 4 - Theory Of Computation (End Term Paper 2016)

[MAY-JUNE 2016]
Subject Code: ETCS-206

Subject: Theory Of Computation

Time: 3 Hrs M.M: 75

Note: Attempt any five questions. Question 1 is compulsory.

Question 1: (5 × 5 = 25)
(a) Differentiate between DFA and NFA.

(b) What is ambiguity? How it is removed?

(c) Define recursive enumerable language. What are its different properties?

(d) Differentiate between Moore and Mealy Machine?

(e) Differentiate between NP-Hard and NP-Complete Problem.

Question 2:
(a) Briefly explain Chomsky Classification of languages with examples.
(b) Draw a DFA for all strings over [0,1] consisting of even no. of 0's and even no. of 1's

Question 3:
(a) State and prove Pumping Lemma for regular languages. Also prove that language L= {aⁿbⁿ for n = 0,1,2,3...} is not regular.

(b) Find a regular expression corresponding to each of the following subset [0,1]:
i.  The language of all strings containing at least two 0s.
ii. The language of all strings containing at most two 0s.

Question 4:
(a) Consider the CFG whose productions are:
S → bB/aA
A → b/bS/aAA
B → a/aS/bBB for the string bbaababa.
i.   Left most derivation
ii.  Right most derivation
iii. Parse Tree

(b) What is PDA? Construct a PDA accepting the set of all strings over [a,b] with equal nunber of a's and b's

Question 5:
(a) What are different closure properties of CFL? Explain with an example.
(b) State pumping Lemma for CFL. Provide an example to understand.

Question 6:
(a) State and prove Halting Problem.
(b) What is Turing Machine? What are its different variants? Explain.

Question 7:
(a) State and prove Savitch Theorem.
(b) Briefly explain Cook's Theorem.

Question 8: Write short note on any two:
(a) Space and Time Complexity.
(b) Turing Church's Thesis
(c) Chomsky Normal Form



Post a Comment

BCE-Hacks Notes

BCE-Hacks Notes
Chemical Engineering Notes

Maths Resources

Maths Resources
Maths Resources

Buy Books

Buy Books
Buy Books

Geography Quiz

Geography Quiz
Geography Quiz

NodeJS Tutorial

NodeJS Tutorial

History MCQs

History MCQs
History Quiz For Competitive exams


Popular Posts


Recent Posts

Unordered List

Express Print Zone

Eduvictors Quizzes

Online Quizzes, Study notes for CBSE Class 6 - 12

Text Widget


Study notes for Competitive Exams

Developer Bytes

Developer Bytes
Developer Bytes
Powered by Blogger.

Blogger Tutorials

Blogger Templates

Sample Text

Copyright © IP University Musings BCA, MCA, BBA, MBA, BTech Question Papers and Study Notes | Powered by Blogger
Design by SimpleWpThemes | Blogger Theme by