Osmania University (OU) 2007 B.E Computer Science and Engineering Automata Language and Computation - Question Paper

FACULTY OF ENGINEERING B.E. 3/4 (CSE) II Semester (Main) Examination, April/May-2007 AUTOMATA LANGUAGE AND COMPUTATION

Time : Three Hours]    [Maximum Marks : 75

Note : Answer ALL questions from Part-A.

Answer FIVE questions from Part-B.

PARTA

1. Give grammar for language L(G) = 0" | n > 1. 3 2. Give FSM which accepts (01)*. 3 3. Prove whether (0 + 1)* 110 is regular or not. 3 4. Define parsing tree. Give applications. 1+3 5. What is the advantage of stack in PDA ? 2 6. Mention the closure properties of CFLs. 3 7. Give the formal definition of T.M. 3 8. Define Ambiguous Language. 2 9. Mention the machine equivalent to type grammar. 1 10. Mention the machine equivalent to CSG. 1

PARTB

11.    Give the design of FSM which accepts sentences having no. of as divisible by 3, and no. of bs divisible by 2 (i.e. even). Alphabet = (a, b); justify your design with example.    10

12.    (a) Give the design of FSM for aa* bb* c. Justify your design with example.    6 (b) Give the design of FSM, which accepts a null-string. 4

13.    (a) Construct deterministic FSM for the following grammar :

S > aS A > bB

S -> bS B -> aC

S -> aA C -> d.    6

(b) Explain the theorems, methodologies, you use for the problem 13(a).    4

14.    Reduce or simplify the following CFG :

S -> AB/CA

B > BC/AB A > a

C aB/b.    10

15.    Construct PDA to accept language : a"b²ⁿ | n > 1.    10

16.    Convert the following grammar to PDA. Justify your design, with the help of an example, [i.e. take a sentence like 010000 and prove that it is acceptable by your PDA.]

S OBB

B OS

B IS

B O.    10

17.    Design A TM to accept language L(G) = 0ⁿ 111 | n > 0. Justify your design by an example. 10

Attachment: osmania-university--ou--2007-b-e-computer-science-and-engineering-48071-1.pdf

Earning:   Approval pending.