(a) Let $D=\left(Q, \Sigma, \delta, q_{0}, F\right)$ be a deterministic finite-state automaton. Define the extended transition function $\hat{\delta}: Q \times \Sigma^{*} \rightarrow Q$, and the language accepted by $D$, denoted $\mathcal{L}(D)$. Let $u, v \in \Sigma^{*}$, and $p \in Q$. Prove that $\hat{\delta}(p, u v)=\hat{\delta}(\hat{\delta}(p, u), v)$.

(b) Let $\sigma_{1}, \sigma_{2}, \ldots, \sigma_{k} \in \Sigma$ where $k \geqslant|Q|$, and let $p \in Q$.

(i) Show that there exist $0 \leqslant i<j \leqslant k$ such that $\hat{\delta}\left(p, \sigma_{1} \cdots \sigma_{i}\right)=\hat{\delta}\left(p, \sigma_{1} \cdots \sigma_{j}\right)$, where we interpret $\sigma_{1} \cdots \sigma_{i}$ as $\epsilon$ if $i=0$.

(ii) Show that $\hat{\delta}\left(p, \sigma_{1} \cdots \sigma_{i} \sigma_{j+1} \cdots \sigma_{k}\right)=\hat{\delta}\left(p, \sigma_{1} \cdots \sigma_{k}\right)$.

(iii) Show that $\hat{\delta}\left(p, \sigma_{1} \cdots \sigma_{i}\left(\sigma_{i+1} \cdots \sigma_{j}\right)^{t} \sigma_{j+1} \cdots \sigma_{k}\right)=\hat{\delta}\left(p, \sigma_{1} \cdots \sigma_{k}\right)$ for all $t \geqslant 1$.

(c) Prove the following version of the pumping lemma. Suppose $w \in \mathcal{L}(D)$, with $|w| \geqslant|Q|$. Then $w$ can be broken up into three words $w=x y z$ such that $y \neq \epsilon,|x y| \leqslant|Q|$, and for all $t \geqslant 0$, the word $x y^{t} z$ is also in $\mathcal{L}(D)$.

(d) Hence show that

(i) if $\mathcal{L}(D)$ contains a word of length at least $|Q|$, then it contains infinitely many words;

(ii) if $\mathcal{L}(D) \neq \emptyset$, then it contains a word of length less than $|Q|$;

(iii) if $\mathcal{L}(D)$ contains all words in $\Sigma^{*}$ of length less than $|Q|$, then $\mathcal{L}(D)=\Sigma^{*}$.