Total No. of Questions 18] [Total No. of Pages 03
M.Sc. DEGREE EXAMINATION, MAY 2017
First Year
COMPUTER SCIENCE
Theory of Automata and Formal Languages
Time 3 Hours Maximum Marks: 70
SECTION A
Answer Any three questions. × 15 45)
Q1) Write a procedure to minimizing the DFA and also minimize the following
DFA
Q2) Construct FA's for the following regular expressions:


Q3) Let G be the grammar as → → → for
the string 'aabbabab', Find
Derivation tree
Rightmost derivation
Leftmost derivation.
Q4) Design push down automata for the language contains equal number of and
equal number of over the alphabets
Q5) Explain about Universal Turing machine, counter machine and church
hypothesis.
SECTION B
Answer Any Five questions. × 4
20)
Q6) Convert the NDA to equivalent DFA for each of the following:
Q7) Explain about moore and mealy machines.
Q8) Show that is perfect square} is not regular.
Q9) Eliminate all the
−productions from the following CFG:
→ →
→

Q10) Covert the following CFG into CNF grammar.
→
Q11) Describe the closure properties of CFL.
Q12) Design Turing machine for the language L {anbn|n 1}.
Q13) Show that "Post Correspondence Problem is un-decidable".
SECTION C
Answer all questions. × 1
Q14) Define DFA.
Q15) What is meant by ambiguity in CFG?
Q16) Define homomorphism.
Q17) What is meant by nullable and unit productions?
Q18) Define context sensitive language.