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

END TERM EXAMINATION

[MAY-JUNE 2016]

FOURTH SEMESTER BTech

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.

Find

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