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

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

This question paper contains 3 printed pages. Your Roll No. ..........................
Sl. No. of Ques. Paper : 6192 1125
Unique Paper Code : 2341502
Name of Paper : Theory of Computation
Name of Course : B.Tech. Computer Science
Semester : V
Duration : : 3 hours
Maximum Marks : 75
(Writeyour 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 speci?ed.
1. (a)
(b)
(C)
(d)
(e)
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
Construct a Finite Automata (FA) for a language having strings that do not
.end in a double letter, i.e., aa or bb. ' 3
Build an FA machine that accepts all strings that have an even length that is
, not divisible by 6. 3
Consider the grammar for the language anb?:
S -* aSlab
Chomky-ize the grammar. 3
Convert the following Non-detcrministic FA (NFA) to Deterministic FA .
(DFA): ? 3
(t7
Find a Context Free Grammar (CFG) for a language of the form Va?b?a? where
x, y, z = 1, 2, 3 and x + z =y = {abba, aabbba, abbbaaa, ...} 4
P. T. O.

6192
(g)
(h)
(i)
(j)
(b)
(b)
4. (a)
2
Construct a Fush 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 E N) and mam. Some example strings are {0), (O, ((0), ((0, }.
The alphabet for the language is {(,)} 4
Design a Turing Machine (TM) to accept the language with words of the
form anbna? where n= 1, 2, 3 (i. e., n, m E N). 4
Construct a TM that transforms the configuration UwLJ_ (where w is an input
string with no blanks) into the configuration UUwQ. U is representing the
blank symbol and _ shows the current-position of the head of the TM. 4
Use Pumping Lemma to show that the language PALINDROME is
non-regular. 4 _
PART B
What language is PALINDROME n {:?1?b"""?a?I | n, m= 1, 2, 3. ..(i e., n, m
E N)}. Is it context free? If context free, draw the PDA, else use Pumping
Lemma to show that it is non- -.CF 5
Give a CFG for language with words of type a?b?a?b?", x, y, z, w = 1, 2, 3
y>x,z>wandx+z =y+w. 5
Consider the CFG in Chomsky Normal Form (CNF):
S -> PQ
Q *QS/b ?
P -? a 5 '
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 uwxyyz, where |u| + |z| 20, |v| + |y| >0 and |x| >0.
Consider the following languages:
L1 4- {a'lbm where 112121},
L2 = {anbm where man}
What is the language formed by their intersection? Show that this language is
context free by constructing a FDA. 5
Use pumping lemma to show that language.{a?b2" | n=1, 2, 3 ...} is
non-rcgular. 4

(b)
(a)
(b)
(C)
(b)
3 6192
For the languages L1 = (a + b)*a and L; = (a + b)*aa(a + b) *construct the
respective FAs and derive the finite automata that define Llan. 1+ 2 +3
Consider the homomorphism h from the alphabet {0, 1. 2}.to {a, b} defined
by:
h(O) = 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
Given the language represented by (1+0)?1, show that the reverse of the
language is also regular using a DFA. 3
Construct a DFA accepting all strings w over {0, 1} such that the number of 3
1?s in w is 3 mod 4. . 3
Give the regular expression for the following language:
(i) All the strings in which b?s occur in clumps 'of an odd humber at a time .
such as abaabbbab, ab, ababbba ,
(ii) All words that contain exactly two b?s or exactly three b?s. 3 +2
If L is a recursive language, then prove that its complement is also recursive.
5
What does the following notation represent:
U("M""w w")- - "M(w)?, where M= (K, E, 6, s, H) and U 15 the Universal TM. 5
Design a Turing Machine for finding the two? 5 complement of a given
number which -is provided as input to it in binary form over the
alphabet {0, 1}. 5
400