7964526624

10

(b)    Construct NFA for (a/£>)⁺ and derive DFA through subset construction algoritlim.

(c)    Prove or disprove tlie following for regular 10 expressions r, s and t

(i)    (r + s) =r* + s*

(ii)    s(rs + s) r rr*s(rr*s)

3 Attempt any four question$ :

(a)    Construct finite automata equivalent to    5

following regular expression -

10 + (0 + ll)0*l

(b)    Write regular expres$ion for tlie following 5 language over tlie alphabet {0, l} -

“The set of all strings not containing 101 as a substring.”

(c)    Explain tlie procedurę to convent a Moore 5 machinę into its corresponding Mealy machinę, witli tlie help of an example.

(d)    Find parse tree for tlie expression abbcde 5 considering tlie productions -

5 -> a Ac Be A -> Ab A->b B —> d

(e)    What is an ambiguous grammar ? Explain with 5 example.