consider the following machine ($,,$,$,$), where: $= {[]: } $([],) = [(,)] $= [&] $= {[] }

1. Prove that [] $. (Hint: the forward direction is immediate. For the converse, consider using the empty string for in the definition of ~.) 2. Prove that : ([],) = [(,)]. Induct on the length of . 3. Prove that () = (). Use the results of the last two parts in your proof. 4. Why cant be further reduced by repeating the process?

Need theoretical proof for the theory of computation or finite automata

Next, consider the following machine M' def (Q', 2,8', s',F'), where: = = = = : l' = {[p]:p E Q} 8'([p], a) = [8(p, a)] s' = [90] F' = {[p] : pe F} Part 6. (3 points) Prove that pe F = [p] e F'. (Hint: the forward direction is immediate. For the converse, consider using the empty string for x in the definition of ~.) Part 7. (5 points) Prove that Vx *: A'([p], x) = [4(p, x)]. Induct on the length of x. Part 8. (5 points) Prove that L(M') = L(M). Use the results of the last two parts in your proof. Part 9. (5 points) Why can't M' be further reduced by repeating the process? = =