= Solution
We induct on the length of $w$. For $w=\varepsilon$, the extended transition set is $\{q\}$, and the sole witnessing sequence is $(q)$, so the claim holds.
Write a nonempty word as $w=va$. By the recursive definition,
$$
q'\in\widehat\Delta(q,va)
$$
if and only if there is some $p\in\widehat\Delta(q,v)$ with $q'\in\Delta(p,a)$. By the induction hypothesis, the first condition on $p$ is equivalent to a witnessing sequence for $v$ from $q$ to $p$. Appending $q'$ gives a witnessing sequence for $va$. Conversely, deleting the last state of any witnessing sequence for $va$ gives just such a state $p$ and sequence for $v$. This proves both implications.
Back to article page
