Last year quiz 3 question 3

Last year quiz 3 question 3

by Xiaoyu Lin -
Number of replies: 2

Hello,

In last year's quiz 3 question 2, to implement SCFG, we have to transform the given rules and lexicon into CNF. In the first method given in solution, can we combine rule X-NP,VP, and Z-NP,VP together?  In other words, can we use X to replace Z in the CYK algorithm?

ThanksFirst method for CNF transformation

In reply to Xiaoyu Lin

Re: Last year quiz 3 question 3

by Jean-Cédric Chappelier -

First of all: we transform it into extended CNF, not pure CNF: we keep the unary rules.

Now, to answer your question: in this very case, yes; but this is a very special case since both X and Z are NEW non-terminals. I prefer you don't bother and remember only the simplest rule, which always work: introduce a NEW non-terminal FOR EACH of your transformations.

The problem would be when using non-terminals which already represent something else. For instance with

S -> NP VP

S -> NP VP PNP
it is VERY WRONG to change second rule into

S -> S PNP
because then you in fact introduced infinitely many new parses like:

NP VP PNP PNP
NP VP PNP PNP PNP

Makes sense?

In reply to Jean-Cédric Chappelier

Re: Last year quiz 3 question 3

by Xiaoyu Lin -

Thank you, professor. It is clearer to me now.