Acharya Nagarjuna University (ANU) 2005 B.Tech Information Technology IT 312 Automata Theory and Formal Languages - Question Paper

III/IV B.Tech Degree exam
October 2005
Automata Theory and Formal Languages
IT 312

(IT 312)

III/IV B.Tech. DEGREE EXAMINATION, OCTOBER 2005.

First Semester

(IT 312)

AUTOMATA THEORY AND FORMAL LANGUAGES

Time ; Three hours    Maximum: 70 marks

All questions carry equal marks.

(IT 312)

Answer Question No. 1 compulsorily. (1 x 14 = 14)

Answer ONE question from each Unit. (4 x 14 = 56)

(a)	Define DEA.
(b)	What is the use of e-move?
(c)	Define Regular Bet.
<d)	c*. ii .r\ to t1
(e)	Define CEL.
(f>	Define ambiguous grammar.
(g)	Define Parse tree.
(h)	Define recursively enumerable language.
(i)	Define C.S.L.
(i)	What are unit productions?
(k)	Define PDA.

(1) Define Computable language.

(m) State myhell - Nerode theorem.

(n) Give any two closure properties of Regular

sets.

UNIT I

2. (a) Design an NFA to accept strings with 0s and ls such that string contains two consecutive 0s or two consecutive 1*8.

(b) Convert the following NFA with moves to OTA without e moves.

(c)    Construct equivalent NFA with transition for the following regular expression, r = 0' +11.

(d)    Convert the following mealy machine into equivalent moore machine.

c/e.    <y_c

3. (a) Show that L {a^Hbⁿ In 0) is not regular by using pumping lemma.

(b) Construct minimum state automation equivalent to the transition diagram.

o Or

(c)    Construct CFG for the set of palindromes over alphabet (c> 6).

(d)    Show that the grammar is ambiguous where G{},{a,6,    ej and productions P are

P :+e / 6 *e/afb.

UNIT m

4. (a) Convert the following CFG into equivalent CMF G=(V,T_yP_tS) where V - (S,A,), T {,&} and productions are S aAbB , A -+ aA/a,

B-+6B/6.

^r (b) Find a Greibach Normal form grammar equivalent to the following CFG.

S AA/Q_t ASS/1 Or

(c)    Design a deterministic pushdown Automata for the following language L = (0"1^2fi in > 1},

(d)    Construct an equivalent PDA for the following CFG,

8 QA_t A - OABCfXBtO, B -> l_tC -2.

'    '    UNIT IV

5. (a) Show that the following language ia not context free L [q,^p / p is prime).

(b)    Design, a T.M. to recognize all strings consisting of odd number of la.

Or

(c)    Design a T.M. that computes m+n for the given two positive integers m,n.

(d)    Write short notea on Universal T using machine.

Attachment: acharya-nagarjuna-university--anu--2005-b-tech-information-technology-7385-1.pdf

Earning:   Approval pending.