# How to pick a good structural induction hypothesis

(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:

1. $\forall q \in Q$

$\delta^*(q, \Lambda) = q$

2. $\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.

• There's some supporting information missing here. I'm guessing from the tags that $\delta^{\ast}$ is an iterated transition function from a DFA/NFA? In the first statement are $x$ and $y$ strings or characters? If the induction is on $y$, shouldn't the base case be $\delta^{\ast}(q,x\lambda)$? – Luke Mathieson Feb 6 '15 at 3:25
• Apologies, I added some more information in the post. You are correct that $\delta^*$ is the extended (iterated) transition function from a DFA. $x$ and $y$ are both strings. I am not sure what the base case should be, but your suggestion sounds doable as well. – itsjareds Feb 6 '15 at 3:38

This is a (moderately sketchy) outline of the induction. As it's a structural induction (a generalisation of the familiar, standard induction), we need the object we're inducting over to have a recursive definition. In this case we'll induct over the string $y$, and we can define a string (over an alphabet $\Sigma$ as:

1. $\lambda$ is a string.
2. If $s$ is a string and $\sigma \in \Sigma$, then $s\sigma$ is a string.

We'll steal the normal notation and say that a string constructed in this way is in $\Sigma^{\ast}$ of course. (This level of formalism can be left implicit, it's just nice to see it a few times to help with the understanding of what the proof structure is). Normal mathematical induction can be done in a similar way, where the recursive structure is the Peano version of the naturals, so we're actually on familiar ground here.

Then the proposition you want to prove is

$$\forall q \in Q, x,y \in \Sigma^{\ast},\,\, \delta^{\ast}(q,xy) = \delta^{\ast}(\delta^{\ast}(q,x),y)$$

We will "prove" this by structural induction over $y$.

So then we have a base case for every base case of the recursive definition. In this case there's only one, $y = \lambda$.

Base Case

$$\Sigma^{\ast},\,\, \delta^{\ast}(q,x\lambda) = \delta^{\ast}(\delta^{\ast}(q,x),\lambda)$$

(You get to fill in the gaps of course, but this one should be reasonable clear.)

Then we have an induction hypothesis and step for every recursive case in the recursive definition, again just like induction over the naturals, we only have one case, so things are nice and simple.

Inductive Case

$$\forall q \in Q, x,y \in \Sigma^{\ast}, \sigma \in \Sigma ,\,\, \delta^{\ast}(q,xy) = \delta^{\ast}(\delta^{\ast}(q,x),y) \rightarrow \delta^{\ast}(q,x(y\sigma)) = \delta^{\ast}(\delta^{\ast}(q,x),(y\sigma))$$

That is, if you know that it's true for $y$, prove that it's true for $y$ plus one more character $\sigma$ (again, we're lucky that the structure is very similar to the natural numbers).

Hint: Prove the identity $\delta^*(q,xy) = \delta^*(\delta^*(q,x),y)$ by induction on $|y|$ (the length of $y$).