L = {a n | n >= 0}、ここ
で
、すべての n >= 1 について。
したがって、L は、長さ 0 のシーケンスを含む、すべての長さの a のシーケンスで構成されます。L2 を L の任意の無限サブセットとします。(L2)* を認識する DFA が常に存在することを示す必要があります。
L2 が有限部分集合である場合、L2 は DFA であり、したがってクリーネ クロージャによって L2* は DFA によって認識されるため、非常に明白です。しかし、文字列の長さが素数などの場合、L2 が DFA として表現されない可能性があるため、無限サブセットの場合は取得できません。
すべての文字列 a n , n >= 0 のセット L を記述する DFA は存在しますが、L のすべてのサブセットに対して DFA が存在するという保証はありません。これは、言語を記述する DFA が存在しない 1 つの例です。
正しいアプローチは、(L')* が L のサブセット L' の正規言語であることを直接証明することです。
GCD(K) = GCD w ∈ K, |w|を定義しましょう。> 0 (|w|)、ここで、K は L の任意の空でないサブセットです。言語 K のすべての空でない単語のすべての長さの最大公約数をGCD(K) と呼ぶことができます。この定義は、L の有限部分集合と無限部分集合の両方に適用されます。
同様に、LCM(K) = LCM w ∈ K, |w|を定義できます。> 0 (|w|)、ここで、K はLの空 でない 有限部分集合です。
GCD(L') = 1 のとき、すべての文字列 a n , n >= M が言語 (L')* に属する数 M が存在することを証明しようとします。これにより、 (L')* は正規言語になります。これは、次の形式の正規表現を作成できるためです。
長さが M 未満で (L')* に属するすべての文字列
OR
長さが M 以上のすべての文字列
上記の正規表現には、M + 1 状態を持つ対応する DFA があります。
GCD(L') > 1 の場合、サブセット L' 内のすべての単語を GCD(L') で「除算」することにより、問題を GCD = 1 の場合に減らすことができます。
GCD(L') = 1 (集合ごとの互いに素) の場合、S 内のすべての文字列の長さの GCD も 1 である L' の有限部分集合 S が存在します。
上記の主張は、構成によって証明できます。
- L', |w 1 |から任意の要素 w 1を選択します。> 0 および構成集合 S 1 = {w 1 }
- GCD(S n ) = 1 の場合、S nが求めたい集合です。
- GCD(S n ) > 1 の場合、L' から要素 w n+1を選び、集合 S n+1 = {w n+1 } ∪ S nを構築して、
GCD(S n+1 ) < GCD(S n )GCD(S n ) > 1 の場合、セットに追加すると GCD を減少させるセット L' の要素が常に存在します。それ以外の場合、セット L' の GCD は 1 になりません。また、最初の要素の長さ w 1には有限個の因数があるため、最終セット S のサイズは有限です。
問題に戻ると、L の部分集合 L' に対して、GCD(L') = GCD(S) を満たす L' の有限部分集合 S を見つけることができます。集合 S から |S| で一般化された線形ディオファントス方程式を構築できます。未知数 a i :
a 1 |w 1 | + a 2 |w 2 | + ... + a |S| |w |S| | | = c ここで、c は非負の整数です
GCD(S) = 1 であるため、上記の方程式は常に可解であり、線形ディオファントス方程式 ax + by = c の最も単純な形式に解を再帰的に適用します。
上記の一般化されたディオファントス方程式を c = 0 ～ (LCM(S) - 1) について解きます。解 (a 1、a 2、...、a |S| ) には負の数を含めることができます。ただし、すべての解が非負の数のみを含むようになるまで、方程式の両側に LCM(S) の倍数を追加し続けることができます。
k を LCM(S) の最小倍数とし、c = k * LCM(S) + q、q = 0 から (LCM(S) - 1) までのすべてのディオファントス方程式が非負の解を持つようにします。次に、M を k * LCM(S) として定義できます。これは、長さが M より大きい文字列は、S 内の単語の連結として分解できるためです (つまり、L' 内)。
L' は、長さが素数である L 内のすべての文字列の集合であるとします。
集合 S = {a 2 , a 5 }を構成しましょう。S は {a 2 , a 19 } または {a 5 , a 23 } のどちらでもかまいませんが、実際には問題ではありません。M の最終値は異なる場合がありますが、(L')* が正規言語であるという事実には影響しません。
10 個の方程式を (個別に) 解く必要があります。
2a 1 + 5a 2 = 0 => (a 1 , a 2 ) = (0, 0)
2a 1 + 5a 2 = 1 => (a 1 , a 2 ) = (3, -1)
2a 1 + 5a 2 = 2 => (a 1 , a 2 ) = (1, 0)
2a 1 + 5a 2 = 3 => (a 1 , a 2 ) = (-1, 1)
2a 1 + 5a 2 = 4 => ( a 1 , a 2 ) = (2, 0)
2a 1 + 5a 2 = 5 => (a 1, a 2 ) = (0, 1)
2a 1 + 5a 2 = 6 => (a 1 , a 2 ) = (3, 0)
2a 1 + 5a 2 = 7 => (a 1 , a 2 ) = ( 1, 1)
2a 1 + 5a 2 = 8 => (a 1 , a 2 ) = (4, 0)
2a 1 + 5a 2 = 9 => (a 1 , a 2 ) = (2, 1)
LCM(2,5) = 10 を 1 つ追加します。LCM の性質により、再度解かなくても解を直接変更できることに注意してください。
2a 1 + (5a 2 + 10) = 1 + 10 => (a 1 , a 2 ) = (3, 1)
(2a 1 + 10) + 5a 2 = 3 + 10 => (a 1 , a 2 ) = (4, 1)
すべての解が非負であり、LCM(2,5) を 1 つだけ追加するため、M = 10 です。
(L')* の正規表現は次のように作成できます。
a 2 +a 4 +a 5 +a 6 +a 7 +a 8 +a 9 +a 10 a*
正規表現はあまりコンパクトではありませんが、ここでは問題にしません。証明のために、すべての n >= M に対してnが (L')* に属するような数 M が存在することを知る必要があるだけです。これは、有限数の状態があり、DFA を構築できることを意味します。 .