私は次の問題を抱えています：
言語L1={a ^ n * b ^ n：n>=0}およびL2={b ^ n * a ^ n：n> = 0}は文脈自由言語であるため、L1L2の下で閉じられ、L = {a ^ n * b ^ 2n A ^ n：n> = 0}は、クロージャプロパティによって生成されるため、コンテキストフリーである必要があります。
これが本当かどうかを証明しなければなりません。それで私はL言語をチェックしました、そしてそれが文脈自由であるとは思わない、そして私はまたL2がちょうどL1が逆になっているのを見ました。
L1、L2が決定論的であるかどうかを確認する必要がありますか？
L1={a n b n : n>=0} と L2={b n a n : n>=0} はどちらもコンテキスト フリーです。
文脈自由言語は連結で閉じているので、L3=L1L2 も文脈自由です。
ただし、L3 は L4={a n b 2n a n : n >= 0}と同じ言語ではありません。文字列abbbaaは L3 にありますが、L4 にはありません。
では、L4 はコンテキストフリーですか? もしそうなら、それは文脈自由言語のポンピング補題に従わなければなりません。
p を L4 のポンピング長とします。s = a p b 2p a pを選択します。この場合、s は L4 にあり、|s| > p。したがって、L4 が文脈自由であれば、s を |vxy| で uvxyz と書くことができます。<= p, |vy| >= 1、および uv n xy n z は、任意の n >= 0 の L4 にあります。
L4 の空でない文字列の次のプロパティを観察します。 a の数は b の数と同じです。部分文字列 'ab' が 1 回だけ出現し、部分文字列 'ba' が 1 回だけ出現します。a の最初の文字列の長さは、a の最後の文字列の長さと同じです。
これらの観察結果を使用して、L4 のポンピング引数で可能な v と y の選択を制限できます。v と y のどちらにも部分文字列 'ab' を含めることはできません。これは、v と y が任意の回数ポンピングされると、出力文字列に 'ab' が複数回出現するため、L4 の要素にすることができないためです。部分文字列「ba」にも同じ引数が適用されます。
したがって、v は空、すべて a、またはすべて b のいずれかでなければなりません。y についても同様です。
さらに、v がすべて a の場合、y は同じ数の b で構成されている必要があります。それ以外の場合、v と y は同じ n によってポンピングされるため、ポンピングされた文字列には異なる数の a と b が含まれます。同様に、v がすべて b の場合、y は同じ数の a でなければなりません。
しかし、v がすべて a で y がすべて b の場合、a の最後の文字列は v と y をポンピングしても影響を受けないため、a の先頭の文字列は a の末尾の文字列と一致しなくなります。同様に、v がすべて b で y がすべて a の場合、v と y がポンピングされるため、a の先頭と末尾の文字列は再び異なる長さになります。
条件 |vy| に違反するため、v と y の両方を空にすることはできません。>= CFL ポンピング レンマの場合は 1。しかし、|v| を確立したので、= |y| の場合、v も y も空にすることはできません。
しかし、v を空にすることも、すべてを a にすることも、すべてを b にすることもできず、部分文字列 'ab' または 'ba' を含めることもできない場合、s のポンピングされたバージョンがまだ L4 にある uvxyz を選択することはできません。したがって、L4 はコンテキストフリーではありません。
どうかはわかりません -- と の定義のそれぞれで、 はその定義内にスコープされていることに注意してくださいL1。L2つまりn、これらは 2 つの異なる変数です。それらを組み合わせるときは、名前を変更して代わりに取得する必要があります。
L = {a^n * b^n b^m * a^m : n,m>=0}
これはあなたの言語とは大きく異なりますLが、明らかに文脈に依存しない言語です。