CS2303 THEORY OF COMPUTATION NOVEMBER/DECEMBER 2010 ANNA UNIVERSITY QUESTION PAPER QUESTION BANK IMPORTANT QUESTIONS 2 MARKS AND 16 MARKS

CS2303 THEORY OF COMPUTATION NOVEMBER/DECEMBER 2010  ANNA UNIVERSITY QUESTION PAPER QUESTION BANK IMPORTANT QUESTIONS 2 MARKS AND 16 MARKS 

CS2303 THEORY OF COMPUTATION NOVEMBER/DECEMBER 2010  ANNA UNIVERSITY QUESTION PAPER QUESTION BANK IMPORTANT QUESTIONS 2 MARKS AND 16 MARKS 

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2010

Fifth Semester

Computer Science and Engineering

CS 2303 — THEORY OF COMPUTATION

(Regulation 2008)

Time : Three hours Maximum : 100 Marks

Answer ALL questions

PART A — (10 × 2 = 20 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 { } 1 | ≥ = n b a L n n .
6. Is the grammar id | E E E + → is ambiguous? Justify.
7. What is Turing machine?
8. Is the language { } 1 | ≥ = n c b a L n n n is context free? Justify.
9. What is recursively enumerable language?
10. Mention the difference between decidable and undecidable problems.
Question Paper Code : 53106

PART B — (5 × 16 = 80 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
{ } 0 q F =
States Inputs
0 1
0 q 2 q 1 q
1 q 3 q 0 q
2 q 0 q 3 q
3 q 1 q 2 q
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 ( ) r L . (10)
(ii) Is the language { } 1 | ≥ = n b a L n n is regular? Justify. (6)
Or
(b) (i) Construct the minimal DFA for the regular expression ( ) . * | baa a b
(10)
(ii) Prove that regular sets are closed under substitution. (6)
13. (a) (i) Let G be the grammar
bA aB S | →
bAA aS a A | | →
aBB bS b B | | →
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 ( ) { } ∗ + = 1 0 in is |w wcw L R .
(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
0 | AA S→
1 | SS A→ (8)
(ii) Construct the Turing machine for the language { } 1 | 0 1 ≥ = n L n n . (8)
Or
(b) (i) Explain the closure properties of context free languages. (8)
(ii) Construct the Turing machine for the language
( ) { } ∗ + = 1 0 in is |w ww L R . (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)