CYK Algorithm
In this practice is about compute the CYK algorithm given the gramma on the Figure 1.
To compute the CYK algorithm the grammar must be on the Chomsky Normal Form (CNF) as show in the Table 1,in the start step the grammar is depurated, in the first step the terminals are replaced, and in the second step it’s the splitting between terminal and generator.
Considering the following case for the CFG with the word w=lxt, In this case the word is part of the language given the grammar.
S -> BD
R -> KD
D -> SR
B -> l
R -> t
K -> c
S -> x
Considering the following steps
N<-|3|
It will show the next results.
Therefore, the word w=lxt is accepted.
Considering the following case for the CFG with the word w= llxtcxt, In this case the word is not part of the language given the grammar.
S -> BD
R -> KD
D -> SR
B -> l
R -> t
K -> c
S -> x
Therefore,the word w= llxtcxt is accepted.
Considering the following case for the CFG with the word w= lxxcxt, In this case the word is not part of the language given the grammar.
S -> BD
R -> KD
D -> SR
B -> l
R -> t
K -> c
S -> x
Therefore,the word w= lxxcxt is not accepted.
Conclusion
As a conclusion I think that this practice was a challenge, because it was a little difficult to understand the map and set at the same time, but what help me a lot was the cplusplus website and the “trasa” on the notebook, and I think that this practice will help to develop the next challenges.
