context-free-grammar - 0,1 を超えるダブルワードの補数の文脈自由文法は何ですか?

Question

L={ww|w は {0,1}* に属する} の補集合の CFG は?

Answer 1

まず第一に、奇妙な単語は言語の一部であるという事実を観察してください。次の言語を定義しましょう。

L1={w1w|w{0,1}*}、L0={w0w|w{0,1}*}。

これらの言語は、次の CFG で定義できます。

S0/1 -> |0S0|1S1|0S1|1S0

次に L3 を見てください。

L3=(L1)U(L2)U(L1L2)U(L2L1)

結合と連結への閉鎖から解放されたコンテキストです。
L3 が探している言語であることを証明しましょう。まず第一に、これまで見てきたように、可能なすべての奇数長の単語を扱います。偶数の長さの単語については、それらがその言語にある場合、少なくとも単語の両側で異なる 1 対の終端があります。このペアを a と b と呼びます。すべての偶数単語は、次のように分割できます。

(x_1^m)(a)(x_2^m)(y_1^n)(b)(y_2^n)

そしてこれはまさに

(L1L2)U(L2L1)

これは、CFG 言語が補数で閉じられていないことを意味します。