How to pick a good structural induction hypothesis
-
01-11-2019 - |
Question
(Full disclosure: homework question)
Let $M = (Q, \Sigma, q_0, A, \delta)$ be a finite automaton. The extended transition function $\delta^*$ is defined as follows:
$\forall q \in Q$
$\delta^*(q, \Lambda) = q$
$\forall q \in Q, y \in \Sigma^*, \sigma \in \Sigma$
$\delta^*(q, y \sigma) = \delta(\delta^*(q, y), \sigma)$
I am attempting to prove the following statement $\forall x,y \in \Sigma^*$:
$\delta^*(q, xy) = \delta^*(\delta^*(q, x), y)$
It seems pretty obvious from an intuitive standpoint. Since the definition of $\delta^*$ states that for all $y \in \Sigma^*, \sigma \in \Sigma$
$\delta^*(q, y\sigma) = \delta(\delta^*(q, y), \sigma)$
And since the base case of $\delta^*$ is (using $\Lambda$ as the empty string)
$\delta^*(q, \Lambda) = q$
That means $\delta^*(q, y)$ is just a bunch of nested $\delta^*$ applications with the first symbol of $y$ on the innermost application, and the last symbol of $y$ on the outermost application. E.g. if $y = y_1y_2y_3$, then
$\delta^*(q, y) = \delta^*(\delta^*(\delta^*(y_1), y_2), y_3)$
I'm not very experienced at writing proofs, so I'm not sure how to go about setting up the basis case, induction hypothesis, etc. I can prove the first equation for $xy = \Lambda$ as the basis, but I don't know what to do beyond that.
No correct solution