Exercise ${32}_{?}$ CYK algorithm

$(6$ points$)$

Let the context free grammar $G=(\{S,A,B,C,D,x,Y\},\{a,b\},P,S)($which already is in Chomsky

normal form$)$ be given, where $P$ is defined by

$SAB|xC|xY,AxC|xY,BDY|xY,xa$

$CAY,DxB,Yb$

$($a$)$ Check by means of the CYK algorithm, whether the following words are in $L(G)$ :

ababab

aaabbb

Set up the table of the CYK algorithm and explain what kind of result can be read from the

table. Submissions without any explanation do not get any points!

$($b$)$ Specify the language $L(G)$ which is generated by $G.$

$($c$)$ Assume the table for the word aaabbb contains a $D$ in row $3,$ column $2.$ What does this imply?

$(1p)$