ポンピング補題を使用して文脈自由でないことを証明していますか？

Question

私は、言語L = {a^n！ | n> = 0}は、ポンピング補題を使用して文脈自由ではない。しかし、私はuvxyz自体に分割する方法に立ち往生しています。唯一のsymol私は非常にトリッキーなそれを見つけるので。

Answer 1

Lから与えられた単語wをポンピングした結果の言語Pを見てください。| vy |すべてのポンピングが| vy |を加算するので、次のものから|シンボル。

一方、2つの階乗の間のギャップは常に大きくなります。明らかに、例えば（| vy | +2）！ - （| vy | +1）！ > | vy |。しかし、これは、^（| vy | +1）！の間にPの中にいくつかの単語があることを意味します。とa ^（| vy | +2）！この単語がLにないので、ポンピング状態に違反します。