Prove that ~ (,)~(,). Equivalently, if [] = [] then [(,)] = [(,)]. (Hint: to proceed, let , . Show that ((,),) ((,),) .) In plain English, this simply says that if you start out in equivalent states then after the next symbol you will be in states that are equivalent. The property we just established is crucial because it ensures that when we merge

= > = > Part 5. (5 points) Prove that p~q = 8(p, a)~8(q, a). Equivalently, if [p] = [q] then [8 (p, a)] = [8(q, a)]. (Hint: to proceed, let a 2, y e*. Show that A(8(p, a), y) EFA A(8(q, a), y) e F.) In plain English this simply says that if you start out in equivalent states then after the next symbol you will be in states that are equivalent. > The property we just established is crucial because it ensures that when we merge equivalent states, the resulting machine will be a DFA. Next, consider the following machine M' def (Q', 2,8', s',F'), where: = Q' = {[p]:p E Q} 8'([p], a) = [8(p, a)] s' = [90] F' = {[p] : pe F} =