CFL Pompalama Lemmasının doğru uygulanması

Question

Dilini göstermekle ilgili bu soruya rastladım $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$içerikten bağımsızdır ancak Peter Linz'in kitabında doğrusal değildir. Bu, doğrusal diller için ayrı pompalama lemması ile kolaylıkla yapılabilir (Linz'in kitabında verildiği gibi), ancak benim sorum farklı.

Belli ki bu bir CFL ve bunun için bir aşağı açılan otomat inşa edilebilir. Ancak, CFL'ler için pompalama lemmasını uygularsam, dile ait olmayan dizeleri pompalayabileceğimi fark ederim, bu da dilin bir CFL olmadığı anlamına gelir. Açıkçası yanlış bir şey yapıyorum.

Linz'de verilen "oyun benzeri" biçime göre, seçtiğini söyle $w = a^mb^mc^{2m}$, $|w| \ge m$. Düşman bir dizi ayrıştırma seçebilir$w = uvxyz$, gibi görünebilirler -:

• $v = a^k, y = a^l$: Nerede $|vxy|$ içinde bulunur $a$dizenin 'ler. Pompa$i = 0$, ve sonra $w_0 = a^{m – (k + l)}b^mc^{2m}$ eşitlik artık geçerli olmadığı için dilde olamaz.
• $v = a^k, y = b^l$: Nerede $v$ içinde $a$ Bölüm, $x$ boyunca yayılır $a$'s ve $b$'s ve $y$ içinde $b$Bölüm. Yine pompa$i = 0$. $w_0 = a^{m – k}b^{m – l}c^{2m}$ dilde olamaz.

Bunun gibi daha çok durum var. CFL PL'nin uygulanmasında nerede yanlış yapıyorum?

Answer 1

CFL için pompalama lemması, eğer $L$ bir CFL, bir sabit var $N \ge 1$ öyle ki herkes için $\omega \in L$ ile $\lvert \omega \rvert \ge N$ bir bölünme var $\sigma = u v w x y$ ile $\lvert v w x \rvert \le N$ ve $v x \ne \varepsilon$ öyle ki $u v^k w x^k y \in L$ hepsi için $k \ge 0$.

(Normal diller için pompalama lemması benzerdir, aşağıdaki tartışma küçük değişiklikler için geçerlidir).

Çelişki ile kanıtlamak istiyorsun $L$bir CFL değildir. Yani varsayıyorsun$L$bir CFL'dir ve lemmaya karşı bir çelişki alır. Bu, ayrıntılı olarak şu anlama gelir:

• Gibi $L$bir CFL'dir, lemmayı karşılar. Özellikle, sabit bir$N$ öyle ki...
• Lemma tüm uzun dizeleri belirttiği gibi$L$ bölünebilir, çalışması kolay olanı seçmekte özgürsünüz.
• Lemma, bazı bölümler olduğunu belirtir.$\omega$öyle ki .... herkes için $k \ge 0$...; lemma ile çelişmek için hiçbir bölünmenin işe yaramadığını kanıtlamanız gerekir . Uygulamada, belirli bir bölümünü alırsınız.$\omega$( herhangi bir bölüm) ve bunun için bazılarını seçin$k$dilde bir dizge vermeyen onun için. Bunu davalara bölmeniz gerekebilir.

Dile ait olmayan veya daha kısa dizeler için ne olur? $N$tamamen alakasızdır. Bazı dizeler pompalanabilir, bazı değerler$k$tüm dizeler için çalışın, ... Önemli olan tek bir dizi için$\omega$(seçtiğiniz) tek bir değerle hiçbir bölüm çalışmaz$k$(yine, sizin seçtiğiniz). Lemma iddia ettiği gibi bunun için çalışan tüm ile, yeterince uzun dizeleri bazı için bölünme tüm $k$bir karşı örnek yeterlidir. Sonsuz örnekler hiçbir şeyi kanıtlamaz.