THEORY OF COMPUTATION
Time: 3 hours
Marks : 60
Instruc tions:
Answer any Six questions each carry 10 marks.
1. (a) State and prove the principle of mathematical induction using two
examples other than Q no. lb.
(b) Prove using mathematical induction ‘For every n > 1 the number of
subsets of {1, 2, ....n} is 2n.
2. (a) Prove that the language accepted by any Finite Automation is
regular.
(b) Construct a minimal DFA for the regular expression
(( ) / *) *
*
ab b ab
3. (a) Write short notes on Pumping lemma.
(b) State and Prove the properties of Context Free languages.
4. (a) Distinguish between deterministic Pushdown Automata and
Non-deterministic Pushdown Automata.
(b) Let G be the Context free grammar with productions
S
aS ASbS c
→
/
/
Let G 1 be the Context free grammar with productions
S
T U T
aTbT c U
aS aTbU
1
1
→
→
→
/
/
/
(i) Show that G is ambiguous.
(ii) Show that G and G 1 generate the same language.
(iii) Show that G 1 is unambiguous.
5. (a) Construct a Turing machine to accept a palindrome over |
|
a b
⋅ .
Draw the transition diagram and trace the moves for the any string.
(b) Does every Turing machine computes a partial function? Explain.
6. State the Rice’s theorem and post correspondence problem and give the
proof of Rice’s theorem.
7. (a) Show that a language L ⊆ Σ
* is recursively enumerable (i.e. can be
accepted by some TM) if and only if L can be enumerated by some
TM.
(b) Distinguish halting problem and Unsolvability.
University Question Papers
323