Bagaimana saya dapat membuktikan bahwa bahasa ini tidak bebas konteks?

Saya memiliki bahasa berikut

$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$

Saya mencoba menentukan kelas bahasa Chomsky mana yang cocok untuknya. Saya bisa melihat bagaimana itu bisa dibuat menggunakan tata bahasa konteks-sensitif jadi saya tahu itu minimal konteks-sensitif. Sepertinya tidak mungkin membuat dengan tata bahasa bebas konteks, tapi saya punya masalah untuk membuktikannya.

Tampaknya melewati lemma pemompaan garpu karena jika semua ditempatkan di bagian ketiga dari setiap kata (bagian dengan semua 2 s). Itu bisa memompa v dan x sebanyak yang Anda inginkan dan itu akan tetap dalam bahasa. Jika saya salah dapatkah Anda memberi tahu saya alasannya, jika saya benar, saya masih berpikir bahasa ini tidak bebas konteks, jadi bagaimana saya bisa membuktikannya?$uvwxy$$2$$v$$x$

Anda dapat memaksa pemompaan berada di beberapa tempat, menggunakan lemma Ogden , misalnya dengan menandai semua 0.

Misalkan itu bebas konteks, maka lemma Ogden memberi Anda , Anda memberikannya w = 0 p 1 p 2 p yang ada dalam bahasa, dan Anda "menandai" semua 0 itu. Maka segala faktorisasi w = u x y z v harus sedemikian rupa sehingga ada 0 dalam x atau z . Anda juga dapat mengasumsikan x = a k dan z = b m karena x x dan z $p>0$$w=0^p1^p2^p$$w=uxyzv$$0$$x$$z$$x=a^k$$z=b^m$$xx$$zz$ harus substring dari bahasa Anda.

1. Jika maka w = u x 2 y z 2 v memiliki lebih banyak 0 daripada 1$z=0...0$$w=ux^2yz^2v$

2. Jika dan z = 1..1 maka w = u x 2 y z 2 v memiliki lebih banyak 1 daripada 2.$x=0..0$$z=1..1$$w=ux^2yz^2v$

3. Jika dan z = 2..2 maka w = u x 2 y z 2 v memiliki lebih banyak 0 daripada 1.$x=0..0$$z=2..2$$w=ux^2yz^2v$

Jadi bukan kata dari bahasa Anda. Karena itu, tidak bebas konteks.$ux^2yz^2v$

Untuk teknik lain, lihat diskusi: Bagaimana membuktikan bahwa bahasa tidak bebas konteks?

Lemma pemompaan harus menyelesaikan masalah Anda mengenai bagian ketiga dari kata tersebut; perhatikan bahwa ketika Anda membagi , kombinasi u v n w x n y juga ada dalam bahasa, termasuk ketika n = 0 . Coba itu.$z = uvwxy$$uv^nwx^ny$$n = 0$

EDIT: Seperti yang dikatakan jmad , Pumping Lemma seperti permainan:

1. Lemma pemompaan memberi Anda $p$
2. Anda memberikan kata dari bahasa panjang setidaknya $s$$p$
3. Lemma pemompaan menulis ulang seperti ini: dengan beberapa kondisi ( | v x y | ≤ p dan | v y | ≥ 1 )$s=uvxyz$$|vxy|≤p$$|vy|≥1$
4. Anda memberikan bilangan bulat $n≥0$
5. Jika tidak dalam L , Anda menang, L tidak bebas konteks.$uv^nxy^nz$$L$$L$

Jadi yang harus Anda lakukan adalah menyatakan kata, memecah 3 ke dalam kasus, dan menunjukkan bahwa untuk setiap kasus Anda dapat menemukan sehingga kata yang dihasilkan tidak dalam bahasa.$n$

Ketika Anda membagi , pikirkan semua case yang dapat jatuh ke dalam v x y . Anda perhatikan bahwa jika v x y tidak termasuk dalam 2's, maka mudah untuk memompa 0 dan 1 sampai mereka melebihi jumlah 2, dan kemudian Anda memiliki kata yang tidak ada dalam bahasa tersebut. Saran saya adalah, jika v x y jatuh ke 2 wilayah, Anda juga dapat membuat v dan y menghilang dengan menetapkan n = 0 , jadi u v n x y n z = $s=uvxyz$$vxy$$vxy$$vxy$$v$$y$$n=0$ . Kemudian dengan menghilangkan 2 Anda bisa sampai pada kata yang tidak termasuk dalam bahasa tersebut.$uv^nxy^nz = uxz$