Problem$1$ Section $23\mathrm{.}2$

Consider the following simple PCFG for noun phrases:

$0$:$6$ : NP $!$ Det AdjString Noun

$0$:$4$ : NP $!$ Det NounNounCompound

$0$:$5$ : AdjString $!$ Adj AdjString

$0$:$5$ : AdjString $!$

$1$:$0$ : NounNounCompound $!$ Noun Noun

$0$:$8$ : Det $!$ the

$0$:$2$ : Det $!$ a

$0$:$5$ : Adj $!$ small

$0$:$5$ : Adj $!$ green

$0$:$6$ : Noun $!$ village

$0$:$4$ : Noun $!$ green

where $$ denotes the empty string.

a$.$ What is the longest NP that can be generated by this grammar? $($i$)$ three words $($ii$)$

four words $($iii$)$ infinitely many words

b$.$ Which of the following have a nonzero probability of being generated as complete NPs$?$

$($i$)$ a small green village $($ii$)$ a green green green $($iii$)$ a small village green

c$.$ What is the probability of generating $$the green green$?$

d$.$ What types of ambiguity are exhibited by the phrase in $($c$)?$

e$.$ Given any PCFG and any finite word sequence, is it possible to calculate the probability that the sequence was generated by the PCFG$?$