x Can be untested by / mach Pow/IDL/MIDSEM/306-202 muttible little machin * Next possible slat is distinctly set cal pawn of siet inpot have many c) Given that LI = {ab, be, abc} and L2 = { b, bb, b}, find: i ) LIL2 ii) Li'L2" iii) (LI U L2)' [15 Marks - 5 marks 4. a) Let G, and G2 be context-free grammars, generating the languages L(G1) and L(G respectively. Show that there is a context-free grammar generating each of following sets. [9 Marks - 3 marks each] i) L(G1) U L(G2) ii ) L(GI)L(G2) iii) L(G1)* c) Let G be the grammar with V = {a, b, c, S}, T =(a, b, c}, starting symbol S, ar productions S -abS, S - bcS, S - bbS, S -a, S - cb. Construct a parse or derivation tree for each of the following: [8 Marks - 2 marks each] i ) bcbba ii) bbbcbba iii) bcabbbbbcb iv) bbacbbbaI. a) List the properties of regular expressions. [5 Marks] b) Let V be an alphabet, and let A and B be subset of V* with A S B. Show that A' CB'. [10 Marks] c) Show that the grammar G - {V. T. S. P) with vocabulary (or alphabet) V - (0. S), terminal symbols T - {0). starting symbol S. and productions P given by S - OS, S - 80, and S - 0, is ambiguous by constructing two different derivation or parse trees for 0'. [10 Marks] 2. a) Determine whether the string 10101 is in each of the following regular sets: i ) (o, 1}' iv ) (11} (01}" v) (111}' (0)' (1) vi) (111, 000} {00, 01} [12 Marks - 2 mark each] b) Draw the Finite State Automaton that can recognize each of the following languages. i) L(M,) = (1" : n = 0, 1, 2, ...} [4 Marks] ii ) L(M2) = (0, 01, 000} [4 Marks] ii) L(M3) = {0", 0"10x : n = 0, 1, 2, ..., and x is any string). [5 Marks] 3. a) Differentiate between Deterministic Finite State Automaton (DFA) and Non- deterministic Finite State Automaton (NFA). [4 Marks] b) Draw the NFA for the following regular expressions: [6 Marks - 3 Marks each] i) a*(atb)* + abc* ii) a (c*+d).(bc)* 2 of 3