Chromsky normal form unit production

74 Views Asked by At

I have the following that I need to convert to CNF:

S -> Aux NP VP
S -> VP
VP -> Verb NP
VP -> VP PP
Verb -> book
Aux -> does

What I have so far is:

S -> X1 VP
X1 -> Aux NP
S -> Verb NP
S -> VP PP
VP -> Verb NP
VP -> VP PP
Verb -> book
Aux -> does

Is that it? What happens to Verb and Aux? My book has the following:

1. Copy all conforming rules to the new grammar unchanged.
2. Convert terminals within rules to dummy non-terminals.
3. Convert unit-productions.
4. Make all rules binary and add them to new grammar
  1. I assume this means all rules with two non-terminals on the right stay
  2. Aux NP is terminal so I turn it to dummy non-terminal X1 -> Aux NP
  3. Not sure what this step is but the book has:

    We can eliminate unit productions by rewriting the right-hand side of the original rules with the right-hand side of all the non-unit production rules that they ultimately lead to

  4. What I have so far seems to be in binary except for Verb and Aux.
0

There are 0 best solutions below