1

クリーネ閉包演算子（例：（ab）*）のみを含む正規言語Lが与えられた場合、2つの非正規言語の連結によってLを生成できる可能性があることを知りたいですか？私は、Lが2つの正規言語の連結によってのみ生成できることを証明しようとしています。

ありがとう。

4

1 に答える 1

1

このステートメントは誤りです。Σ={a}で次の2つの言語を考えてみましょう。

L 1 = {a n | nは2の累乗です}∪{ε}

L 2 = {a n | nは2の累乗ではありません}∪{ε}

これらの言語はどちらも規則的ではありません（最初の言語はMyhill-Nerodeの定理を使用して非規則的であることが証明でき、2番目の言語はL 1の補集合に密接に関連しており、非規則的であることが証明できます。

ただし、L 1 L 2 =a*であると主張します。まず、連結L 1 L 2の文字列は、a nの形式であるため、a*の要素であることに注意してください。次に、a*の任意の文字列を取得します。nとします。nが2の累乗である場合、L1からのnとL2からのεの連結として形成できます。それ以外の場合、nは2の累乗ではなく、 L1からのεとL2からのnの連結として形成できます。したがって、L 1 L 2 = a *であるため、証明しようとしている定理は誤りです。

お役に立てれば！

于 2014-10-26T21:32:28.903 に答える