Q$1$ CYK$-$algorithm

$10$ Points

The context$-$free grammar $(V,T,P,S)$ with variables $V=\{S,A,B,C\},$ terminals $T=$

$\{a,b\}$ and the productions

$SAB|BC$

$ABA|a$

$BCC|b$

$CAB|a$

generates non$-$empty strings in $T^{**}.$ Execute the Cocke$-$Younger$-$Kasami $($CYK$)$ algorithm for

this grammar on the input $s=$abbaba. Give a table of all sets $V(i,k)$ computed and all

parse trees for $s.$

The parse trees are encoded as strings, which will be obtained from $s$ by inserting brackets.

Below you are asked to give the codes of the different parse trees, sorted in alphabetic order,

where

For example, $(ab)(ab)$ encodes the tree

Moreover, the parse tree given $by$ the string $(ab)(ab)is$ ordered before the parse tree given

$by$ the string $a((ba)b).$

Q$1\mathrm{.}1$ V$($i$,$i$)$

Give the sets V$[$i$,$i$]$ for i$=1,...,6$ separated by a single blank symbol. In each set list the variables in alphabetic order and separate them by a comma only. Especially, $\{\}$ denotes the empty set and $\{$A$,$B$\}$ denotes the set containing A and B$.$

Q$1\mathrm{.}2$ V$($i$,$i$+1)$

Give the sets V$[$i$,$i$+1]$ for i$=1,...,5$ separated by a single blank symbol. In each set list the variables in alphabetic order and separate them by a comma only. Especially, $\{\}$ denotes the empty set.

Q$1\mathrm{.}3$ V$($i$,$i$+2)$

Give the sets V$[$i$,$i$+2]$ for i$=1,...,4$ separated by a single blank symbol. In each set list the variables in alphabetic order and separate them by a comma only. Especially, $\{\}$ denotes the empty set.

Q$1\mathrm{.}4$ V$($i$,$i$+3)$

Give the sets V$[$i$,$i$+3]$ for i$=1,2,3$ separated by a single blank symbol. In each set list the variables in alphabetic order and separate them by a comma only. Especially, $\{\}$ denotes the empty set.

Q$1\mathrm{.}5$ V$($i$,$i$+4)$

Give the sets V$[1,5]$ and V$\{2,6].$

Q$1\mathrm{.}6$ V$($i$,$i$+5)$

Give the set V$[1,6].$

Q$1\mathrm{.}71$st parse tree

Give the $1$st parse tree as described above:

Q$1\mathrm{.}82$nd parse tree

Give the $2$nd parse tree as described above:

Q$1\mathrm{.}93$rd parse tree

Give the $3$rd parse tree as described above:

Q$1\mathrm{.}104$th parse tree

Is there a fourth parse tree?