When you are performing the CYK algorithm, you are basically filling the bottom triangular matrix from its bottom to the uppermost element. Whenever some element (j,i,x)
where j
is the column index, i
is the row index and x
is the non-terminal symbol is true, it means that you are able to generate the subsequence j
to j+i-1
of your word from the symbol Rx
.
Your goal is to generate the whole word from one of the starting symbols. The element corresponding to the possibility of generating the whole word is (1,n,x)
- the leftmost and uppermost element of the matrix, where the x
is the index of your non-terminal symbol. As you have to start in one of the start symbols, you are looking just for a subset of all of your non-terminals - the subset of s
. If you manage to generate the whole word from one of the start symbols, you simply state that the word is part of the language. If no such start symbol exists, you aren't able to generate that word and the word isn't part of the language described by the grammar.