Given a deterministic finite-state automaton M = (S, I, (, s0, F), use structural induction and the recursive definition of the extended transition function f to prove that ((s, xy) = ((( (s, x), y) for all states s ∈ S and all strings x ∈ I* and y ∈ I*.