Bổ đề bơm: nếu L chính quy thì tồn tại độ dài bơm p sao cho mọi s ∈ L với |s| ≥ p có phân tách s = xyz, |xy| ≤ p, |y| ≥ 1, và x·yⁱ·z ∈ L với mọi i ≥ 0. Nếu tìm được một s mà không phân tách nào bơm được, thì L không chính quy.
Cho p, K, một chuỗi s (với |s| ≥ p) và ngôn ngữ mẫu L (liệt kê đầy đủ các thành viên liên quan). Hãy kiểm tra: có tồn tại phân tách s = xyz (|xy| ≤ p, |y| ≥ 1) sao cho x·yⁱ·z ∈ L với mọi i = 0..K hay không. In PUMPABLE nếu có, ngược lại NOT_PUMPABLE.
Ví dụ với L = {aⁿbⁿ} (mẫu), chuỗi s = aabb thường cho NOT_PUMPABLE — bằng chứng L không chính quy.
Dòng 1: p K. Dòng 2: chuỗi s. Dòng 3: n. n dòng: các chuỗi của L.
1 ≤ p ≤ |s| ≤ 50, 0 ≤ K ≤ 10, 1 ≤ n ≤ 500.
Một dòng: PUMPABLE hoặc NOT_PUMPABLE.
Ví dụ:
Đầu vào:
2 2
aabb
4
ab
aabb
aaabbb
Đầu ra:
NOT_PUMPABLE
Giải thích:
Đang tải editor...