if $\delta(q, a) = q$ for all symbols $a$, show that $\delta^* (q, w) = q$ is true for all strings $w$

Question

Let $A$ be a DFA and $q$ a particular state of $A$, such that $\delta(q, a) = q$ for all input symbols $a$. Show by induction on the length of input that for all strings $w$, $\delta^* (q, w) = q$.

I'm completely new to the subject. But this is what I have done. Can someone please tell me if this is the correct solution?

For the basis of the induction $|w|=1$, $\delta (q,a)=a$ is already correct by definition.

Let $n = |w|$, the number of symbols in the string $w$. Let $\delta^*(q,w)=q$ be true for some $n \gt 1$ (hypothesis of induction). Now I should prove it for $n+1$ using the hypothesis of induction. Let $z=wa$.

$$ \delta^*(q,z) = \delta^*(q,wa) $$

It follows that: $$ \delta^*(q,wa) = \delta^*(\delta^*(q,w),a) $$

From the hypothesis, I know that $\delta^*(q,w)=q$, so if I substitute this in the above equation:

$$ \delta^*(q,a) $$

and this is equal to $q$ according to the base case. So, I conclude that $\delta^*(q,w)=q$ is true for every $n$.

Is the above so-called "solution" correct?

Answer 1

By popular request, here is what the proof could look like:

By induction over the length of $w$. Assume $\delta(q,a)=q$ for all $a$. Take any $w$. There are two cases:

1. If $|w|=0$ then $w=\epsilon$ (the empty word). Now the definition of $\delta^*$ has "$\delta^*(q,\epsilon)=q$" without any assumption on $\delta$ or $q$. We thus have $\delta^*(q,w)=q$ in this first case.

2. If $|w|>0$ then $w$ is some $w'a$ and $|w'|<|w|$. Now $\delta^*(q,w)=\delta^*(q,w'a)=\delta(\delta^*(q,w'),a)$ by definition of $\delta^*$. Since $|w'|<|w|$ we have $\delta^*(q,w')=q$ by induction hypothesis. Finally $\delta^*(q,w)=\delta(q,a)$, which is $q$ by the assumption. We have proved the required conclusion in this second case too.

All cases have been covered. The proof is complete.

Note that the two cases can be considered in any order we like. And that we do not use that $|w'|=|w|-1$, just that $|w'|<|w|$.

As you can see, the above proof uses the same arguments as in your solution, and at the same places. It is slightly more rigorous on the quantifications ("take any $w$" is a "$\forall w$" and "$w$ is some $w'a$" is a "$\exists w'\exists a:w=w'a$") and their nesting ($w'$ and $a$ depend on $w$).

It is the kind of proof I'd love to get from a bright student beginning automata theory. But it is too pedantic and pedestrian for experts who, in their own papers, will usually just state the conclusion as obvious from the assumption. They may even not state the conclusion at all and use it anyway.