$($c$)$ The following recursive algorithm uses a slightly different idea. Its correctness relies on the

fact that a string $w_1{w}_{2}dots{w}_{n}in{L}^{**}$ if and only if there exists an index iin$\{0,$dots,$n-1\}$ such

that $w_1{w}_{2}dots{w}_{i}in{L}^{**}$ and $w_{i+1}dots{w}_n$inL. Explain why $S_2$ does not run in polynomial time.

$($d$)$ The main issue with the recursive algorithm in part $($c$)$ is that it for each prefix $w_1{w}_{2}dots{w}_i$ of

$w,$ it keeps repeating the work of checking whether that prefix is in $L^{**}.$ Wouldn't it be great

if for each $i,$ you only had to check whether $w_1{w}_{2}dots{w}_i$ is in $L^{**}$ once?

It turns out you can, and this forms the basis of an actual polynomial time algorithm. Think

of filling out an array $T[0,1,$dots,$n]$ where each cell $T[i]$ contains the answer to the question,

$"$is $w_1{w}_{2}dots{w}_{i}in{L}^{**}?"$ Design an algorithm $S_3$ that systematically fills in this array and uses

it to determine whether $win{L}^{**}.$ Briefly explain why your algorithm runs in polynomial time,

and how it allows you to conclude that $P$ is closed under the star operation.