Please solve P.14.1.3. and explain clearly.

Build a DFA that inputs a binary string and accepts it if and only if the natural in binary notation where s is your start state. is divisible by three. Describe it formally and determine o (s it represents D14.1.2 Let M be a DFA with transition function 6. Prove carefully, by induction for all strings w over M's alphabet, that 6*(i, w) j if and only if there is a path from node i to node j ir the graph of M such that the labels on the edges of the path, read in order, form w P14.1.3 Suppose that Mi and M2 are two DFA's with the same input alphabet. We'll refer to the state set, start state, final state set, and transition function of Mi as Si, 11, F, and ?? respectively, and similarly for M2. We define the product DFA M1 M2 as follows. The state set is the direct product S1 x S2, the set of ordered pairs (s1,82) with s1 e Si and s2 S2. The st state is the pair (41, (2) and the final state set is F1 x F2. The new transition function takes a state (s1, s2) and a letter a to (61(81, a), 62(82,a)). Prove that the product DFA decides the language L(Mi)n L(M2) 14.1.4 Design a variant of the product DFA from Problem 14.1.3 that decides the language L(M?)u L(M2). (Hint: You need change only the final state set.) 41.5 (Suitable for an Excursion) Design a DFA to decide the "Fibonacci language" (0+10) (A+1), the language of strings that never contain 11 as a substring. Prove that your DFA is correct, by finding a characterization of the strings taking it to each state and pr on strings that these characterizations are all correct oving by induction 41.6 Prove that every language with a finite number of strings is the language of some DEA. .17 Find the language decided by each of the two-state DEA 's counted in Exercise 14.1.3. (Hint