PROBLEM $1$: Parsing with Cocke$-$Kasami$-$Younger $($CKY$)$ algorithm $(50$ points$)$

Grammar:

$```$

S $\}->\backslash$mathrm$\{$ NP VP

VP $->$ V NP $|$ VP PP$|$V

PP $->$PNP

NP $->$ Det N$|$N$|$NP PP

Det $->$ 'the' $|\text{'}$a$\text{'}$

N $->$ 'dog' $|$ 'cat' $|$ 'garden' $|$ 'boy' $|$ 'telescope'

V $->$ 'saw' $|\text{'}$chased$\text{'}|$ 'ran'

P $->\text{'}$in$\text{'}|$ 'with'

$```$

Sentences:

$1.$ The boy saw the dog with the telescope

$2.$ The cat ran in the garden

$3.$ The dog chased the boy in the garden

$4.$ A boy with a telescope saw the cat

Use the CKY algorithm to parse the four sentences using the grammar provided and show all the possible parses for the sentences in the simple bracketed structure.