Cs2303 theory of computation all anna University question papers

Cs2303 theory of computation all anna University question papers fifth semester computer science and engineering

1. Reg. No. :


B.E. / B.Tech. DEGREE EXAMINATION, NOVEMBER / DECEMBER 2010
Fifth Semester
Computer Science and Engineering
CS2303 – THEORY OF COMPUTATION
(Regulation 2008)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (��×�=�� marks)
1. What is inductive proof?
2. Find the set of strings accepted by the finite automata.
3. Give the regular expression for set of all strings ending in 00.
4. State pumping lemma for regular set.
5. Write down the context free grammar for the language L = {a
n
b
n
| ≥1 }.
6. Is the grammar E → E + E | id is ambiguous? Justify.
7. What is Turing machine?
8. Is the language L = {a
n
b
n
c
n
| �≥1 }is context free? Justify.
9. What is recursively enumerable language?
10. Mention the difference between decidable and undecidable problems.

Part B – (5 ×�??????=??????� marks)

11. (a) (i) Construct the deterministic finite automata for accepting the set of all strings with
three consecutive 0‟s. (10)

(ii) Distinguish NFA and DFA with examples. (6)

Or

(b) (i) Consider the finite automata transition table shown below with {Q, Σ, δ, q0, F}
States
Inputs
0 1
q0 q2 q1
q1 q3 q0
q2 q0 q3
q3 q1 q2

Find the language accepted by the finite automata. (10)

(ii) What is ε-closure (q)? Explain with an example. (6)


12. (a) (i) Let r be a regular expression. Prove that there exists an NFA with ε -transitions
that accepts L(r). (10)

(ii) Is the language L = {a
n
b
n
| ≥1 } is regular? Justify. (6)
Question Paper Code : xxxxx

2. Or

(b) (i) Construct the minimal DFA for the regular expression (b|a)*baa. (10)

(ii) Prove that regular sets are closed under substitution. (6)

13. (a) (i) Let G be the grammar
S → aB | bA
A → a | aS | bAA
B → b | bS | aBB
for the string baaabbabba. Find leftmost derivation, rightmost derivation and
parse tree. (9)

(ii) What is deterministic PDA? Explain with an example. (7)

Or

(b) (i) Construct the PDA for the Language L = {wcw
R
| w is in (0+1)*}. (10)

(ii) Let L is a context free language. Prove that there exists a PDA that accepts L. (6)


14. (a) (i) Obtain a Greibach normal form grammar equivalent to the context free grammar
S → 0 | AA
A→ 1 | SS (8)

(ii) Construct the Turing machine for the language L = {a
n
b
n
| ≥1 }. (8)

Or

(b) (i) Explain the closure properties of context free languages. (8)

(ii) Construct the Turing machine for the language L = {ww
R
| w is in (0+1)*}. (8)


15. (a) (i) Explain the difference between tractable and intractable problems with examples.
(10)
(ii) What is halting problem? Explain. (6)

Or

(b) (i) Explain post correspondence problem with an example. (8)

(ii) Explain any four NP-Complete problems. (8)





All the Best – No substitute for hard work.
Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).

3. Reg. No. :


B.E. / B.Tech. DEGREE EXAMINATION, APRIL / MAY 2011
Fifth Semester
Computer Science and Engineering
CS2303– THEORY OF COMPUTATION
(Regulation 2008)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (��×�=�� marks)
1. Differentiate between proof by contradiction and proof by contra positive.
2. Construct a DFA for the language over {0, 1}* such that it contains “000” as a substring.
3. Prove that the complement of a regular language is also regular.
4. Prove by pumping Lemma, that the language 0
n
1
n
is not regular.
5. Construct a CFG over {a,b} generating a language consisting of equal number of a‟s and b‟s.
6. Is the language of Deterministic PDA and Non - Deterministic PDA same? Justify.
7. What is the height of the parse tree to represent a string of length „n‟ using Chomsky normal
form?
8. Construct a Turing machine to compute „n mod 2‟ where n is represented in the tape in unary
form consisting of only 0‟s.
9. Prove that the complement of recursive language is recursive.
10. Define the classes P and NP.

Part B – (5 ×�??????=??????� marks)

11 (a) (i) Show that a connected graph G with n vertices and n-1 edges (n>2) has at least
one leaf. (6)
(ii) Convert the following ε-NFA to a DFA using subset construction algorithm. (10)
ε a b c
→p Φ {p} {q} {r}
q {p} {q} {r} Φ
*r {q} {r} Φ {p}
Or
(b) (i) Prove that there exists a DFA for every ε - NFA . (8)
(ii) Show that the maximum number of edges in a graph (with no self-loops or
parallel edges) is given by (n(n-1))/2, where n is the number of nodes. (6)

12 (a) (i) Construct Regular expression for the following DFA using Kleene‟s theorem.(10)
0 1
→*A A B
B C B
C A B

(ii) Construct a ε - NFA for the following Regular expression. (6)
(0+1)*(00+11)(0+1)*
Or
Question Paper Code : 11262

4. (b) (i) Construct a minimized automata for the following automata to define the same
language. (10)
a b
→q0 q1 q0
q1 q0 q2
q2 q3 q1
*q3 q3 q0
q4 q3 q5
q5 q6 q4
q6 q5 q6
q7 q6 q3

(ii) Prove that “If two states are not distinguished by table filling algorithm then the
states are equivalent”. (6)

13 (a) (i) Prove that if „w‟ is a string of a language then there is a parse tree which yield „w‟
and also prove that if A => w then it implies that „w‟ is a string of the language L
defined by a CFG. (6)
(ii) Prove that the expression grammar is ambiguous. (4)
� → �+�|�∗�|(�)|�
(iii) Construct a CFG for the set �
�
�
�
�
�
�≠� or j≠�}. (6)
Or
(b) (i) Prove that if there exists a PDA that accepts by final state then there exists an
equivalent PDA that accepts by Null state. (8)
(ii) Construct a PDA to accept language 0
n
1
2n
by empty stack. (8)


14 (a) (i) Prove that every grammar with ε productions can be converted to an equivalent
grammar without ε productions. (4)
(ii) Reduce the following grammar to Chomsky normal form. (8)
?????? → � | ��� � → �� | �� | ∈ � → ��� | ∈
(iii) Convert the following grammar to Greibach normal form. (4)
?????? → � | �� � → � | �� � → � � → �.
Or
(b) (i) Construct a Turing machine to accept the language a
n
b
n
c
n
. (8)
(ii) Construct a Turing machine to perform proper subtraction. (8)


15 (a) Prove that the universal language Lu is recursively enumerable but not recursive. Also
prove that the language Ld is not recursive or recursively enumerable. (12+4)
Or
(b) Prove that PCP problem is undecidable and explain with an example. (10+6)


All the Best – No substitute for hard work.
Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).

5. Reg. No. :


B.E. / B.Tech. DEGREE EXAMINATION, NOVEMBER / DECEMBER 2011
Fifth Semester
Computer Science and Engineering
CS2303 – THEORY OF COMPUTATION
(Regulation 2008)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (��×�=�� marks)
11. What is structural induction?
12. State the difference between NFA and DFA.
13. Construct a DFA for the following :
(a) All strings that contain exactly 4 zeros.
(b) All strings that don't contain the substring 110.
14. Is the set of strings over the alphabet {0} of the form 0
n
where n is not a prime is regular?
Prove or disprove.
15. Is the grammar below ambiguous S → SS | (S) | S(S)S | E?
16. Convert the following grammar into an equivalent one with no unit productions and no
useless symbols S → ABA A → aAA|aBC|bB B → A|bB|Cb C → CC|cC.
17. Design a TM that accepts the language of odd integers written in binary.
18. State the two normal forms and give an example.
19. How to prove that the Post Correspondence Problem is Undecidable.
20. Show that any PSPACE-hard language is also NP-hard.

Part B – (5 ×�??????=??????� marks)

11 (a) (i) Prove that 2 is not rational. (8)

(ii) Construct a DFA accepting all strings w over {0, 1} such that the number of 1’s in
w is 3 mod 4. (8)
Or
(b) Construct a minimized DFA from the regular expression (�+ �)�(� + �)∗. Trace
for a string � = ����. (16)


12 (a) State and explain the conversion of DFA into regular expression using Arden's
theorem. Illustrate with an example. (16)

Or

(b) (i) What are the closure property of regular sets? (8)

(ii) Define regular expression. Show that
(1+00*1)+(1+00*1)(0+10*1)*(0+10*1)=0*l(0+10*l)* (8)
Question Paper Code : 66281

6. 13. (a) (i) Is NPDA (Nondeterministic PDA) and DPDA (Deterministic PDA) equivalent?
Illustrate with an example. (8)
(ii) What are the different types of language acceptances by a PDA and define them.
Is it true that the language accepted by a PDA by these different types provides
different languages? (8)
Or

(b) (i) Convert the grammar ??????→�??????�|�,�→�??????�|??????|€ to a PDA that accepts the same
language by empty stack. (10)
(ii) If ??????→�??????�|���,�→���,�→�� is the context free grammar. Determine the
context free language. (6)


14. (a) (i) State the techniques for Turing machine construction? Illustrate with a simple
language. (6)
(ii) Explain the different models of Turing machines. (10)

Or

(b) (i) What are the closure properties of CFL? State the proof for any two properties.(8)
(ii) State the Pumping lemma for CFLs. What is its main application? Give two
examples. (8)


15. (a) (i) State the halting problem of TMs. Prove that the halting problem of Turing
Machine over {0, 1}* as unsolvable. (8)
(ii) Let Σ = {a, b}*. Let A and B he lists of three strings as given below:
�=(�,���3,��) �={�3,�� ,�}
Does this instance of PCP have a solution? Justify your answer. (8)

Or

(b) Write short notes on:
(i) Recursive and recursively enumerable languages. (8)
(ii) NP hard and NP complete problems. (8)









All the Best – No substitute for hard work.
Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).

7. Reg. No. :


B.E. / B.Tech. DEGREE EXAMINATION, MAY / JUNE 2012
Fifth Semester
Computer Science and Engineering
CS2303/CS53/10144/CS1303/CS504 – THEORY OF COMPUTATION
(Regulation 2008)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (��×�=�� marks)
21. What is proof by contradiction?
22. Define ε – closure (q) with an example.
23. Construct NFA for the regular expression a* b*.
24. Is the regular set closed under complementation? Justify.
25. Specify the use of context free grammar.
26. Define parse tree with an example.
27. State pumping lemma for CFL.
28. What is Chomsky normal form?
29. Mention the difference between P and NP problems.
30. What is meant by recursively enumerable language?


Part B – (5 ×�??????=??????� marks)

11 (a) (i) Prove by mathematical induction on � that �
�
�=0=
�(�+1)
2
(6)
(ii) Construct a DFA accepting binary strings such that the third symbol from the
right end is ⊥. (10)

Or

(b) (i) Convert an NFA without ε – transition for the NFA given below. (8)

(ii) Construct an NFA accepting binary strings with two consecutive o‟s. (8)


ε
q0 q1

0 1
Question Paper Code : 10270

8. 12 (a) (i) Obtain minimized finite automata for the regular expressions (b/a)*baa. (10)
(ii) Prove that there exists an NFA with ε – transitions that accepts the regular
expression ??????. (6)

Or

(b) (i) Which of the following languages is regular? Justify (8)
(1) L = {a
n
b
m
/ �,�≥ ⊥}
(2) L = {a
n
b
n
/ �≥ ⊥}.

(ii) Obtain the regular expressions for the finite automata. (8)

13 (a) (i) Is the grammar �→�+�/�∗�/�� ambiguous? Justify. (6)
(ii) Find the context free languages for the following grammars. (10)
S → asbs / bsas / ε
S → asb / ab
Or

(b) (i) Construct PDA for the language L = {��
R
| � is in (a+b)*}. (10)
(ii) Discuss the equivalence between PDA and CFG. (6)


14 (a) (i) Find the Greibach normal form for the grammar. (10)
S → AA / ⊥
A → SS / θ
(ii) Explain any two higher level techniques for Turing machines construction. (6)

Or

(b) (i) Construct Turing machines for �={ ⊥
�
??????
�
⊥
�
/ �≥⊥ }. (8)
(ii) Discuss the closure properties of CFLs. (8)


15 (a) (i) Explain undecidability with respect to post correspondence problem. (8)
(ii) Discuss the properties of recursive languages. (8)

Or

(b) (i) Explain any two undecidable problems with respect to Turing Machine. (8)
(ii) Discuss the difference between NP-complete and NP-hard problems. (8)




All the Best – No substitute for hard work.
Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).

b b
start q1 q3

q2

a a

9. Reg. No. :


B.E. / B.Tech. DEGREE EXAMINATION, NOVEMBER / DECEMBER 2012
Fifth Semester
Computer Science and Engineering
CS2303/CS53/10144/CS504/CS1303 – THEORY OF COMPUTATION
(Regulation 2008/2010)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (��×�=�� marks)
31. Define:
a) Finite Automaton (FA)
b) Transition diagram.
32. State the principle of induction.
33. Give regular expressions for the following.
LI = set of all strings of 0 and 1 ending in 00.
L2 = set of all strings of 0 and 1 beginning with 0 and ending with 1.
34. Differentiate regular expression and regular language.
35. What is an ambiguous grammar? Give example.
36. What are the different types of language accepted by a PDA and define them?
37. State the pumping lemma for CPIs.
38. What are the applications of Turing Machine?
39. When we say a problem is decidable? Give an example of undecidable problem.
40. What is recursively enumerable language?

Part B – (5 ×�??????=??????� marks)

11 (a) (i) Explain the different forms of proof with examples. (8)

(ii) Provo that, if L is accepted by an NFA with ε-transitions, then L is accepted by an
NFA without ε-transitions. (8)

Or


(b) (i) Prove that if n is a positive integer such that n mod 4 is 2 or 3 then n is not a
perfect square. (6)

(ii) Construct a DFA that accept the following language.
{ x € {a, b}: |x|a = odd and |x|b = even }. (10)


Question Paper Code : 11278

10. 12 (a) (i) Using pumping lemma for the regular sets, prove that the language
L = { a
m
b
n
| �>� } is not regular. (10)

(ii) Prove any two closure properties of regular languages. (6)
Or
(b) Construct a minimized DFA that can be derived from the following regular expression
0*(01)(0/111)*. (16)


13 (a) (i) Consider the following grammar for list structures : (10)
S → a/^/(T) T → T, S | S.
Find left most derivation, rightmost derivation and parse tree for
(((a , a) , ^ (a)),a).

(ii) Construct the FDA accepting the language {(ab)
n
| �≥1}by empty stack. (6)
Or
(b) (i) Construct a transition table for PDA which accepts the language
L = {a
2n
b
n
| �≥1}. Trace your PDA for the input with n = 3. (10)

(ii) Find the PDA equivalent to the given CFG with the following productions.
S → A, A → BC, B → ba, C → ac. (6)


14 (a) (i) Convert the following grammar into CNF
S → cBA, S → A, A → cB, A→ AbbS, B → aaa. (10)

(ii) State and prove the pumping lemma for CFL. (6)
Or
(b) (i) Design a Turing machine which reverses the given string {abb}. (8)

(ii) Write briefly about the programming techniques for TM. (8)


15 (a) (i) If L1 and L2 are recursive language then L1 U L2 is a recursive language. (6)

(ii) Prove that the halting problem is undecidable. (10)
Or
(b) (i) State and prove the post's correspondence problem. (10)

(ii) Write a note on NP problems. (6)





All the Best – No substitute for hard work.
Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).

11. Reg. No. :


B.E. / B.Tech. DEGREE EXAMINATION, MAY / JUNE 2013
Fifth Semester
Computer Science and Engineering
CS2303/CS53/10144/CS504 – THEORY OF COMPUTATION
(Regulation 2008/2010)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (��×�=�� marks)
41. What is meant by DFA?
42. Define the term Epsilon transition.
43. What is a regular expression?
44. Name any four closure properties of Regular languages.
45. What is a CFG?
46. Define the term Ambiguity in grammars.
47. What is meant by Greibach Normal Form?
48. List the closure properties of Context Free Languages.
49. What is meant by recursively enumerable language?
50. Define the class NP problem.


Part B – (5 ×�??????=??????� marks)

11 (a) (i) Construct DFA to accept the language. (10)
� = { � | � is of even length and begins with 11 }

(ii) Write a note on NFA and compare with DFA. (6)

Or

(b) (i) Convert the following NFA to a DFA. (10)
δ a b
p {p} {p, q}
q {r} {r}
r {ϕ} { ϕ }

(ii) Discuss on the relation between DFA and minimal DFA. (6)


Question Paper Code : 21308

12. 12 (a) (i) Discuss on regular expressions (8)
(ii) Discuss in detail about the closure properties of regular languages. (8)

Or

(b) (i) Prove that the following languages are not regular. (8)
(1) {O
2n
| �≥1}
(2) {a
m
b
n
a
m+n
| �≥1 and �≥1}
(ii) Discuss on equivalence and minimization of automata. (8)


13 (a) (i) Explain about Parse trees. For the following grammar (8)
S → aB | bA
A → a | aS | bAA
B → b | bS | aBB
For the string aaabbabbba, Find
(1) Leftmost derivation
(2) Rightmost derivation
(3) Parse tree.
(ii) Construct PDA for the language L = {��
R
| � in (a+b)*}. (8)
.
Or

(b) Explain in detail about equivalence of Pushdown automata and CFG. (16)


14 (a) (i) Construct the following grammar in CNF (8)
A → BCD | b
A → Yc | d
C → gA| c
D → dB | a
Y → f.
(ii) Discuss about programming techniques for Turing machines. (8)

Or

(b) (i) Explain about the closure properties of CFL. (8)
(ii) Explain in detail about Pumping lemma for CFL. (8)


15 (a) (i) Explain about “A language that is not Recursively Enumerable”. (8)
(ii) Prove Lne is recursively enumerable. (8)

Or

(b) (i) Discuss on undecidable problems about Turing Machine. (10)
(ii) Explain about the PCP. (6)



All the Best – No substitute for hard work.
Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).

13. Reg. No. :


B.E. / B.Tech. DEGREE EXAMINATION, NOVEMBER / DECEMBER 201 3
Fifth Semester
Computer Science and Engineering
CS2303/CS53/10144/CS504/CS1303 – THEORY OF COMPUTATION
(Regulation 2008/2010)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (��×�=�� marks)
51. Draw the transition diagram (automata) for an identifier.
52. What is a non deterministic finite automaton?
53. State the pumping lemma for regular languages.
54. Construct NFA equivalent to the regular expression : (0+1)01.
55. Construct the CFG for the language L = { a
n
�
n
| �≥1 }.
56. Compare NFA and PDA.
57. What are the closure properties of CFL?
58. List out the different techniques for Turing Machine construction.
59. What are (a) recursively enumerable languages (b) recursive sets?
60. What is universal Turing machine?

Part B – (5 ×�??????=??????� marks)

11 (a) (i) Explain steps in conversion of NFA to DFA. Convert the following NFA to DFA.
(8)

(ii) Prove that, if L is accepted by an NFA with ε transition, then L is accepted by an
NFA without ε transition. (8)
Or
(b) (i) Prove the equivalence of NFA and DFA using subset construction. (8)
(ii) Give deterministic finite automata accepting the following languages over the
alphabet. (8)
(1) Number of 1‟s is a multiples of 3.
(2) Number of 1‟s is not a multiples of 3.

12 (a) (i) Convert the following NFA into regular expression. (8)

(ii) Discuss the closure properties of regular languages. (8)
Or
(b) (i) Discuss the applications of finite automaton. (6)
0+1 0
start A C

B

0, 1
0, 1
D

1 0
start q0 q2

q1

0, 1
Question Paper Code : 31308

14. (ii) Using pumping lemma for regular sets prove that the language
L = {0
�
1
�
0
�+�
| �≥1��� �≥1}) is not regular. (10)


13. (a) (i) Convert the following grammar into GNF. (8)
S → XY1 / 0
X → 00X / Y
Y → 1X1
(ii) Give formal pushdown automata that accepts { ���
R
| � �� 0+1 ∗ } by empty
stack. (8)
Or
(b) (i) Show that the following grammars are ambiguous. (6)
{ S → aSbS / bSaS / λ } and
{ S → AB / aaB, A → a / Aa, B → b }
(ii) Prove the equivalence of PDA and CFL. (10)

14. (a) (i) Explain Turing machine as a computer of integer functions with an example. (10)
(ii) Remove ε productions from the given grammar. (6)
Or
(b) Write short notes on the following:
(i) Two-way infinite tape TM. (8)
(ii) Multiple tracks TM. (8)

15. (a) (i) Write the classes and definition of NP problems. (6)
(ii) Prove that for two recursive languages L1 and L2 their union and intersection is
recursive. (10)
Or
(b) (i) Prove that if a language is recursive if and only if it and its complement are both
recursively enumerable. (8)
(ii) Explain about undecidability of PCP. (8)


















All the Best – No substitute for hard work.
Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).

15. Reg. No. :


B.E. / B.Tech. DEGREE EXAMINATION, MAY / JUNE 2014
Fifth Semester
Computer Science and Engineering
CS2303/CS53/10144/CS504 – THEORY OF COMPUTATION
(Regulation 2008/2010)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (��×�=�� marks)
61. What is a finite automaton?
62. Enumerate the difference between DFA and NFA.
63. Construct a finite automaton for the regular expression 0*1*
64. Mention the closure properties of regular languages.
65. Construct a CFG for the language of palindrome strings over {a, b}.
66. What do you say a grammar is ambiguous?
67. State pumping Lemma for context free languages.
68. Define a turing machine.
69. When a language is said to be recursively enumerable?
70. Define the classes P and NP.

Part B – (5 ×�??????=??????� marks)
11 (a) (i) Prove the following by the principle of induction: �
2�
�=1=
� �+1 (2�+1)
6
. (8)
(ii) Construct a DFA that accepts all strings on {0, 1} except those containing the
substring 101. (8)
Or
(b) (i) Construct a non-deterministic finite automaton accepting the set of strings over
(�,�) ending in aba. Use it to construct a DFA accepting the same set of strings.
(10)
(ii) Construct NFA with ∈ moves which accepts a language consisting the strings of
any number of a's, followed by any number of b's, followed by any number of c's.
(6)
12 (a) (i) Design a finite automaton for the regular expression (0+1)*(00+11)(0+1*). (8)
(ii) Prove that L ={0
�
2
/ i is an integer; �≥1 } is not regular. (8)
Or
(b) (i) Prove that the class of regular sets is closed under complementation. (6)
(ii) Minimize the finite automaton shown in figure below and show both the given
and the reduced one are equivalent. (10)
Question Paper Code : 51348

16. 13 (a) (i) If G is a grammar S → SbS / a, show that G is ambiguous. (6)
(ii) Let M= ({q0, q1}, {0, 1}, {x, z0}, δ, q0, z0, ϕ) where δ is given by (10)
δ(q0,0, z0) = {( q0, xz0)}
δ(q1,1, x) = {( q1, ∈)}
δ(q0,0, x) = {( q0, xx)}
δ(q1, ∈, x) = {( q1, ∈)}
δ(q0, 1, x) = {( q1, ∈)}
δ(q1, ∈, z0) = {( q1, ∈)}
Construct a CFG for the PDAM.
Or
(b) (i) Construct a Push down Automata to accept the language L = {a
n
b
n
/ �≥1} by
empty stack and by final state. (10)
(ii) Convert the grammar S → 0S1 / A; A → 1A0 / S / ∈ into a PDA that accepts the
same language by empty stack. Check whether 0101 belongs to N(M). (6)

14 (a) (i) Define Chomsky normal form. Find an equivalent grammar in CNF for the
grammar G = ({S, A, B}, {a, b}, P, S) with productions S → bA / aB;
A → bAA / aS / a; B → aBB / bS / b. (8)
(ii) Show that the Language L = {a
i
b
i
c
i
/ �≥1} is not contest free. (8)
Or
(b) (i) Design a Twinning machine to accept the language L = {0
n
1
n
/ �≥1} and
simulate its action on the input 0011. (12)
(ii) Write short note on checking off symbols (4)

15 (a) Define diagonalization language. Show that the language Ld is not a recursively
enumerable language. (16)
Or
(b) (i) Prove that the universal language is recursively enumerable. (10)
(ii) Define Post correspondence problem. Let Σ = {0, 1}. Let A and B be the lists of
three strings, each defined as
List A List B
i wi xi
1 1 111
2 10111 10
3 10 0
Does this PCP have a solution.

All the Best – No substitute for hard work.
Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).

q0
1
1
start
q1

q4

q3

1
q2

1
0
0,1
0
0 0

17. Reg. No. :


B.E. / B.Tech. DEGREE EXAMINATION, NOVEMBER / DECEMBER 201 4
Fifth Semester
Computer Science and Engineering
CS2303/CS53/10144/CS504/CS1303 – THEORY OF COMPUTATION
(Regulation 2008/2010)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (��×�=�� marks)
71. Define Deductive proof.
72. Design DFA to accept strings over Σ = (0,1) with two consecutive 0‟s
73. Prove or disprove that (r + s)* = r* + s* .
74. State the pumping lemma for regular languages.
75. Give the general forms of CNF.
76. Show that CFLs are closed under substitutions.
77. Let G be the grammar S→aB|bA A→a|aS|bAA B→b|S|aBB . For the string aaabbabbba, find
(a) LMD and (b) RMD
78. Define Diagonalization (Ld) Language.
79. Define multitape turing machine.
80. Give examples for NP-complete problems.

Part B – (5 ×�??????=??????� marks)

11 (a) (i) Prove that every tree has 'e' edges and 'e + l' nodes. (6)
(ii) Prove that for every integer is n≥0 the number 4
2n+1
+ 3
n+2
is a multiple of 13. (10)
Or
(b) (i) Let L be a set accepted by a NFA and then prove that there exists a DFA that
accepts L. (10)
(ii) Construct a DFA equivalent to the NFA. M=({a, b, c, d), (0,1), δ, a, {b, d}) where
δ is a defined as (6)
δ 0 1
a {b, d} {b}
b c {b, c}
c d a
d - a


12 (a) Construct a minimized DFA for the RE 10 + (0 +11) 0*1. (16)
Or
(b) (i) Show L ={0
�
2
/ is an integer, �≥1}) is not regular. (6)
(8)
(ii) Explain the DFA minimization algorithm with an example. (10)




Question Paper Code : 91350

18. 13. (a) (i) Write a grammar G to recognize all prefix expressions involving all binary
arithmetic operators. Construct a parse tree for the sentence '-* + abc/de' using G?
(6)
(ii) Show that the following grammar G is ambiguous S → SbS / a. (6)
(iii) Construct a context free grammar for {0
m
1
n
/ 1≤�≤�}. (4)
Or
(b) (i) If L is context free language prove that there exists a PDA M, such that
� = �(�). (8)
(ii) Prove that If L is N(M1) (the language accepted by empty stack) for some PDA
M1, then L is N(M2) (the language accepted by final state) for some PDA M2. (8)


14. (a) (i) Find a grammar G' in CNF form equivalent to G,
S → a AD, A → aB / bAB, B → b, D → d. (6)
(ii) Convert to GNF the grammar G, G = ({A1, A2, A3), {a, b}, P, A1) where P
consists of the following A1→ A2A3, A2→ A3A1 /b, A3 → A1A2 / a . (10)
Or
(b) (i) Design a TM, M to implement the function "MULTIPLICATION" using the
subroutine "COPY'. (12)
(ii) Show that language {0
n
1
n
2
n
/ �≥1} is not context free language. (4)

15. (a) (i) Show that the union of two recursive language is recursive & union of two
recursively enumerable language is recursive. (12)
(ii) Define the language Lu and show that Lu is RE language. (4)
Or
(b) State and Prove Post Correspondence Problem and Give example. (16)
















All the Best – No substitute for hard work.
Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).

19. Reg. No. :


B.E. / B.Tech. DEGREE EXAMINATION, APRIL / MAY 2015
Fifth Semester
Computer Science and Engineering
CS2303/CS53/10144/CS504/CS1303 – THEORY OF COMPUTATION
(Regulation 2008/2010)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (��×�=�� marks)
81. Any set A, B and C, if �∩�=?????? and C B then �∩�=??????. Prove by induction.
82. Prove for every �≥1 by mathematical induction �
2�
�=n n+1 (n+2)/6.
83. Give the English description of the following language (0+10)*1*.
84. Construct NFA-^ for 1*(01)*.
85. Generate CFG for (011+1)*.
86. Construct a parse tree of (a + b)*c for the grammar E → E+E / E*E / (E) / id.
87. Differentiate PDA acceptance by empty stack method with acceptance by final state method.
88. Define – Pumping lemma for CFL.
89. Define RE language.
90. Differentiate recursive and non-recursively languages.

Part B – (5 ×�??????=??????� marks)

11 (a) Design a DFA accept the following strings over the alphabets {0, 1}. The set of all
string that contains a pattern 11. Prove this using mathematical induction.
Or
(b) Design a NFA accepts the following strings over the alphabets {0, 1}. The set of all
string that begin with 01 and ends with 11. Check for the validity of 01111 and 0110
strings.

12 (a) Find the min-state DFA for (0+1)*10.
Or
(b) Find the regular expression of a language that consists of set of string starts with 11 as
well as ends with 00 using Rij formula.

Question Paper Code : 71386

20. 13 (a) Construct a PDA for the given grammar S → aSa | bSb | c.
Or
(b) Construct a PDA for the given language L = { x € {a, b}* | na(x) > nb(x) }.


14 (a) Construct a TM to perform copy operation.
Or
(b) Given the CFG G, find CFG G' in CNF generating the language L(G) – {^}.
S → AACD A → aAb | ^ C → aC | a D → aDa | bDb | ^


15 (a) Explain Post Correspondence Problems and decidable and undecidable problems with
examples.
Or
(b) Explain the class P and NP problems with suitable example.

















All the Best – No substitute for hard work.

Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).

21. Reg. No. :


B.E. / B.Tech. DEGREE EXAMINATION, NOVEMBER / DECEMBER 2015
Fifth Semester
Computer Science and Engineering
CS2303/CS53/10144/CS504/CS1303 – THEORY OF COMPUTATION
(Regulation 2008/2010)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (��×�=�� marks)
91. Define the term NFA.
92. What is meant by Epsilon transition?
93. List the operators used in the Regular Expression and their precedence.
94. Mention any four Closure properties of Regular Languages.
95. Define the term Parse tree.
96. What is meant by ambiguity in Grammars?
97. Define the term Chomsky Normal Form.
98. List the components of Turing Machine.
99. What is meant by recursively enumerable language?
100. Define PCP.

Part B – (5 ×�??????=??????� marks)

11 (a) (i) Construct DFA to accept the language L ={ w | w is of even length and begins
with 10} (10)
(ii) Discuss on Finite Automata with Epsilon transitions. (6)
Or
(b) (i) Convert the following NFA to a DFA. (10)

0 1
p {p, q} {p}
q {r, s} {t}
r {p, r} {t}
*
s ϕ ϕ
*
t ϕ ϕ

(ii) Discuss on the relation between DFA and Minimal DFA. (6)

12 (a) (i) Explain about Finite Automata and Regular Expressions. (8)
(ii) Discuss about the closure properties of Regular Languages. (8)
Or
(b) (i) Prove that the following languages are not regular. (8)
{0
n
1
m
| �≤� }
{0
n
1
2n
| �≥1 }
(ii) Discuss on equivalence and minimization of Automata. (8)


Question Paper Code : 21386

22. 13 (a) Discuss the following:
(i) CFG and Parse trees. (6)
(ii) Ambiguity in Context Free Grammars with example. (10)
Or
(b) (i) Construct PDA for the language. (10)
L = { ww
R
| w is in {0, 1}
*
}.
(ii) Discuss on deterministic PDA. (6)


14 (a) (i) Construct the following grammar in CNF. (8)
S → ABC | BaB
A → aA | BaC | aaa
B → bBb | a | D
C → CA | AC
D → ε.
(ii) Discuss on Turing Machine. (8)
Or
(b) (i) List and explain the closure properties of CFL. (8)
(ii) Explain in detail about the programming techniques for Turing Machines. (8)


15 (a) (i) Explain about “A language that is not Recursively Enumerable”. (8)
(ii) Prove that Lne is not recursive. (8)
Or
(b) (i) Discuss on undecidable problems about Turing Machine. (10)
(ii) Explain about the universal language. (6)





















All the Best – No substitute for hard work.
Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).

23. Reg. No. :


B.E. / B.Tech. DEGREE EXAMINATION, MAY / JUNE 2016
Fifth Semester
Computer Science and Engineering
CS2303/CS53/10144/CS504/CS1303 – THEORY OF COMPUTATION
(Regulation 2008/2010)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (��×�=�� marks)
101. Prove by mathematical induction that for �≥2, then �
3
−� is always divisible by 3.
102. Give two strings that are accepted and two strings rejected by the following finite
automata M = ({ q0, q1, q2}, {0, 1}, δ , q0, {q1}).

103. Find a string of minimum length in {x, y}* not in the language corresponding to the
given regular expression.
(a) x*(y + xy)*x*
(b) (x* + y*) (x* + y*) (x* + y*)
104. State whether Regular Languages are closed under intersection and complementation.
Give an example for intersection.
105. Show that the context free grammar with the following productions is ambiguous.
G = ({S, A, B}, {a, b}, {S → AB, A → aAB | ab, B → abB | λ}, S)
106. Define Push down Automata.
107. State the advantages of Turing machine over other automata.
108. State the pumping lemma for Context Free languages.
109. Differentiate between recursive and recursively enumerable languages.
110. State the class of P problem with an example.

Part B – (5 ×�??????=??????� marks)

11 (a) Use mathematical induction to solve the problem of Fibonacci series and examine
the relationship between recursive definition and proof by induction. Also state
the inductive proofs. (16)
Or
(b) State the Thompson construction algorithm and subset construction algorithm.
Construct finite automata for generating any float point number with an
exponential factor for example numeric value of the form 1.23 e
-10
. Trace for a
string. (16)


12 (a) Design a minimized DFA by converting the following regular expression to NFA,
NFA-λ and to DFA over the alphabet Σ = {a, b, c}*. RE=a(a+b+c)* (a+b+c). (16)
Or

0, 1 0, 1
start
q0 q1

q2

1 0
Question Paper Code : 21386

24. (b) (i) Determine whether the following languages are regular or not with proper
justification. (8)
(i) L1 = { a
n
��
3n
| �≥0 }
(ii) L2 = { a
5n
| �≥0 }
(ii) Construct Deterministic finite Automata that recognize the regular expression
defined over the alphabet Σ = {0, 1}. RE = (1 + 110)*0. Trace for a string
acceptance and rejection. (8)


13 (a) Consider the following grammar:
E → E + T | T
T → T * F | F
F → (E) | id
(i) Give a rightmost derivation and leftmost derivation for the sentence
�=��∗(��+��)∗��. (8)
(ii) Is the Grammar Ambiguous? Justify. (4)
(iii) Construct the parse tree for the sentence in 13 (a) (i). (4)

Or
(b) (i) Differentiate between Deterministic Push down Automata and Non-Deterministic
Push down Automata. (6)
(ii) Construct Push down Automata to recognize the grammar G with following
productions and trace for a string of acceptance and rejection. (10)
S → aSA | €
A→ bB | cc
B→ bd | €


14 (a) (i) Define the two normal forms that are to be converted from a Context Free
grammar (CFG). Convert the following CFG to Chomsky normal forms: (4+6)
S → A | B | C A → aAa | B
B → bB | bb C → aCaa | D
D → baD | abD | aa
(ii) Convert the following CFG G to Greibach normal form generating the same
language. (6)
S → ABA A → aA | λ B → bB | λ
Or
(b) (i) Design a Turing machine to recognize the language L = { a
n
��
n
| �≥0 }. (12)
(ii) State the closure properties of Context free languages. (4)


15 (a) What are the undecidable problems? Explain the same using Post Correspondence
Problem (PCP). Does a PCP solution exist for the following set? (16)
(10, 101), (01, 100), (0, 10), (100, 0), (1, 010)
Or
(b) (i) State any four applications of NP complete problems. (10)
(ii) Prove that if L1 and L2 are Recursively Enumerable language over Σ, then
L1 ∪ L2 and L1 ∩ L2 are also Recursively Enumerable. (6)


All the Best – No substitute for hard work.
Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).

25. Reg. No. :


B.E. / B.Tech. DEGREE EXAMINATION, MAY / JUNE 2016
Fifth Semester
Computer Science and Engineering
CS6503 THEORY OF COMPUTATION
(Regulation 2013)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (��×�=�� marks)
111. Draw a non-deterministic finite automata to accept strings containing the substring 0101.
112. State the pumping lemma for regular languages.
113. What do you mean by null production and unit production? Give an example..
114. Construct a CFG fro set of strings that contain equal number of a‟s and b‟s over Σ={a,
b}.
115. Does a Push down Automata have memory? Justify.
116. Define Push down Automata.
117. What are the differences between a Finite automata and a Turing machine?
118. What is Turing machine?
119. When is a Recursively Enumerable language said to be Recursive?
120. Identify whether „Tower of Hanoi‟ problem is tractable or intractable. Justify your
answer.

Part B – (5 ×�??????=??????� marks)

11 (a) (i) Construct a NFA that accepts all strings hat end in 01. Give its transition table and
extend transition function for the input string 00101. Also construct a DFA for the
above NFA using subset construction method. (10)
(ii) Prove the following by principle of induction. �
2�
�=1=
� �+1 (2�+1)
6
. (6)
Or
(b) (i) What is Regular Expression? Write a regular expression for set of strings that
consists of alternating 0‟s and 1‟s. (8)
(ii) Write and explain the algorithm for minimization of a DFA. Using the above
algorithm minimize the following DFA. (8)

A
0 1 start
B C D
0
1
0
E
1 1
F G D
0
0
0
1
1
1
1
0
0
Question Paper Code : 57255

26. 12 (a) (i) Construct a reduced grammar equivalent to the grammar G = (N, T, P, S) where,
N = {S, A, C, D, E} (6)
T = {a, b}
P = { S → aAa, A → Sb, A → bCC, A → DaA, C → abb, C → DD, E → aC,
D → aDA}.
(ii) When is a grammar said to be ambiguous? Explain with the help of example. (5)
(iii) Show the derivation steps and construct derivation tree for the string „ababbb‟. (5)
by using left most derivation with the grammar.
S → AB | ε
A→ aB
B→ Sb
Or
(b) (i) What is the purpose of normalization? Construct the CNF and GNF for the
following grammar and explain the steps. (10)
S → aAa | bBb | ε
A→ C | a
B→ C | b
C→ CDE | ε
D→ A | B | ab
(ii) Construct a CFG for the regular expression (011+1) (01). (6)


13 (a) (i) Construct a Push down Automata to accept the following language L on Σ={a, b}
by empty stack. �={��
R
| �∈??????
+
}. (10)
(ii) What is an instantaneous description that the PDA? How will you represent it?
Also give three important principles of ID and their transactions. (6)
Or
(b) (i) Explain acceptance by final state and acceptance by empty stack of a Push down
Automata. (8)
(ii) State the pumping lemma for CFL. Use pumping lemma to show that the
language � = {�
i
�
j
�
k
| &#3627408470;<&#3627408471;<&#3627408472;} is not a CFL. (8)


14 (a) (i) Construct a Turing Machine to accept palindromes in an alphabet set Σ={a, b}.
Trace the string “abab” and “baab”. (8)
(ii) Explain the variations of Turing Machine. (8)
Or
(b) (i) Explain Halting problem. Is it solvable or unsolvable problem? Discuss. (8)
(ii) Describe the Chomsky hierarchy of languages with example. What are the
devices that accept these languages? (8)


15 (a) What is Universal Turing Machine? Bring out its significance. Also construct a
Turing Machine to add two numbers and encode it. (16)
Or
(b) What is post correspondence problem (PCP)? Explain with the help of an
example. (16)


All the Best – No substitute for hard work.
Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).

27. Reg. No. :


B.E. / B.Tech. DEGREE EXAMINATION, NOVEMBER / DECEMBER 2015
Fifth Semester
Computer Science and Engineering
CS6503 THEORY OF COMPUTATION
(Regulation 2013)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (&#3627409359;&#3627409358;×&#3627409360;=&#3627409360;&#3627409358; marks)
121. What is finite automaton?
122. Write a Regular Expression for the set of strings over {0, 1} that have at least one.
123. Let G be a grammar with
S → aB|bA,
A → a|aS|bAA,
B → b|bS|aAA.
for the string aaabbabbba, find the left most derivation.
124. Construct the context free grammar representing the set of palindrome over (0+1)*.
125. What are the different ways of language acceptance by a PDA and define them?
126. Convert the following CFG to a PDA.
S → aAA, A → aS|bS|a.

127. Define a Turing Machine.
128. What is a multi-tape turing machine?
129. State when a problem is said to be decidable and give an example of an undecidable
problem.
130. What is a universal language Lu.

Part B – (5 ×&#3627409359;??????=??????&#3627409358; marks)

11 (a) (i) Prove that “A language L is accepted by some DFA if and only if L is accepted
by some NFA”. (10)
(ii) Construct Finite Automata equivalent to the regular expression (ab+a)*. (6)
Or
(b) (i) Consider the following ε – NFA for an identifier. Consider the ε – closure of
each state and find it‟s equivalent DFA. (10)

(ii) State the pumping lemma for Regular languages. Show that the set
&#3627408447;={0
i2
| &#3627408470;≥1}. is not regular. (6)
1 2 3 4
5 6
7 8
9 10 letter ε
letter
digit
ε
ε
ε
ε
ε
ε
ε
ε
Question Paper Code : 27173

28. 12 (a) (i) Let G = (V, T, P, S) be a context free grammar then prove that if the recursive
procedure tells us that terminal string w is in the language of variable A, then
there is a parse tree with root A and yield w. (10)
(ii) Given the Grammar G = (V, Σ, R, E), where
V = {E, D, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, -, *, /, (, )},
Σ = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, -, *, /, (, )}, and R contains the following rules.
&#3627408440; → &#3627408439;|(&#3627408440;)|&#3627408440;+&#3627408440;|&#3627408440;−&#3627408440;|&#3627408440;∗&#3627408440;|&#3627408440;/&#3627408440;
&#3627408439; → 0|1|2|…|9
Find the parse tree for the string 1+2∗3. (6)
Or
(b) (i) Construct a equivalent grammar G in CNF for the grammar G1 where
G1 = ({S, A, B}, {a, b}, { S → ASB|∈, A → aAS|a, B → SbS|A|bb}, S). (10)
(ii) What is an ambiguous grammar? Explain with an Example. (6)


13 (a) (i) Design a Push Down Automata to accept {0
n
1
n
| &#3627408475; > 1}. Draw the transition
diagram for the PDA. Show by instantaneous description that the PDA accepts the
string „0011‟. (10)
(ii) State the pumping lemma for CFL and Show that the language
&#3627408447;={&#3627408462;
n
&#3627408463;
n
&#3627408464;
n
| &#3627408470;≥1} is not a CFL. (6)
Or
(b) (i) Construct PDA to CFG. PDA is given by P = ({p, q}, {0, 1}, {X, Z}, δ , q, z), δ is
defined as δ(p, 1, Z) = {(p, XZ)}, δ(p, ∈, Z) = {(p, ∈)}, δ(p, 1, X) = {(p, XX)},
δ(q, 1, X) = {(q, ∈)}, δ(p, 0, X) = {(q, X)}, δ(q, 0, Z) = {(p, Z)}. (10)
(ii) What are deterministic PDA‟s? Give an Example for Non-deterministic PDA
deterministic PDA. (6)


14 (a) (i) Design a Turing Machine to accept L = {0
n
1
n
| &#3627408475;≥ 1}. Draw the transition
diagram. Also specify instantaneous description to trace the string 0011. (10)
(ii) State and describe the Halting problem for Turing Machine. (6)
Or
(b) (i) Explain the programming techniques for Turing Machine construction. (10)
(ii) Describe the Chomsky hierarchy of languages. (6)


15 (a) (i) Prove that “MPCP reduces to PCP”. (10)
(ii) Discuss about tractable and intractable problems. (6)
Or
(b) (i) State and explain rice theorem. (10)
(ii) Describe about Recursive languages and Recursively Enumerable languages with
examples. (6)





All the Best – No substitute for hard work.
Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).