Annamalai University THEORY OF COMPUTATION End Semester Examination November/December 2010 Question paper

University: Annamalai  University

Course: THEORY OF COMPUTATION

Subject : THEORY OF COMPUTATION

Year of  Question Paper : 2010

Reg. No. ________                                                                                                                                                      

Karunya University

(Karunya Institute of Technology and Sciences)

(Declared as Deemed to be University under Sec.3 of the UGC Act, 1956)

End Semester Examination – November/December 2010   

Subject Title:THEORY OF COMPUTATION                                                                       
Time: 3 hours

Subject Code:09CS301                                                                                                          
Maximum Marks: 100           

                                                                                                                                                                                                                                               

Answer ALL questions (5 x 20 = 100 Marks)

1.         Compulsory:

Find a deterministic acceptor equivalent to

where is given as follows (see Table).

States/∑	a	b
àq0	q0, q1	q­2
q1	q0	q­1­
	--	q0, q1

2.    a.  Give a regular expression for representing the set L of strings in which every 0 is    immediately followed by at least two 1’s.                                                                                                                (10)

b.    Prove that the regular expression  also describes the same set of strings.                                                                                                                                                                                               (10)

(OR)

3.         Construct an FA equivalent to the regular expression

                                  (0 + 1)*(00 + 11)( 0  + 1)^*

4.         If G is the grammar S à SbS|a, show that G is ambiguous.

(OR)

5.         Show that L = {a^p|p is a prime} is not a context-free language.

6.         Consider the following productions:

                   

For the string aaabbabbba, find the

a.       Leftmost derivation,

b.      Rightmost derivation, and

c.       Parse tree.

(OR)

7.         Show that the grammar S à a|abSb|aAb, A à bS|aAAb is ambiguous. 

8.    Let where P consists of S à aAB, S à bBA, A à bS, A à bS,

A àa, BàaS, B à b.

For the grammar mentioned above, construct a deterministic pda accepting L(G) and a leftmost derivation of abbab.

(OR)

9.         Design a Turing machine M to recognize the language {1ⁿ2ⁿ3ⁿ | n ≥ 1}..

Share This