context-free-grammar - 模糊的 CFG 是否有可能转换为 CNF 并变得明确？

Question

模棱两可的上下文无关语法（CFG）是否有可能转换为乔姆斯基范式（CNF）并变得明确？

Answer 1

当然。你真正需要的只是一个例子来证明这是可能的。考虑模棱两可的语法

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

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

S :- a

这个语法没有歧义。