是否有可能将不明确的 CFG 转换为 CNF 并变得明确？

Question

有歧义的上下文无关文法（CFG）是否有可能转换成乔姆斯基范式（CNF）并变得无歧义？

Answer 1

当然可以。您真正需要的只是一个示例来说明这是可能的。考虑语法二义性

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

该文法等同于CNF中的以下文法

S :- a

这个语法没有歧义。