Problem 23. Design a DFA M that decides the language A={r {0,1}* |#(1, 1) is odd and (bnum(I) is a multiple of 2 or a multiple of 3)} Define a finite-state compressor (FSC) to be a 4-tuple C = (Q.5,v,s), where Q is a finite set of states; .::Q {0,1} Q is the transition function; v:Qx {0,1} {0,1}" is the output function; SEQ is the start state. Define the extended transition function 8 : Qx{0,1}" Q as for DFAs. Define the output from state qe Q on input string w {0,1}* to be the string (q,w) defined by the recursion vq, 1) = 1 vq, ub) = v(q, uv( [q,u),b) for all q E Q, {0,1}", and be {0,1}. Finally, define the output of the FSC C on input w {0,1}* to be the string C(u) = (s, w). Example 1/11 0/0, 1/10001 3 1/1001 0/ 1/101 0/1 1 2 2 0/1 The diagram above denotes the FSC C = (0,0,0,8), where Q = {0, 1, 2, 3}; 8(9,0) = (q + 1)moda for all q E Q; 8(q, 1) = 0) for all q E Q; S1, if q 52 v(,0) = 0, if q=3 v(q, 1) = 1091 for all q EQ. Note that each transition arrow is labeled by b/y, where b is the input bit producing the transition and y is the output string produced by the transition. Intuitively, an FSC compresses an input string w if |C(w) is significantly less than |w). Problem 23. Design a DFA M that decides the language A={r {0,1}* |#(1, 1) is odd and (bnum(I) is a multiple of 2 or a multiple of 3)} Define a finite-state compressor (FSC) to be a 4-tuple C = (Q.5,v,s), where Q is a finite set of states; .::Q {0,1} Q is the transition function; v:Qx {0,1} {0,1}" is the output function; SEQ is the start state. Define the extended transition function 8 : Qx{0,1}" Q as for DFAs. Define the output from state qe Q on input string w {0,1}* to be the string (q,w) defined by the recursion vq, 1) = 1 vq, ub) = v(q, uv( [q,u),b) for all q E Q, {0,1}", and be {0,1}. Finally, define the output of the FSC C on input w {0,1}* to be the string C(u) = (s, w). Example 1/11 0/0, 1/10001 3 1/1001 0/ 1/101 0/1 1 2 2 0/1 The diagram above denotes the FSC C = (0,0,0,8), where Q = {0, 1, 2, 3}; 8(9,0) = (q + 1)moda for all q E Q; 8(q, 1) = 0) for all q E Q; S1, if q 52 v(,0) = 0, if q=3 v(q, 1) = 1091 for all q EQ. Note that each transition arrow is labeled by b/y, where b is the input bit producing the transition and y is the output string produced by the transition. Intuitively, an FSC compresses an input string w if |C(w) is significantly less than |w)