Download DU (University of Delhi) B-Tech 5th Semester Theory of Computation Question Paper

Firstranker's choice www.FirstRanker.com

SL. No. of Ques. Paper : 1333

Unique Paper Code : 2341502

--- Content provided by FirstRanker.com ---

Name of Paper : Theory of Computation

Name of Course : B.Tech. Computer Science

Semester : V

Duration : 3 hours

Maximum Marks : 75

--- Content provided by FirstRanker.com ---

Question No. 1 is of 35 marks and all its parts are compulsory.

Attempt four questions from Q. Nos 2 to 7.

PART A

Note: For all the questions, consider the alphabet {a,b} unless otherwise specified.

1. (a) Is (S*)' = (S*)* for all sets S ? Explain with an example. (3)
   

   --- Content provided by FirstRanker.com ---

   (b) Consider the language PALINDROME and a string y over the given alphabet. Prove that if the string yⁿ is in PALINDROME, then so is the string y. (3)
   (c) Give a regular expression for the language of all words that do not end in a double letter. (3)
   (d) Show that (ab)*a and a(ba)* define the same language. Give the set of strings representing the two languages. Give the first five strings generated in the lexicographic manner. (3)
   (e) Using pumping lemma for regular languages, show that the language L={aⁿbaⁿ | n > 0} is not regular. (3)
   (f) Given two Finite Automata(FA): FA₁ and FA₂, find the machine for the intersection of the languages represented by these FA’s. (3)
   

   --- Content provided by FirstRanker.com ---

   (g) Create a Push Down Automata(PDA) for the language L = {aⁿS, where S starts with b and length (S)=n }. (3)
   (h) Find a Context Free Grammar(CFG) for the language defined by the regular expression a*b*. (3)
   (i) Show that the following CFG is ambiguous by finding a word with two distinct syntax trees: (3)
   S→AA
   A→AAA|a|bA | Ab
   

   --- Content provided by FirstRanker.com ---

   (j) Convert the following CFG into CNF: (3)
   X→aS|bS|a
   (k) Explain the working of the following Turing Machine(TM): (5)
   >R:EE→1R→§RUaRub
   U represents the blank symbol.
   

   --- Content provided by FirstRanker.com ---

   (l) Describe the Universal Turing Machine. (3)

PART B

2. (a) Let language L= EQUAL, the language with words having equal number of a's and b's and L₂= {aⁿb^maⁿ| m,n=1,2,...}. What is the language defined by the intersection of L₁ and L₂? Is it a context free language? If yes, construct a PDA for the language, else prove using pumping lemma for CFLs. (6)
3. (b) Construct a CFG.

3. (a) Prove that regular languages are closed under complementation, i.e., if a language L is regular then L’(complement of L) is also regular. (3)

--- Content provided by FirstRanker.com ---

4. (b) For the following pair of regular languages find an FA that defines the difference, L₁-L₂: (6)
   L₁=(a+b)*c
   L₂=b(a+b)*c
   Z={abc}
5. (c) Build an FA that accepts the language of all strings of a's and b's such that the next to last letter is an a. (3)

--- Content provided by FirstRanker.com ---

4. (a) Consider the homomorphism h from the alphabet {0,1,2} to {a,b} defined by:
   h(0)=ab, h(1)=b, h(2)=aa
   i) What is h(0210)?
   ii) What is h(2201)?
   iii) If L is the language 102*, what is h(L)? (4)

--- Content provided by FirstRanker.com ---

5. (b) Give a PDA for the language with words of type a^xb^ya^zb^w x,y,z,w=1,2,3 y>x and z>w and x+z=y+w. (6)

5. (a) Convert the following NFA to DFA. (4)
6. (b) Write regular expression and construct a DFA for the following language of all words that have an even number of substrings ab in them. (5)

6. (a) Consider the following CFG in Chomsky Normal Form (CNF) (6)
   S→PQ
   

   --- Content provided by FirstRanker.com ---

   Q→Qs|b
   P→a
   Generate the derivation trees for the word i)abab ii)ababab
7. (b) Consider S as the self embedded non terminal, trace the division of each word w into uvxyz and uvvxyyz, where |u|+|z|>=0, |v|+|y|>0 and |x|>0.

7. (a) Which of the following could be configurations of a Turing Machine? Justify your answer.
   

   --- Content provided by FirstRanker.com ---

   i. (q,>aUaU, U, Ua)
   ii. (q, abe,b, abc)
   iii. (p, >abc,ae)
   iv. (h,>,ee)
   (> represents the left end symbol) (4)

--- Content provided by FirstRanker.com ---

8. (b) Give a Turing Machine which computes the function f(w) =ww. (5)

The language H = { “M w” ; Turing machine M halts on input w} describes the halting problem. Prove that H is not recursive, i.e., the Halting problem is undecidable.

www.FirstRanker.com