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 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) 2 (b) For each of the following regular expressions, draw an FA recognizing the corresponding language.
i. 1(01 + 10) + 0(11 + 10)
ii. (010 + 00)(10).(7 marks) 2 (c) Let M₁ , M₂ and M₃ be the FAs pictured in Figure below, recognizing languages L₁ , L₂ , and L₃ respectively.