Cs2303 Theory Of Computation Notes Examples
Cs2303 Theory Of Computation Notes Receivable
Cs2303 Theory Of Computation Notes Calculus

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

3d custom girl evolution mods. K.L.P Mishra & N.Chandrasekaran,“Theory of Computer Science”, PHI Learning. Peter Linz, “Introduction to Automata Theory and Formal Languages”, Narosa Publishing. John C Martin, “Introduction to languages and the theory of computation”, TATA McGraw Hill. Ht vhs to dvd 8.0. CS6503 Theory of Computation Notes free download Anna University CSE TOC Notes Regulation 2013 CS6503 Notes, TOC Unit wise Lecture Notes – CSE 5th Semester. Anna university Notes ece syllabus lecture handwritten notes. Twitter Facebook Google+.

Computer Science and Engineering

(Regulation 2008)

Answer ALL questions

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 Cs2303 Theory Of Computation Notes

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→

Cs2303 Theory Of Computation Notes Examples

1 | SS A→ (8)
(ii) Construct the Turing machine for the language { } 1 | 0 1 ≥ = n L n n . (8)
Or

Cs2303 Theory Of Computation Notes Receivable

(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)

Cs2303 Theory Of Computation Notes Calculus

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