Bổ đề bơm cho ngôn ngữ phi ngữ cảnh (CFL) tách w = u v x y z và bơm đồng thời hai đoạn v, y lên i lần: u·vⁱ·x·yⁱ·z.
Cho w, bốn chỉ số a ≤ b ≤ c ≤ d (u = w[0..a), v = w[a..b), x = w[b..c), y = w[c..d), z = w[d..)) và số mũ i, hãy in u·vⁱ·x·yⁱ·z.
Ví dụ: w = aabb, a=1,b=2,c=2,d=3, i=2 → u=a, v=a, x='', y=b, z=b → a·aa··bb·b = aaabbb.
Dòng 1: w. Dòng 2: bốn số a b c d. Dòng 3: i.
0 ≤ a ≤ b ≤ c ≤ d ≤ |w| ≤ 100, 0 ≤ i ≤ 50.
Một dòng: u·vⁱ·x·yⁱ·z.
Ví dụ:
Đầu vào:
aabb
1 2 2 3
2
Đầu ra:
aaabbb
Giải thích:
Đang tải editor...