$P14\mathrm{.}5\mathrm{.}8[10pts]$

The end of the section gives a recursive definition of the relation ${}^{**}(s,w,t)$ in a $-$NFA for

arbitrary states $s$ and $t,$ and arbitrary strings $w.$ Prove by induction on this definition that

if ${}^{**}(s,w,t)$ is true, then there exists a path in the $-$NFA's state diagram from $s$ to $t$ such

that the letter labels on the path, taken in order, spell out $w.$