# Mumbai University Previous year question papers

## V Sem CSE Examination June 2009

## Theory of Computer Science

N.B.: (1) Question No.1 is”‘compulsory.

(2) -Solve any four questions out of remaining six questions.

(3) All questionscarry equal marks.

(4) Assume suitable data if required.

(5) Figures to the right indicate full marks.

1. Solvethefollowing:-s .

(a) State the pumping lemma for regular language and prove that L = { 02nIn 2: 1 }is not regular.

(b), Design a Mealy machine that accepts an input from (0 + 1)*, if the input ends in ‘101, output A; if the input ends in 110, output B ; otherwise C.

(c) Let G = (V, T, P, S) be the CFG having following set of productions. Derive the string “aabbaa” using leftmost derivation and rightmost derivation.

(d) Write a short note on Universal Turing Machine.

2. Solvethe followings:-

(a) ConstructanNFAwith E movesfor the regularexpression10(0+ 01+ 0110)* 6

(b) Find the equivalentDFAaccepting the regular language defined by the right linear grammar gIven as-

3. Solve the followings :-

(a) Given a CFG G, find G’ in Chomsky normal form generating L(G)

(b) Construct left linear and right linear grammar for the regular expression

«(01 +. 10)* 11)* 00)*.

(c) Write short note on ambiguity resolution.

4. Solve the followings :-

(a) Design a PDA for CFL that checks the well formedness of parenthesis i.e. the language L of all “balanced” string of two types of parenthesis say “( Y’& “[ ]”. Trace the sequence of moves made corresponding to input string ( ([ ]) []).

(b) Construct a PDA that will accept a CFL generated by the following :-

CFG G = (~ T, P, S) having the following set of productions–

(c) Give context free grammar generating the following sets.

(i) The string containing no consecutive ‘b’s but ‘a’s can be consecutive.

(ii) The set of all strings over alphabet {a, b} with exactly twice as many a’s as b’s.

5. Solve the followings :- ,,..’

(a) Construct a Turing machinesMto accept the language L= {wcwRIwe { 0, I } * 10

and wRmeans reverse ofw }. Trace the sequence of moves made corresponding to input string OlelO

(b) Construct a turing machine M for performing proper subtraction m-n is defined to be m-n for m > n and zero for m < n. The TM started with omI0″ on its tape, halts with om-” on its tape. Trace the sequence of moves for the input string 0000100.

6. Solve the followings :-

(a) Give the context .free grammar for the language N(M) where-

M = ( { qO,ql }, { 0, I }, { X, ZO }, 0, qO,ZO,cp),where 0 is given by

o(qO,0, ZO)= { (qO,XZO) }, o(ql, I, X) = { (qt, e) }

o(qO,0, X) = { (qO,XX) }, o(ql, e, X) = { (ql, e) }

o(qO, I, X) = { (ql, e) }, o(ql, e, ZO)= { (ql, e) }

(b) Writedowhthe minimizationalgorithmand using it find out the minimumstate finite automaton equivalent to the transition table given below.

7. Solve the followings :- .

(a) Explain the undecidability of PCP ? Does PCP with following two list-

A = (10,011, 101) and B = (101,11,011) have a solution ‘? Justify your answer.

(b) Write short note on Recursive Decent Parser.

(c) Find a Greibach normal-form grammar equivalent to the following CFG.

A~Bb IBB B ~AB Ia S ~BAI ab

(d) Give DFAaccepting the following languages over the character (0, I)

(i) The set of all strings ending in 00.

(ii) The set of all strings with three consecutive zeros.