Bổ đề bơm cho CFG
Bổ đề
Nếu L là một ngôn ngữ không có ngữ cảnh, có độ dài p sao cho bất kỳ chuỗi nào w ∈ L chiều dài ≥ p có thể được viết như w = uvxyz, Ở đâu vy ≠ ε, |vxy| ≤ pvà cho tất cả i ≥ 0, uvixyiz ∈ L.
Các ứng dụng của bổ đề bơm
Bổ đề Pumping được sử dụng để kiểm tra xem một ngữ pháp có phải là ngữ cảnh hay không. Hãy để chúng tôi lấy một ví dụ và chỉ ra cách nó được kiểm tra.
Vấn đề
Tìm hiểu liệu ngôn ngữ L = {xnynzn | n ≥ 1} ngữ cảnh có tự do hay không.
Giải pháp
Để cho Lkhông có ngữ cảnh. Sau đó,L phải thỏa mãn bổ đề bơm.
Lúc đầu, hãy chọn một số ncủa bổ đề bơm. Sau đó, lấy z là 0 n 1 n 2 n .
Phá vỡ z thành uvwxy, Ở đâu
|vwx| ≤ n and vx ≠ ε.
Vì thế vwxkhông thể liên quan đến cả 0 và 2, vì 0 cuối cùng và 2 đầu tiên cách nhau ít nhất (n + 1) vị trí. Có hai trường hợp -
Case 1 - vwxkhông có 2s. Sau đóvxchỉ có 0 và 1. Sau đóuwy, mà sẽ phải ở L, có n 2 giây, nhưng ít hơn n 0 hoặc 1s.
Case 2 - vwx không có số 0.
Tại đây xảy ra mâu thuẫn.
Vì thế, L không phải là một ngôn ngữ không có ngữ cảnh.