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

We rely on ads to keep our content free. Please consider disabling your ad blocker or whitelisting our site. Thank you for your support!

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

This post was last modified on 31 January 2020

whatsapp