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

FirstRanker.com

SI. No. of Ques. Paper: 16192 F-5

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 ---

(Write your Roll No. on the top immediately on receipt of this question paper.)

Question No. 1 is of 35 marks and all its parts are compulsory. Attempt any four questions from Q. No. 2 to Q. No. 7.

PART A

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

1. (a) For a language defined over the alphabet , is (a*b*)'=(a+b)*? Generate the first 6 words of each of the language in the lexicographic order. 3

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

2. (b) Construct a Finite Automata (FA) for a language having strings that do not end in a double letter, i.e., aa or bb. 3
3. (c) Build an FA machine that accepts all strings that have an even length that is not divisible by 6. 3
4. (d) Consider the grammar for the language aⁿb^m:
   S -> aS|ab
   Chomsky-ize the grammar. 3

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

5. (e) Convert the following Non-deterministic FA (NFA) to Deterministic FA (DFA): 3
   N, +—0O
   o )
   (i
6. (f) Find a Context Free Grammar (CFG) for a language of the form a^xb^ya^z where X,Y,z=1,2,3...and x +z=y = {abba, aabbba, abbbaaa, ...} 4

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

7. (g) Construct a Push Down Automata (PDA) that accepts strings with unbalanced open and close round braces, where all the opening braces precede the closing braces, i.e., strings of the form (ⁿ)^m where n,m=1,2,3 ... (i.e.,n, m ∈ N) and n≠m. Some example strings are {(), (()), ((())), (()(), ... }. The alphabet for the language is {(,)}. 4
8. (h) Design a Turing Machine (TM) to accept the language with words of the form aⁿbⁿaⁿ where n=1, 2,3 ... (i.e.,, n, m ∈ N). 4
9. (i) Construct a TM that transforms the configuration UwU (where w is an input string with no blanks) into the configuration UUwU. U is representing the blank symbol and _ shows the current position of the head of the TM. 4
10. (j) Use Pumping Lemma to show that the language PALINDROME is non-regular. 4

PART B

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

2. (a) What language is PALINDROME ∩ {aⁿbⁿa^m | n, m=1,2,3 ... (ie, n, m ∈ N)}. Is it context free? If context free, draw the PDA, else use Pumping Lemma to show that it is non-CF. 5
3. (b) Give a CFG for language with words of type a^xb^ya^zb^w, x,y,z,w =1,2,3 ... y>x,z>w and x+z =y+w. 5

3. (a) Consider the CFG in Chomsky Normal Form (CNF):
   S->PQ
   Q->QS/b ,
   

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

   P->a S
   Generate the derivation trees for the words (i) abab, (ii) ababab.
   Consider Q 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. 5
4. (b) Consider the following languages:
   L1={aⁿb^m where n≥m}
   

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

   L2={aⁿb^m where m=n}
   What is the language formed by their intersection? Show that this language is context free by constructing a PDA. 5

4. (a) Use pumping lemma to show that language {aⁿbⁿcⁿ | n=1, 2, 3 ..} is non-regular. 4
5. (b) For the languages L1=(a+b)*a and L2= (a+b)*aa(a+b)*construct the respective FAs and derive the finite automata that define L1∩L2. 5

5. (a) Consider the homomorphism h from the alphabet {0, 1, 2} to {a, b} defined by:
   

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

   h(0) =ab, h(1) =b, h(2) =aa.
   (i) If L is the language (ab+baa)*bab, what is h^-1(L)?
   (ii) If L is the language consisting of the single string ababb, what is h^-1(L)? 4
6. (b) Given the language represented by (1+0)*1, show that the reverse of the language is also regular using a DFA. 3

6. (a) Construct a DFA accepting all strings w over {0, 1} such that the number of 1’s in w is 3 mod 4. 3

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

7. (b) Give the regular expression for the following language:
   (i) All the strings in which b’s occur in clumps of an odd number at a time such as abaabbbab, ab, ababbba, ...
   (ii) All words that contain exactly two b’s or exactly three b’s. 3+2

7. (a) If L is a recursive language, then prove that its complement is also recursive. 5
8. (b) What does the following notation represent:
   

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

   U("M","w") ="M(w)", where M= (K, Σ, Δ, s, H) and U is the Universal TM. 5

8. (a) Design a Turing Machine for finding the two’s complement of a given number which is provided as input to it in binary form over the alphabet {0, 1}. 5

FirstRanker.com