Contoh bahasa bebas non-konteks yang tetap BISA dipompa?

Jadi pada dasarnya L memenuhi kondisi lemma pemompaan untuk CFL tetapi bukan CFL (itu mungkin menurut definisi lemma).

Contoh klasiknya adalah . Wise menunjukkan dalam makalahnya Sebuah lemma pemompaan yang kuat untuk bahasa bebas konteks bahwa baik Bar-Hillel yang memompa lemma atau teorema Parikh (yang menyatakan bahwa rangkaian panjang kata dalam bahasa bebas konteks adalah semi-linear) dapat digunakan untuk membuktikan bahwa L tidak bebas konteks. Trik lain seperti bersinggungan dengan bahasa biasa juga tidak membantu. (Lemma Ogden, generalisasi dari lemma pemompaan Bar-Hillel, memang membuktikan bahwa $L = \{ a^i b^j c^k : i,j,k \text{ all different} \}$$L$$L$tidak bebas konteks.) Ia juga menyediakan lemma pemompaan alternatif yang setara dengan kehalusan konteks (untuk bahasa yang dapat dihitung), dan menggunakannya untuk membuktikan bahwa tidak bebas konteks.$L$

Lemma pemompaan Wise menyatakan bahwa bahasa bebas konteks jika dan hanya jika ada (tidak dibatasi) tata bahasa menghasilkan G L dan bilangan bulat k sehingga setiap kali G menghasilkan "bentuk sentimental" s (sehingga s dapat mencakup non-terminal) panjang | s | > k , kita dapat menulis s = u v x y z di mana x , v y tidak kosong, | v x y | ≤ $L$$G$$L$$k$$G$$s$$s$$|s| > k$$s = uvxyz$$x,vy$$|vxy| \leq k$, dan ada non-terminal sehingga G menghasilkan u A z dan A menghasilkan v A y dan x .$A$$G$$uAz$$A$$vAy$$x$

Dengan berulang kali menerapkan kondisi dalam lemma, Wise dapat membuktikan bahwa tidak bebas konteks, tetapi detailnya agak rumit. Dia juga memberikan kondisi setara yang lebih rumit, dan menggunakannya untuk membuktikan bahwa bahasa { a n b a n m : n , m > 0 } tidak dapat ditulis sebagai persimpangan terbatas dari bahasa bebas konteks.$L$$\{ a^n b a^{nm} : n,m > 0 \}$

Jika Anda tidak dapat mengakses kertas Wise (di balik paywall), ada versi yang diketik yang keluar sebagai laporan teknis universitas Indiana.

---

Bahasa bebas-konteks yang memenuhi kondisi pemompaan lemma Ogden diberikan oleh Johnsonbaugh dan Miller, Kebalikan dari memompa lemma , dan dikaitkan di sana dengan Boasson dan Horvath, Pada bahasa yang memuaskan lemma Ogden . Bahasa yang dimaksud adalah Kita dapat menulisL′=L1∪

$$\begin{align*} L' &= \bigcup_{n \geq 1} (e^+a^+d^+)^n(e^+b^+d^+)^n(e^+c^+d^+)^n \\ &\cup (a+b+c+d)\Sigma^* \cup \Sigma^*(a+b+c+e) \cup \Sigma^*(ed+d(a+b+c)+(a+b+c)e)\Sigma^*. \end{align*}$$ , sesuai dengan dua garis yang berbeda. Perhatikan bahwa L 1 ∩ L 2 = ∅ dan bahwa L 2 adalah teratur. Lemma Ogden dapat digunakan untuk membuktikan bahwa L 1 tidak bebas konteks, dan begitu juga L ′ , tetapi tidak dapat digunakansecara langsunguntuk menunjukkan bahwa L ′ tidak bebas konteks.$L' = L_1 \cup L_2$$L_1 \cap L_2 = \emptyset$$L_2$$L_1$$L'$$L'$

Lebih sederhana: . Selalu dapat memompa a ; persimpangan dengan teratur L ( a b + c + d + ) memberikan non-CFL (dan yang dapat dibuktikan dengan memompa lemma).$\{a^m b^n c^n d^n\colon m \ge 1, n \ge 1\}$$a$$\mathcal{L}(a b^+ c^+ d^+)$

A simple language is $\{a b^n c^n d^n \colon n \ge 1\} \cup \mathcal{L}(a a^+ b^+ c^+ d^+)$. Intersect with $\mathcal{L}(a b^+ c^+ d^+)$ to get a clearly non-CFL, but you can always pump the $a$, and mimetize the equal-length-ness in the sea of ${}^+$.