Penerapan yang benar dari CFL Pumping Lemma

Aug 16 2020

Saya menemukan pertanyaan ini tentang menunjukkan bahasa itu $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$bebas konteks tetapi tidak linier dalam buku oleh Peter Linz. Hal itu mudah dilakukan dengan lemma pemompaan terpisah untuk bahasa linier (seperti yang diberikan dalam buku Linz), tetapi pertanyaan saya berbeda.

Jelas ini adalah CFL, dan robot pushdown dapat dibuat untuknya. Tetapi jika saya menerapkan lemma pemompaan untuk CFL, saya menemukan bahwa saya dapat memompa string yang tidak termasuk dalam bahasa tersebut, yang berarti bahasanya bukan CFL. Jelas saya melakukan sesuatu yang salah.

Menggunakan format "seperti permainan" yang diberikan di Linz, katakanlah Anda memilih $w = a^mb^mc^{2m}$, $|w| \ge m$. Musuh dapat memilih sejumlah dekomposisi$w = uvxyz$, mereka bisa terlihat seperti -:

  • $v = a^k, y = a^l$: Kasus dimana $|vxy|$ terkandung di dalam $a$dari senar. Pompa$i = 0$, lalu $w_0 = a^{m – (k + l)}b^mc^{2m}$ tidak bisa dalam bahasa karena kesetaraan tidak lagi berlaku.
  • $v = a^k, y = b^l$: Kasus dimana $v$ ada di $a$ bagian, $x$ membentang di seluruh $a$dan $b$'s, dan $y$ ada di $b$bagian. Sekali lagi, pompa$i = 0$. $w_0 = a^{m – k}b^{m – l}c^{2m}$ tidak bisa dalam bahasa.

Ada lebih banyak kasus seperti ini. Di mana kesalahan saya dalam penerapan CFL PL?

Jawaban

1 vonbrand Aug 17 2020 at 08:20

Lemma pemompaan untuk CFL menyatakan bahwa jika $L$ adalah CFL, ada konstanta $N \ge 1$ seperti itu untuk semua $\omega \in L$ dengan $\lvert \omega \rvert \ge N$ ada divisi $\sigma = u v w x y$ dengan $\lvert v w x \rvert \le N$ dan $v x \ne \varepsilon$ seperti yang $u v^k w x^k y \in L$ untuk semua $k \ge 0$.

(Lemma pemompaan untuk bahasa biasa serupa, pembahasan di bawah ini berlaku dengan sedikit perubahan).

Anda ingin membuktikan dengan kontradiksi itu $L$bukan CFL. Jadi Anda berasumsi$L$adalah CFL, dan mendapatkan kontradiksi dengan lemma. Artinya, secara detail:

  • Sebagai $L$adalah CFL, itu memenuhi lemma. Secara khusus, ada konstanta$N$ seperti yang...
  • Seperti yang dinyatakan lemma semua string panjang masuk$L$ dapat dibagi, Anda bebas memilih salah satu yang mudah dikerjakan.
  • Lemma menyatakan ada beberapa pembagian$\omega$seperti itu .... untuk semua $k \ge 0$...; untuk menentang lemma Anda harus membuktikan tidak ada pembagian yang berhasil. Dalam praktiknya, Anda mengambil pembagian tertentu dari Anda$\omega$( divisi apapun ) dan untuk itu pilihlah beberapa$k$untuk itu yang tidak memberikan string dalam bahasa tersebut. Anda mungkin perlu membagi ini menjadi beberapa kasus.

Apa yang terjadi untuk string yang bukan milik bahasa tersebut, atau lebih pendek dari $N$, sama sekali tidak relevan. Mungkin beberapa string dapat dipompa, beberapa nilai$k$bekerja untuk semua string, ... Yang terpenting adalah untuk satu string$\omega$(yang Anda pilih) tidak ada pembagian yang bekerja dengan satu nilai$k$(sekali lagi, yang Anda pilih). Seperti yang dinyatakan lemma, ia bekerja untuk semua string yang cukup panjang, dengan beberapa pembagian untuk semua $k$, satu contoh balasan sudah cukup. Contoh tak terbatas tidak membuktikan apa-apa.