二义性CFG(上下文无关文法)是否可以转换为GNF(格里巴赫范式)?

结论 #

你构造的这个二义性上下文无关文法完全可以转换为等价的GNF

核心原理 #

上下文无关文法能否转换为GNF，和文法是否具有二义性没有任何关系。已被严格证明的结论是：所有合法的上下文无关文法，都存在与之等价的Greibach范式（GNF）。
二义性是文法的独立属性，指的是同一个终结符串可以对应多棵不同的语法分析树，和文法采用什么范式表示无关。GNF转换只是统一规范产生式的结构为「右部首字符为终结符，后续跟随零个或多个非终结符」，既不会消除原文法的二义性，也不会因为原文法有二义就无法完成转换，转换得到的GNF仍然会保留原有的二义性特征。

针对你给出的文法的说明 #

你给出的原文法产生式如下：

A → AkS | SA
S → AtA

其中S、A为非终结符，k、t为终结符
这个文法的所有产生式右部都不以终结符开头，实际上不生成任何仅由终结符组成的串，对应的语言是空集，转换后的GNF直接表示为无可用产生式的形式即可。

内容的提问来源于stack exchange，提问作者Saneet Kaul