Total No. of Questions 18] [Total No. of Pages 02
M.Sc. DEGREE EXAMINATION, MAY 2018
First Year
COMPUTER SCIENCE
Theory of Automata and Formal Languages
Time 3 Hours Maximum Marks :70
SECTION A
Answer any three questions. x 15 45)
Q1) Construct DFA for the language L w|mod 3
Prove that "Let L be the language accepted by NFA then there exists it
accepts DFA".
Q2) Give the regular expression for the following DFA and also give right
linear grammar and left linear grammar:
Q3) Find the CFG with no useless symbols equivalent to the following
grammar.
S → AB B→ BC AB, A→a,C →aB b
Construct GNF grammar for the following CFG:
S → AA| A→SS a
Q4) Design pushdown automata for the language: L i j k a b c i j k trace it
for String "bbbbbccccc".
Q5) Design Turing machine for the language L n n a b n and also give
different types of Turing machines.
SECTION B
Answer any five questions. x 4 20)
Q6) Differentiate Moore and Mealy machines.
Q7) Find regular expression for following over the alphabet
Language of all strings containing exactly two 0's.
ii) Language of all strings that begins or ends with 00 or 11.
Q8) Prove that regular language is closed under union and intersection.
Q9) Construct NFA for the regular expression
Q10) What is meant by ambiguous grammar? Show that S →aSb bSa SS |ε
ambiguous Grammar.
Q11) Show that the language L p a p is prime number} is not regular.
Q12) Show that "Post Correspondence Problem is un-decidable".
Q13) Briefly explain about Church hypothesis.
SECTION C
Answer all questions. x 1
Q14) Construct the DFA for the language L n aba n
Q15) Define PDA.
Q16) Define Chomsky Normal form.
Q17) What unit production?
Q18) What is decidable problem?