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

Formally prove the correctness of our construction for the star operator, as follows. Let $N$

be a $-$NFA constructed for the regular expression $,$ and let $N^{\text{'}}$ be the one constructed for

${}^{**},$ with two new states and four new $-$moves. Let $L$ be the language of $.$

$($a$)$ By induction on all naturals $t,$ prove that if $w$ is any string in the language $L^t,$ then

there are $w-$paths from the start state of $N^{\text{'}}$ to both the original final state of $N$ and

to the final state of $N^{\text{'}}.($The path to $N\text{'}$s final state is a useful inductive hypothesis.$)$

$($b$)$ Prove, by induction on all paths from the start state of $N^{\text{'}}$ to either the original start

state of $N,$ the original final state of $N,$ or the final state of $N^{\text{'}},$ that the string read

on the path is in the language $L^{**}.$

Solution:

$($a$)$

$($b$)$