9

ご存知のように、通常の文法が与えられた場合、その正規表現を取得するアルゴリズムがあります。

しかし、指定された文法が文脈自由文法である場合 (ただし、通常の言語しか生成しない)、次のようになります。

  • S->aAb
  • A->bB
  • B->cB|d

    一般的に正規表現を取得できる既存のアルゴリズムはありますか?

    ありがとう！</p>

    • 4

    1 に答える 1

    2

    最も一般的な意味では、解決策はありません。CFG が正則かどうかを判断する問題は決定不可能です (Greibach Theorem、http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdfの最後の 3 ページ) CFG を正規表現に変換できれば、任意の文法でそのアルゴリズムを使用し、その成功/失敗を使用して言語が正規であるかどうかを判断できます。

    代わりに、CFG が通常の言語を生成することが知られている場合、その言語が既に知られている (したがって、RegEx に直接変換できる) か、利用する文法のプロパティがあります。各プロパティには、正規表現に変換するための独自のアルゴリズムがあります。

    たとえば、文法が右線形の場合、すべての生成は A->bC または A->a の形式になります。これは、次の場合に NFA に変換できます。

    1) すべての非終端の状態に加えて、受け入れ状態があります。

    2) 開始シンボル S は開始状態です。

    3) A->bC は、入力 b での A から B への遷移です。

    4) A->a は、A から入力 a の受け入れ状態への遷移です。

    この NFA は、状態の除去によって正規表現に変換できます ( http://www.math.uaa.alaska.edu/~afkjm/cs351/handouts/regular-expressions.pdfの 5 ～ 8 ページ)。左線形文法の類似のプロセスでは、開始状態と受け入れ状態が交換されます。

    さらに、通常の言語のクロージャ プロパティを利用することもできます。たとえば、質問の言語は直線的ではありませんが、S->S'b、S'->aA と書くことができます。ここで、S' は右線形であり、S は 2 つのバラバラな線形文法の連結です。最終式の 2 つの式を連結します。ユニオンの同様のロジック。

    于 2012-11-04T19:44:17.690 に答える