上下文无关语法：（e代表epsilon）
S --> aSb|aSa|bSa|bSb|e
它可以生成常规语言，这意味着它可以转换为正确的线性语法 . 是否有将CFG转换为RLG的一般规则？
没有用于将CFG转换为右线性语法的通用算法，因为右线性语法精确地生成常规语言，这是无上下文语言的严格子集 . 因此，如果存在执行该转换的通用算法，则证明所有无上下文的语言都是规则的，这已知是错误的 .
希望这可以帮助！
1 回答
没有用于将CFG转换为右线性语法的通用算法，因为右线性语法精确地生成常规语言，这是无上下文语言的严格子集 . 因此，如果存在执行该转换的通用算法，则证明所有无上下文的语言都是规则的，这已知是错误的 .
希望这可以帮助！