context-free-grammar - 空集合の文脈自由文法?

Question

空集合を生成する CFG を求める宿題があります。私はそれが2つのうちの1つであるべきだと考えていますが、100％確実ではありません.

S->S ですが、これは無限ループになりそうです

と

S-> {} 「空集合」表記ですが、変数でも端子でもない...

Answer 1

有限言語 の文法を書く 1 つの方法Lは、for each win Linclude S -> win grammar です。つまり、すべての単語を書き出します。

たとえば、言語L = ['aa', 'ab', 'ba', 'bb']は文脈自由文法によって生成されます。

S -> 'aa'
S -> 'ab'
S -> 'ba'
S -> 'bb'

もちろん、通常はもっと簡潔な文法があります!

.

あなたの例ではL = [ {} ]。あなたの懸念に明確に答えるために：空のセットは端末ですが、それを記述するために使用する値は、プログラミング言語に大きく依存します（Pythonでは選択できますset()）。