Bổ đề bơm cho ngữ pháp thông thường
Định lý
Hãy để L là một ngôn ngữ thông thường. Sau đó, tồn tại một hằng số‘c’ như vậy cho mọi chuỗi w trong L -
|w| ≥ c
Chúng ta có thể phá vỡ w thành ba chuỗi, w = xyz, như vậy -
- | y | > 0
- | xy | ≤ c
- Với mọi k ≥ 0, chuỗi xy k z cũng nằm trong L.
Các ứng dụng của bổ đề bơm
Bổ đề Pumping được áp dụng để chỉ ra rằng một số ngôn ngữ nhất định không chính quy. Nó không bao giờ được sử dụng để thể hiện một ngôn ngữ là thông thường.
Nếu L là chính quy, nó thỏa mãn Bổ đề Bơm.
Nếu L không thỏa mãn Bổ đề Bơm, nó không chính quy.
Phương pháp chứng minh rằng một ngôn ngữ L không chính quy
Lúc đầu, chúng ta phải giả định rằng L là thường xuyên.
Vì vậy, bổ đề bơm nên giữ cho L.
Sử dụng bổ đề bơm để thu được mâu thuẫn -
Lựa chọn w như vậy mà |w| ≥ c
Lựa chọn y như vậy mà |y| ≥ 1
Lựa chọn x như vậy mà |xy| ≤ c
Gán chuỗi còn lại cho z.
Lựa chọn k sao cho chuỗi kết quả không nằm trong L.
Hence L is not regular.
Problem
Chứng minh rằng L = {aibi | i ≥ 0} không thường xuyên.
Solution -
Lúc đầu, chúng tôi giả định rằng L là chính quy và n là số trạng thái.
Cho w = a n b n . Do đó | w | = 2n ≥ n.
Bằng cách bơm bổ đề, cho w = xyz, trong đó | xy | ≤ n.
Cho x = a p , y = a q , và z = a r b n , trong đó p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Như vậy | y | ≠ 0.
Cho k = 2. Khi đó xy 2 z = a p a 2q a r b n .
Số as = (p + 2q + r) = (p + q + r) + q = n + q
Do đó, xy 2 z = a n + q b n . Vì q ≠ 0 nên xy 2 z không có dạng a n b n .
Do đó, xy 2 z không nằm trong L. Do đó L không chính quy.