Sr. No. of Question Paper: Your Roll No………….….
Unique Paper Code :
Name of the Course :
Name of the Paper : THEORY OF COMPUTATION
Semester : V
Duration : 3 Hours Maximum Marks : 75
Instructions For Candidates
1. Write your Roll No. on the top immediately on receipt of this question paper.
2. Part A is of 35 marks and all its questions are compulsory. Attempt any four questions
from Part B.
3. Assume { } as the underlying alphabet set unless mentioned otherwise.
4. Parts of a question must be answered together.
Part A
1 (a) Prove that for all sets S, 2
(b) Give regular expression for the language of all strings that do not contain 2
‘ab’ as substring.
(c) Does and defines the same language. Generate first 6 3
words of each of the language in the lexicographic order.
(d) Build deterministic finite automata (DFA) machine that accept all strings 4
that either start with ‘ab’ or end with ‘ba’.
(e) Build a DFA machine that accepts only those strings that do not end with 4
double letters.
(f) Find a Context Free Grammar (CFG) for a language of the form 4
where x,y,z >=0 and x+y=z.
(g) Using pumping lemma for regular languages show that the language 4
L= { } is not regular.
(h) Show that if L1 and L2 are regular languages then so are L1+L2, L1L2 and 4
L1*.
(i) Construct a PDA for the language { }. 4
(j) Design a right shifting Turing machine. 4
Part B
2 (a) Define regular expression. 2
(b) Build a regular expression for all strings in which b’s occur in clumps of an 3
odd number at a time such as ab, ba, abbb, bbba, abaabbb,……..
(c) Build an FA that accepts all strings that have an even length that is not 5
divisible by 6.
3 (a) For languages, L1= and L2= , Construct 6
respective DFA’s and derive the finite automata that define L1 + L2 .
(b) Show that the following context free grammar is ambiguous: 4
4 (a) Convert the following NFA to DFA. 5
a
X2
a b
a, b
- +
X1 X4
b a
X3
(b) Write a regular expression and construct a DFA for the language of all 5
words that have an even number of substrings ‘ab’ in them.
5 (a) Construct a PDA for the language EQUAL. 6
(Language that contains equal number of a’s and b’s no matter where they
are distributed).
(b) Construct a CFG for the language (ba+ab)* 4
6 (a) Prove that a recursive language is also recursively enumerable. 5
(b) Consider the following CFG in Chomsky Normal Form (CNF) 5
Generate the derivation trees for the word
(i) abab
(ii) ababab
State whether the given CFG is ambiguous or not.
7 (a) Design a Turing machine for the language anbncn where . 6
(b) Describe Universal Turing machine. 4
