Ứng dụng đúng của Bổ đề bơm CFL

Question

Tôi đã gặp câu hỏi này về việc hiển thị rằng ngôn ngữ $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$không có ngữ cảnh nhưng không tuyến tính trong sách của Peter Linz. Điều đó có thể dễ dàng thực hiện được bằng bổ đề bơm riêng biệt cho các ngôn ngữ tuyến tính (như được đưa ra trong cuốn sách của Linz), nhưng câu hỏi của tôi thì khác.

Rõ ràng đây là một CFL và có thể xây dựng một động cơ tự động đẩy xuống cho nó. Nhưng nếu tôi áp dụng bổ đề bơm cho CFL, tôi thấy rằng tôi có thể bơm các chuỗi không thuộc về ngôn ngữ, điều đó có nghĩa là ngôn ngữ đó không phải là CFL. Rõ ràng là tôi đang làm sai.

Theo định dạng "giống trò chơi" được đưa ra trong Linz, giả sử bạn chọn $w = a^mb^mc^{2m}$, $|w| \ge m$. Kẻ thù có thể chọn một số cách phân tách$w = uvxyz$, chúng có thể trông giống như -:

• $v = a^k, y = a^l$: Trường hợp mà $|vxy|$ được chứa trong $a$của chuỗi. Máy bơm$i = 0$, và sau đó $w_0 = a^{m – (k + l)}b^mc^{2m}$ không thể có trong ngôn ngữ vì sự bình đẳng không còn giữ.
• $v = a^k, y = b^l$: Trường hợp mà $v$ là trong $a$ phần, $x$ kéo dài qua $a$'cát $b$'cát $y$ là trong $b$phần. Một lần nữa, bơm$i = 0$. $w_0 = a^{m – k}b^{m – l}c^{2m}$ không thể bằng ngôn ngữ.

Có nhiều trường hợp như thế này. Tôi đã sai ở đâu trong việc áp dụng CFL PL?

Answer 1

Bổ đề bơm cho CFL nói rằng nếu $L$ là một CFL, tồn tại một hằng số $N \ge 1$ như vậy cho tất cả $\omega \in L$ với $\lvert \omega \rvert \ge N$ có một sự phân chia $\sigma = u v w x y$ với $\lvert v w x \rvert \le N$ và $v x \ne \varepsilon$ như vậy mà $u v^k w x^k y \in L$ cho tất cả $k \ge 0$.

(Bổ đề bơm cho các ngôn ngữ thông thường cũng tương tự, cuộc thảo luận bên dưới áp dụng với những thay đổi nhỏ).

Bạn muốn chứng minh bằng mâu thuẫn rằng $L$không phải là CFL. Vì vậy, bạn giả sử$L$là một CFL, và nhận được một mâu thuẫn với bổ đề. Điều này có nghĩa là, chi tiết:

• Như $L$là một CFL, nó thỏa mãn bổ đề. Đặc biệt, có một hằng số$N$ như vậy mà...
• Khi bổ đề cho biết tất cả các chuỗi dài trong$L$ có thể được phân chia, bạn có thể tự do chọn một cái dễ làm việc.
• Bổ đề nói rằng có một số phân chia của$\omega$như vậy .... cho tất cả $k \ge 0$...; để mâu thuẫn với bổ đề bạn phải chứng minh rằng không có phép chia nào hoạt động. Trong thực tế, bạn lấy một phần đã cho của$\omega$( bất kỳ bộ phận nào ) và chọn một số$k$vì nó không cung cấp một chuỗi trong ngôn ngữ. Bạn có thể cần phải chia điều này thành các trường hợp.

Điều gì xảy ra đối với các chuỗi không thuộc về ngôn ngữ hoặc ngắn hơn $N$, là hoàn toàn không liên quan. Có thể là một số chuỗi có thể được bơm, một số giá trị của$k$làm việc cho tất cả các chuỗi, ... Điều quan trọng là đối với một chuỗi$\omega$(cái bạn đã chọn) không có bộ phận nào hoạt động với một giá trị là$k$(một lần nữa, một trong những bạn đã chọn). Như bổ đề khẳng định nó hoạt động với tất cả các chuỗi đủ dài, với một số phép chia cho tất cả $k$, một ví dụ là đủ. Ví dụ vô hạn chứng minh không có gì.