-1

上下文无关文法：（e代表epsilon）

  S --> aSb|aSa|bSa|bSb|e

它可以生成正则语言，这意味着它可以转换为正确的线性语法。是否有将 CFG 转换为 RLG 的一般规则？

4

1 回答 1

1

没有将 CFG 转换为右线性文法的通用算法，因为右线性文法精确生成正则语言，它们是上下文无关语言的严格子集。因此，如果存在执行这种转换的通用算法，它将证明所有上下文无关语言都是正则的，这被认为是错误的。

希望这可以帮助！

于 2013-02-07T02:17:51.410 回答