The Moments of String Length

$($

$2$

$4$

$$pts

$)$

In this question, we explore one of the benefits of having a language model based on a simpler formalism

$$

namely, many computations that we may wish to perform can be done exactly in polynomial time.

In that context, your task is to derive efficient algorithms for computing several quantities about the

string length under two modeling frameworks

i

$)$

$$when the language model is finite

$-$

state and

ii

$)$

$$when the language model is context

$-$

free.