Возможно ли для неоднозначного CFG преобразовать в CNF и стать однозначным?

Question

Возможно ли для неоднозначной контекстно-свободной грамматики (CFG) преобразоваться в нормальную форму Хомского (CNF) и стать однозначной?

Answer 1

Конечно. Все, что вам действительно нужно, это один пример, чтобы показать, что это возможно. Рассмотрим неоднозначную грамматику

S :- A | B
A :- a
B :- a

Эта грамматика эквивалентна следующей грамматике в CNF

S :- a

Эта грамматика не является неоднозначной.