theory of computations important questions

Important Questions in Theory Of Computations CS2303 CS 2303 subject for NOV/DEC 2011 ANNA UNIVERSITY EXAMINATIONS FOR THIRD 3RD YEAR CSE Students

CS2303 – Theory Of Computations Important Questions For V SEMESTER CSE

UNIT I

1.      Consider the following ε–NFA. Compute the ε–closure of each state and find it’s equivalent DFA.                                                                                                  

	ε	A	b	C
p	Ф	{p}	{q}	Ф
q	{p}	{q}	{r}	Ф
*r	{q}	{r}	ф	{p}

2.      Construct a NFA over the alphabet {0,1} that accepts all strings end in 01

3.      For the finite state machine M given in the following table, test whether the strings     101101,11111 are accepted by M.

4.      Consider the following ε–NFA. Compute the ε–closure of each state and find it’s equivalent DFA.

	ε	a	b	c
p	{q,r}	Ф	{q}	{r}
q	Ф	{p}	{r}	{p,q}
*r	Ф	ф	ф	ф

5.      Convert a NFA which accepts the string ends with 01 to a DFA.        

6.      Consider the following ε–NFA. Compute the ε–closure of each state and find it’s equivalent DFA.                                                              

	ε	a	b	c
p	{q}	{p}	Ф	Ф
q	{r}	ф	{q}	Ф
*r	Ф	ф	ф	{r}

7.      Convert the NFA string that ends with 01 to equivalent DFA

UNIT II

1.      Find The regular expression for the set of all strings denoted byR13² from the  DFA  given below. 

2.      Draw the table of distinguishabilities for this automaton & Construct the minimum – state equivalent DFA.

3.      Find the regular expression for the set of all strings denoted by R₁³₃  from the deterministic finite automata  given below

4.      Construct the NFA –Σ For the given regular expression Using Thompson’s and Construct DFA For the  above  NFA –Σ and find the Minimized DFA?  (b/a)*bba

5.      Find whether the languages (ww, w is in (1+0)*} and {1^k | k=n2, n ≥1} are regular or not. 

UNIT III

1.      Obtain the regular expression that denotes the language accepted by the following DFA

2.      Find the regular expression for the set of all strings denotes by R₁³ ₃    from the deterministic finite automata given below

3.  Find a derivation tree of a*b +a*b given that a*b+a*b is in L(G) where G is given by

                   S → S + S | S * S , S → a | b. 

4.  Suppose the PDA P= ({q,p},{0,1},{Z₀,X}, δ,q, Z₀,{p})  has the following transition function :                                                                       

                  1. δ(q,0, Z₀)  ={(q, XZ₀)}

                 2. δ(q,0, X) = {(q,XX)}

                 3. δ(q,1, X)  = {(q,X)}      

                 4. δ(q,ε, X)  = {(p,ε)}

                 5. δ(p,ε, X)   = {(p,ε)}     

                 6. δ(p,1, X) = {(p,XX)}

                 7. δ(p,1, Z₀)  = {(p,ε)}  starting from the intial ID (q,w, Z₀), show all the reachable ID’s when  

                         the input w is a) 01  b) 0011 c) 010.

UNIT IV

1.      Show that set of all strings over {a,b} consisting of equal number of a’s & b’s is accepted by a deterministic PDA.             

2.      Convert the grammar S → 0S1 | A, A→1A0 | S | ε  to a PDA that a accepts the same language by empty stack.

3.      The following grammar generates the language of regular expression 0^*1(0+1)^*                       S → A1B , A → 0A | ε,  B → 0B | 1B | ε. Give leftmost & rightmost derivation of   the following strings:     a) 00101     b) 1001   c)  00011

4. Design context free grammar for the following languages

a) The set {0ⁿ1ⁿ | n≥1}, that is the set of all strings of one or more 0’s followed by an equal number of 1’s.      

UNIT V

1.      Consider the Language L_wwr={ww^R  | w is in (0+1)^*}. Design the PDA P to accept the L_wwr.   Starting from the initial ID (q,w, Z₀), show all the reachable ID’s when  the input w is a) 11111  b) 0011 c) 011.  

2.      Convert the PDA P= ({p,q},{0,1},{X,Z₀},δ,q, Z₀)  to a CFG , if is given by

                 1. δ(q,1, Z₀)  ={(q, XZ₀)}                    

                 2. δ(q,1, X) = {(q,XX)}

                 3. δ(q,0, X)  = {(p,X)}      

                 4. δ(q,ε,  X)  = {(q,ε)}

                 5. δ(p,1, X)   = {(p,ε)}     

                 6. δ(p,0, Z₀)  = {(q, Z₀)}           

  

3.     Prove the theorem, Let L be L(P_F) for some PDA P_F=(Q, ∑, Γ, δ_N, q, Z₀,F), then there Is

                         a PDA P_N such that L=L(P_N)    

4  Convert the PDA P= ({q,p},{0,1},{Z₀,X}, δ,q, Z₀,{p}) to a Context free grammar.

                  1. δ(q,0, Z₀)  ={(q, XZ₀)}

                 2. δ(q,0, X) = {(q,XX)}

                 3. δ(q,1, X)  = {(q,X)}      

                 4. δ(q,ε, X)  = {(p,ε)}

                 5. δ(p,ε, X)   = {(p,ε)}     

                 6. δ(p,1, X) = {(p,XX)}

                    7. δ(p,1, Z₀)  = {(p,ε)}