I'm having a few problems with this proof and I'm not sure where to start.
In our class, a Deterministic Finite Automata, or DFA, is defined as a 5-tuple
$$M = (Q,\Sigma,\delta, q_0, F) $$
Where $Q$ is a set of states, $\Sigma$ is a set of symbols, $\delta$ is a transition function between states, $q_0$ is the starting state, and $F$ is a set of accepting states for the DFA.
The problem in my assignment is as follows:
A DFA is given with a transition function $\delta$ , which is a function from $$ Q * \Sigma \to Q $$ We extend the domain of the definition of $$ \hat\delta : Q * \sideset{}{^*}\Sigma \to Q$$ That is for every pair $<q,s>$, where $ q \in Q $ and $s$ is any string of symbols over $\Sigma$, the extended function value $$ \hat\delta (q, s) \in Q$$ is defined as follows: $$\hat\delta (q, \varepsilon ) = q $$ and $$ \hat\delta (q, xa) = \delta ( \hat\delta (q, x), a)$$ The definition intends to capture the notion of a DFA starting with any state $q$, and after reading a string $s$, reaches state $\hat\delta (q, s)$
Prove by induction on the length of the string that for all $q \in Q $ and all strings $x$ and $y$,
$$\hat\delta (q, xy) = \hat\delta ( \hat\delta (q, x), y)$$ where $xy$ is the concatenation of $x$ and $y$.
My current problem is that I don't know where to start induction. It says to perform induction on the length of the string but it isn't clear to start on string $x$ or string $y$. Also, I am bad at induction.
Choose any string $x \in \Sigma^*$ and let $y \in \Sigma^n$ have length $n \geq 0$. We proceed by induction on $n \geq 0$.
Base Case: For $n = 0$, we have that $y = \varepsilon$. (Fill in the rest here.)
Induction Step: Assume that the claim holds for $n' = n - 1$, where $n \geq 1$. It remains to show that it holds for $n' = n$. Indeed, let $y = za$, where $z \in \Sigma^{n - 1}$ has length $n - 1$ and $a \in \Sigma$ has length $1$. Then it follows that: \begin{align*} \hat\delta(\hat\delta(q, x), y) &= \hat\delta(\hat\delta(q, x), za) \\ &= \delta(\hat\delta(\hat\delta(q, x), z), a) \\ &= \cdots \text{fill the rest in here} \cdots \\ &= \hat\delta(q, xza) \\ &= \hat\delta(q, xy) \end{align*}