Shivaji University 2012-4th Sem B.E Computer Science and Engineering S.E(Computer Sci& Engg.) , - Question Paper

S.E. (Computer Sci. & Engg.) (Semester-IV) Examination, 2012
AUTOMATA THEORY
Sub. Code: 43614

Instructions: 1) ques. no. one and four are compulsory.
2) Figures to right indicate full marks.
3) presume suitable data whenever necessary.

SECTION-I
1. Solve any 3 questions:
a) Draw NFA and convert it DFA for (1+0)(01)*(011)*.
b) Write the CFG for a language of odd length string in {a, b}* with the 1st ,middle and last symbols are identical.
c) What is extended transition function? Write the recursive definition of extended transition function for NFA-^.
d) What is LL(k) Grammar? discuss with suitable example.
2. a) obtain the regular expression for the subsequent languages ? ={0,1}
i) The language of all strings that start or end with 00 or 11.
ii) The language of all strings that do not end with 01.
b) define the proof of union and concatenation of CFLs is a CFL.
3. a) Convert the subsequent grammar to its Chomsky Normal Form.
S ? AACD
A ? aAb / ^
C ? Ac / A
D ? aDa / bDb / ^
b) What is ambiguous CFG? discuss with suitable example

SECTION-II
4. Solve any 3 questions:
a) Comment on "Intersection and complement of CFL is not a CFL".
b) discuss calculation of partial function using Turing Machine.
c) What is Universal Turing Machine? discuss encoding of Turing Machine.
d) Draw a PDA for accepting language of palindrome of the for xcx. (x is any string of the form (a+b)*)
5. a) Convert the subsequent grammar to Top-down PDA:
S ? aABB / Aaa
A ? aBB / a
B ? bBB / ^
b) define the acceptance of a string in PDA.
6. a) Construct the 1 tape Turing Machine for copying the string on tape. ( copy the new string after the ending blank symbol of 1st string )
b) Construct Turing Machine to convert the lowercase string to uppercase string.

Earning:   Approval pending.