Question (1) (A) Obtain the minimal equivalent DFA for the following NFA: NFA = ({a, b,c}, {QO, Q1, Q2, Q3, Q7}, F, QO, {Q3}) F(QO, a) = {QO, Q2, Q3} F(QO, c) = {Q1} F(Q1, c)= {Q3} F(Q2, b) = {Q2, Q3} F(Q7, b) = {Q2, Q3} (B) Construct the NFA for c* (cd)*d*. Question (2) (A) Given the following grammar S+ 0S 0S1S | 2 Is this grammar ambiguous? If so, prove it and construct a non-ambiguous grammar that derives the same language. (B) Give context-free grammars that generate the following languages where = {0,1} (i) {w w starts and ends with the same symbol} (i) {w the length of wis odd and its middle symbol is 0} Question (3) (A) Show that the following languages is regular or not regular. (1) A = {www we {a, b}*} (ii) B = {1P-1| p is prime} a,b 2 (B) Convert the following finite automata to regular expressions. 3 Question (4) Let D= {w w contains an even number of a's and an odd number of b's and does not contain the substring ab}. Give a DFA that recognizes D and a regular expression that generates D. Question (5) Convert the following CFG R to Chomsky Normal Form CNF, and then test if x = abbbbb E L(R) S ASBE A AS a B SSA | bb