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

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

This question paper contains 4 printed pages. Your Roll No.
..........................
Sl. No. of Ques. Paper_ , 1332 ' F?7 ?
Unique Paper Code? : 2341502 ?
Name ofPaper : Theory of Computation
Name of Course : B.Tech. Computer Science
Semester : V
Duration : : 3 hours
Maximum Marks ' : 75 \ . .
meNaon?tewp?mdetermreceiptof?isqm?mpapa)
? . Question No. 1 is of 35 marks and all its parts are compulsory.
? Attemptfour questibns from Q. Nos 2 to 7.
PART A
Note: For all the questions, consider the alphabet {a,b} unless otherwise speci?ed.
1. (a) Is (3*)+ = (35* for all sets 3 :7 Explain with an example. _ (2)
(b) Consider the lariguagc PALINDROME and a string y over the given ' (3)
glphabet. Prove that if the string y3 is in PALINDROME, then so is the _
string y. '
(0) Give a regular expression for the language of all words that do not end in (3)
a double letter. ? '
(d) Show that(ab)*a and a(ba)* de?ne the same language. Give the set of (2)
strings representing the two languages. Give the ?rst ?ve strings
generated in the lexicographic manner.
(e) Using pumping lemma fox regular languages, show that the langua~ e. (3
_ . g
={a"ba" I n 2 0} is not regular.
(1) Given two F inite AutomataCFA): FA; alld FA; find the machine for the (4)
. intersectionof the languages represented by these FA?s.
FA1
P.T;O_.

(g)
(h)
2(a)
(i)
FA; 7
Create 8. Push Down Automata(PDA) for the language L= { anS, where S (4)
starts with b and length (S)= n }.
Find a ConteXt Free Grammar(CFG) for the ianguage de?ned by the (2)
regular expression a*b*. '
Show that the following CFG' is ambiguous by ?nding a word with two (3)
distinct syntax trees:
3"? , I .
A?vAAAlalelAb ? ..
Convert the folloWing CFG into CNF: ' . I ? (3)
' S?+dKX
(k).
(1)
X?raSi-bS | a ,7 7
EXplain the wofkingpf the f?ilewing Turing MachineCI'M) . V i (2)
4 >R 19?..RiRUaRUb
U repr?sents the blank symbol. 7
Describe the Universalfl?uring Machine. ' . . , 7. i , (4)
PART B
Let language L1= EQUAL, the language with words having equal number (6)
of as and Us and L2= {anbma" a| m,n?=1,2,.. ..} What IS the language de?ned
by the intersection of L1 and L2? Is it a context '?'ee language? If yes,
construct a PDA for the language, else prove using pumping lemma for ,
' CFLs.

2(b)
3(a)
3(1)).
37(c)
4(a) ;
4(b)
? 5(a)
5(b)
' h(o)=ab, h(1)=b, h(2)=aa
. , 3 .
Construct a CFG for the language L = { amb? | m>n , m, n>=l}. ' . (4)
Prove that regular languages are closed under complementation, i.e., if a (3)
language L is regular then L'(com'plcment of L) is also regular.
For the following pair of regular lahguages ?nd an FA that de?nes the (4)
difference, Ll-Lz:
L. =(a+b)?c
Iq=b(a+b)'c
'~ Z={a,b,c}
~?Build an FA that accepts the language of all strings of 3's and?b's such that (3)
the next to last lgttet is an a.V ' '
by:
v .
i) What is h(0210)? V
. ii) What is 110201)?
iii) IfL is the language 1?02?, what is h(L)? '
y>x and PW and x+z#y+w. .
Convert the following NFA to DFA. . ' ' (5)
Write regular expression and construct a DFA for the following language (5)
V of all words that have an evennumber of substrings ab in them.
Consider the homomorphism h from the alphabet {0,1,2} to {a,-h}.de?ned (4)
. Give a PDA for the language with words of type: a?b?a?b?xygw = l,? 2,3 (6) '

6(a) Consider the foliowing cm in Chomsky Normal Fbrm (CNF) - _ (6) ?
S?vPQ ' '
0?er | b
P?>a
? Generate the derivation trees for the word i)abttb ii)ababab
Consider S as the self embedded non terminal, trace the division of each
word w into uvxyz and uvvxyw, '
where] Iu}+|z I>=O, lvl+|yl>0andlxl>0p
.6(b) Which of the following could be con?gurations of a Turing Machine? 4 (4)
Justify. your answer. , _ .
i. (q,>aUaU, U ,,Ua)
? ii. (q, abc,b, abc)
iii- (p, ?abc. 8; e) ?
iv. (h, b, e, e)
(b represents the le? and symbol)
7 (ti) . I Give a Turing Machine which computes the function f(w) =ww. , (5)
7 (h) . The language H= { ?M???w?; Turing machine M halts on input w} _ (5)
describes the halting preblem. Prove that H 15 not recursive, i. e., the
Haltiiig problem 13 undecidable.
200 3