Как бороться с циклами при конвертации из контекста в CNF? - PullRequest
Новая
       51

Как бороться с циклами при конвертации из контекста в CNF?

0 голосов
/ 02 июня 2018

Допустим, есть грамматика

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

Есть цикл:

  • X -> Y
  • Y -> X

Как устранить это при конвертации в CNF?Я не думаю, что это нормально, чтобы добавить правило к грамматике (как в исключении единиц) X -> X, верно, потому что это в основном другой цикл?

1 Ответ

0 голосов
/ 21 августа 2018

Если X -> Y и Y -> X, нетерминальные символы являются взаимозаменяемыми, и вы можете смело заменять все экземпляры одного из двух на другой из двух, полностью исключая один из двух.Как вы также указали, правила формы X -> X могут быть безопасно устранены.Таким образом, эта грамматика эквивалентна той, которую вы даете: 

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

И вот эта: 

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