algorithm - 文脈自由文法

Question

特定の文脈自由文法からすべての文字列を生成するアルゴリズムはありますか?

Answer 1

レオナルドの答えは技術的に正しいです。多くの場合、そのセットは無限であるため、一般的な CFGの単語のセットを返す終了アルゴリズムはありません。

しかし、CFGの一連の単語を生成するアルゴリズムがあり、文法に一致するすべての単語が「最終的に」表示されます。あなたの目的には、これらの 1 つで十分です。yieldPython などの言語でこれらの 1 つを記述するのはかなり簡単です。

そのようなアルゴリズムのスケッチ (かなり絶望的な疑似コードで、私は恐れています):

generate(g):
    if g is empty:
        yield ""
    otherwise if g is a terminal a:
        yield "a"
    otherwise if g is a single nonterminal:
        for c in every construction of g:
            start a generator for generate(c)
        until all generators are exhausted:
            looping over each nonexhausted generator gen:
                yield "a" where a = next(gen)
    otherwise if g is a pair of symbols m and n:
        for c in every construction of m:
            start a generator in set 1 for generate(c)
        for d in every construction of m:
            start a generator in set 2 for generate(d)
        until all in set 1 or all in set 2 are exhausted:
            loop over all pairs gen1,gen2 of nonexhausted in set 1 and set 2:
                yield "a b" where a = next(gen1) and b = next(gen2)

各構造が 0 から 2 端子になるように文法が変換されていると仮定すると、これは文法のすべての解析ツリーのツリーに対して幅優先検索を実行します。特定のサブツリーのサイズは無限である可能性があるため、BFS が必要です。

特定の解析ツリーが具体化するのを待機する時間とメモリ コストは任意ですが、その解析ツリーでは有限です。

Answer 2

Q：特定の文脈自由文法からすべての文字列を生成するアルゴリズムはありますか？

A：いいえ、文法は単語を定義するための一連のルールです。特定の文法は特定の数の単語を生成しますが、大多数は無限の単語を生成するため、特定の文法からすべての文字列を生成するアルゴリズムはありません。