-1

文脈自由文法: (e はイプシロンを表します)

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

それは正しい線形文法に変換できることを意味する通常の言語を生成できます。CFG を RLG に変換する一般的なルールはありますか?

4

1 に答える 1

1

CFG を右線形文法に変換するための一般的なアルゴリズムはありません。右線形文法は、文脈自由言語の厳密なサブセットである正規言語を正確に生成するためです。したがって、この変換を実行する一般的なアルゴリズムが存在する場合、すべての文脈自由言語が規則的であることが証明されますが、これは誤りであることが知られています。

お役に立てれば！

于 2013-02-07T02:17:51.410 に答える