Acharya Nagarjuna University (ANU) 2005 B.Tech Computer Science and Engineering CS 325 Automata Theory and Formal Languages - Question Paper

III/IV B.Tech Degree exam
October 2005
Automata Theory and Formal Languages
CS 325

Iir/2V H.Tech. DEGREE EXAMINATION, OCTOBER 2005.

Second Semester AUTOMATA THEORY AND FORMAL LANGUAGES Time : Three hours    Maximum : 70 marks

All questions carry equal marks.

Answer Question No. 1 compulsorily.

(J x 14 = 14 j

Answer ONE question from each Unit.

-    (4x14 = 56)

1,    (a) Give an example for DFA.

(b) What is meant by language accepted by DFA?    

(e) What is meant by e -closure (q)?

(d)    What is meant by crossing sequence of 2DFA?

(e)    Define GPL,

(f5 Define undecidability.

(g)    Define PDA.    .

(h)    Define TM,

(i)    Write instantaneous description of T.M.

(j) What is p&rae tree?

(k) What is meant by ambiguous grammar?

(1) Define compactable language-(m)'Define universal tuning machine.

(n) What is useless symbol?

UNIT I

2.    (a) Construct finite' automata equivalent to the following regular expressions 01 {((10)' + 111}' + 0]' 1.

(b) Construct a DFA equivalent to the NFA m = {?, X, 5, pi f) where Q = {p.q,r*s} S (0,1), F = Ij) and S given by the table

(d) Design a Moore machine to determine the residue mod 3 for each binary string treated binary integer,

UNIT II

(a)    Show that the set L = jo'¹ / i > l] ia not regular.

(b)    Find the minimum state automaton, for the following DFA :

(c> Construct CFG generating the language L = b^J c^h U = j + k\ (d) Let O be the grammar

S > aB IM A a/ aS I bAA B btbs/aBB.

For the string aaabbabbba find a

(i) Left most derivation

Right most derivation

UNIT HI

4,    (aj End a grammar in CNF equivalent to the grammar S - N ~S/\s~3s]l pfq (sbeingthe only variable. ¹

Cb) Find a grammar in CNF equivalent to.the grammar S M/o A* SStl.

Or

tc> Construct a PDA that accepts the language L = {wCw' / we {a.6)}

(d) Wirte GYK algorithm.

UNIT IV

5.    (a) Write short notes on T.M.? And also give differences between a T.M. find P.D.A?

(b)    Design a T.M. to accept the language L = {(JT/nSl).

Or

(c)    Write short notes on Recursively enumerable language.

(d)    Show that post correspondence problem ia undecidable.

Attachment: acharya-nagarjuna-university--anu--2005-b-tech-computer-science-and-engineering-7573-1.pdf

Earning:   Approval pending.