2023 2024 Student Forum > Management Forum > Main Forum

 
  #2  
15th December 2014, 09:15 AM
Super Moderator
 
Join Date: Apr 2013
Re: Theory of Computation CSE Department Question papers

You are looking for Anna university CSE Department Theory of Computation exam model paper, I am giving here:
Anna Univ CSE Dept DTC Exam paper
PART A — (10 x 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.

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)


Quick Reply
Your Username: Click here to log in

Message:
Options

Thread Tools Search this Thread



All times are GMT +5. The time now is 05:58 PM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.
SEO by vBSEO 3.6.0 PL2

1 2 3 4