How to deal with loops when converting from context free to CNF?

1
votes

Let's say there is a grammar

  • S -> PQT
  • R -> T
  • U -> aU | bX
  • X -> Y
  • P -> bQ
  • Y -> SX | c | X
  • Q -> aRY
  • T -> U

There is a loop:

  • X -> Y
  • Y -> X

How to eliminate it when converting to CNF? I don't think it's fine to add a rule to grammar (as in unit elimination) X -> X, right, because it s basically another loop?

1
loopscontext-free-grammarautomatachomsky-normal-form

1 Answers

1
votes

If X -> Y and Y -> X, the nonterminal symbols are interchangeable and you can safely replace all instances of either of the two with the other of the two, eliminating one of the two completely. As you also pointed out, rules of the form X -> X can be safely eliminated. So this grammar is equivalent to the one you give:

S -> PQT
R -> T
U -> aU | bX
P -> bQ
X -> SX | c
Q -> aRX
T -> U

And so is this one:

S -> PQT
R -> T
U -> aU | bY
P -> bQ
Y -> SY | c
Q -> aRY
T -> U