## Theory Of Computation - Dec 2014

### Computer Engineering (Semester 6)

TOTAL MARKS: 100

TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.

(2) Attempt any **four** from the remaining questions.

(3) Assume data wherever required.

(4) Figures to the right indicate full marks.
**1 (a) (i)** Given the relation R in A as R={(1,1), (2,2), (2,3), (3,2), (4,2), (4,4)}
is R (a) reflexive (b) symmetric (c) transitive? (d) antisymmetric?(4 marks)
**1 (a) (ii)** Show that 2^{n} > n 3 for n >10 by Mathematical Induction.(3 marks)
**1 (b) (i)** Give recursive definition of each of the following sets.

a. The set T of positive integer divisible by 2 or 7.

b. The set U of all string in {0,1} * containing the substring 00.(4 marks)
**1 (b) (ii)** Prove that for any every n>=0,n(n 2 +5) is divisible by 6.(3 marks)
**2 (a)** Find a regular expression corresponding to each of the following subsets of
{0, 1}*.
i. The language of all strings that do not contain the substring 110.
ii. The language of all strings containing both 101 and 010 as substrings.
iii. The language of all strings in which both the number of 0's and the number of
l's are odd.*

*(7 marks)*

*+ 0(11 + 10)*

i. 1(01 + 10)

**2 (b)**For each of the following regular expressions, draw an FA recognizing the corresponding language.i. 1(01 + 10)

*(10)*

ii. (010 + 00)

ii. (010 + 00)

*.*

*(7 marks)*

**2 (c)**Let M_{1}, M_{2}and M_{3}be the FAs pictured in Figure below, recognizing languages L_{1}, L_{2}, and L_{3}respectively.*
*

*Draw FAs recognizing the following languages.*

i. L

ii. L

iii. L

iv. L

v. L

(i) {w | w contains at least three 1s} (ii) {w | w starts and ends with the same symbol}.(7 marks)

G has productions: S -> AaA|CA|BaB A-> aaBa|CDA|aa|DC

B->bB|bAB|bb|aS C-> Ca|bC|D D->bD|Λ(7 marks)

{ a

{xε{a,b,c}|n

i. L

_{1}∪ L_{2}ii. L

_{1}∩ L_{2}iii. L

_{1}- L_{2}iv. L

_{1}∩ L_{3}v. L

_{3}- L_{2}. (7 marks)**3 (a)**Explain Pumping Lemma and its applications.(7 marks)**3 (b)**Generate the Context-Free Grammars that give the following languages.(i) {w | w contains at least three 1s} (ii) {w | w starts and ends with the same symbol}.(7 marks)

**3 (c)**Write Kleene's theorem part -1.(7 marks)**3 (d)**For given CFG G, find Chomsky normal form:G has productions: S -> AaA|CA|BaB A-> aaBa|CDA|aa|DC

B->bB|bAB|bb|aS C-> Ca|bC|D D->bD|Λ(7 marks)

**4 (a)**Write a Turing Machine to copy strings.(7 marks)**4 (b)**Write PDA for following languages:{ a

^{i}b^{j}c^{k}| i, j, k >= 0 and j = i or j = k}.(7 marks)**4 (c)**Write a Turing Machine to delete a symbol.(7 marks)**4 (d)**Write PDA for following languages:{xε{a,b,c}

_{a}(x)or n

_{a}<n<sub>c}.</n<sub>(7 marks)

**5 (a)**Explain Universal Turing Machine and Halting Problem.(7 marks)

**5 (b)**Answer the following

(i) Explain time and space complexity.

(ii) Explain P and NP completeness.(7 marks)

**5 (c)**Explain unbounded minimization and μ recursive functions.(7 marks)

**5 (d)**Top down and bottom up parsing.(7 marks)