Note: Answer all the FOUR questions. Q. 1 Maximum score 25 Draw a DFA which will accept all strings that begin or end with aa or bb Q. 2 Maximum score 25 Design a NFA for the following language L = {w (0-9)* : w represents the decimal encoding of a natural number whose encoding contains, as a substring, the encoding of a natural number that is divisible by 3}. {Note that 0 is a natural number that is divisible by 3. So any string that contains even one 0,3, 6, or 9 is in L, no matter what else it contains. Otherwise, to be in L, there must be a sequence of digits whose sum equals 0 mod 3 Q. 3 Maximum score 25 Convert the following NFA to DFA (Arrow represent the starting state and * represents accepting state) a b 2 (2.4) State +1 2 3 4 *5 {3} (5) {5} (2) {4} Q. 4 Maximum score 25 For the following DFA, find the minimal DFA (minimal number of states (Arrow represent the starting state and * represents accepting state) State a b 2 3 2 6 2 4 6 4 5 3 *4 6