এই পর্বে যা শিখবেন
- CFL pumping lemma-র পূর্ণ বক্তব্য: পাঁচ ভাগ uvxyz, দুই শর্ত আর quantifier-এর ক্রম
- CNF parse tree-র উচ্চতা আর pigeonhole দিয়ে lemma-র পূর্ণ প্রমাণ, আর Python-এ সেই প্রমাণ চালিয়ে u, v, x, y, z বের করা
- প্রতিপক্ষের খেলা হিসেবে non-CFL প্রমাণ: anbncn, ww, an², i ≤ j ≤ k
- সবচেয়ে সাধারণ ভুল: |vxy| ≤ p-কে “শুরুর p চিহ্ন” পড়া, বিভাজন বেছে নেওয়া, একটি ক্ষেত্র বাদ দেওয়া
- Ogden-এর lemma দিয়ে এমন ভাষা ধরা, যা সাধারণ lemma পারে না; আর Parikh-এর theorem কেন একক-চিহ্নের CFL-কে regular বানায়
১ · Stack-এরও সীমা আছে — কেন CFL-এর নিজস্ব pumping lemma
পর্ব ১৭-এ আপনি দেখেছেন, সসীম স্মৃতির যন্ত্র anbn গুনতে পারে না। মডিউল ৫ আর ৬ সেই সমস্যার সমাধান দিয়েছে: grammar S → aSb ∣ ε (পর্ব ২৫) আর একটি stack-যুক্ত যন্ত্র, অর্থাৎ pushdown automaton (পর্ব ৩২)। স্বাভাবিক প্রশ্ন: stack কি সব গোনার সমস্যা মেটায়? একটি stack একটি সংখ্যা মনে রাখতে পারে: a পড়ে push, b পড়ে pop. কিন্তু anbncn-এ তিনটি সংখ্যা মেলাতে হয়। b-গুলো দিয়ে a-এর হিসাব মেলাতে গিয়ে stack খালি হয়ে যায়; c পড়ার সময় আর কিছু মনে নেই।
“কোনো PDA পারে না” বলতে হলে আবারও সব সম্ভাব্য PDA বা সব context-free grammar একসঙ্গে বাতিল করতে হয়। পর্ব ১৭-এর কৌশল এখানেও কাজ করে, তবে pigeonhole এবার DFA-র state-এর ওপর নয়, grammar-এর variable-এর ওপর, আর চক্রটি একটি পথে নয়, একটি parse tree-এর ভেতরে।
বাজারঘরের order query ভাষায় শর্ত বন্ধনীর ভেতরে বন্ধনী দিয়ে লেখা যায়: (দাম ≥ 500 AND (জেলা = ঢাকা OR (জেলা = খুলনা AND …))). ধরুন query-র grammar-এ মোট ৫টি variable, যেমন QUERY, COND, TERM ইত্যাদি। খুব লম্বা একটি query-র parse tree-তে ওপর থেকে নিচে নামতে নামতে কোনো এক সময় COND-এর ভেতরে আবার COND আসবেই, কারণ নাম মাত্র ৫টি। টিফিন ক্যারিয়ারের বাটির মতো: বড় COND-এর ভেতরে ছোট COND বসানো। এখন বড় বাটির “বাইরের স্তর” (ভেতরের বাটি বাদে যা থাকে) আরেকবার জুড়ে দিন, বা পুরো বাইরের স্তরটি ফেলে দিয়ে শুধু ছোট বাটি রাখুন, query তবু বৈধ থাকে। বাইরের স্তরের বাঁ দিকের অংশ v আর ডান দিকের অংশ y, তাই দুটি সবসময় একসঙ্গে বাড়ে বা কমে।
এই “দুটি টুকরো একসঙ্গে” ধর্মটিই context-free আর regular-এর পার্থক্য। anbn-এ v = a আর y = b একসঙ্গে বাড়ালে সংখ্যা সমান থাকে, তাই এটি CFL হতে বাধা নেই। anbncn-এ তিনটি সংখ্যা একসঙ্গে বাড়াতে হতো, কিন্তু pump মাত্র দুটি, আর সেগুলো কাছাকাছি থাকে। এই পর্ব এটিকে একটি উপপাদ্য আর পূর্ণ প্রমাণে পরিণত করে।
এই পর্বের notation: CFG G = (V, Σ, R, S), CNF-এ নিয়ম A → BC বা A → a, সঙ্গে শুধু start থেকে S0 → ε (পর্ব ২৯)। Parse tree-র উচ্চতা মানে মূল থেকে সবচেয়ে দূরের পাতা পর্যন্ত edge-এর সংখ্যা। ε ফাঁকা string (কিছু বইয়ে λ), vi মানে v-কে i বার পরপর লেখা, তাই v0 = ε. anbncn দিয়ে বোঝানো হয়েছে {anbncn : n ≥ 0}.
২ · Lemma-র বক্তব্য — পাঁচ ভাগ আর দুই pump
বক্তব্যটি পর্ব ১৭-এর regular pumping lemma-র মতোই গঠনের, শুধু তিন ভাগের জায়গায় পাঁচ ভাগ, আর একটি টুকরোর জায়গায় দুটি টুকরো pump হয়।
L যদি একটি context-free language হয়, তবে একটি পূর্ণসংখ্যা p ≥ 1 আছে (pumping length), যাতে L-এর প্রতিটি string s, যার |s| ≥ p, পাঁচ ভাগে লেখা যায়, s = uvxyz, এমনভাবে যে:
১. |vy| ≥ 1 (v আর y একসঙ্গে ফাঁকা নয়);
২. |vxy| ≤ p (মাঝের তিন ভাগ মিলে সর্বোচ্চ p চিহ্ন);
৩. প্রতিটি i ≥ 0-এর জন্য uvixyiz ∈ L.
Quantifier-এর ক্রম আগের মতোই ∃∀∃∀ (nested quantifier), তাই খেলার নিয়মও একই। তবে দুটি শর্তের অর্থ সাবধানে পড়ুন, কারণ ভুল এখানেই সবচেয়ে বেশি হয়:
- |vy| ≥ 1 বলে v আর y-এর অন্তত একটি ফাঁকা নয়। একটি ফাঁকা হতে পারে: v = ε, y = c হলেও বিভাজন বৈধ।
- |vxy| ≤ p একটি দৈর্ঘ্যের সীমা, অবস্থানের নয়। Regular lemma-র |xy| ≤ p বলত টুকরোটি s-এর শুরুর p চিহ্নে; এখানে vxy s-এর যেকোনো জায়গায় বসতে পারে, শুধু তার দৈর্ঘ্য p-এর বেশি নয়। ফলে s = apbpcp হলে vxy একসঙ্গে a আর c ছুঁতে পারে না, কারণ মাঝে p-টি b.
- i = 0 মানে v আর y দুটিই একসঙ্গে বাদ, i ≥ 2 মানে দুটিই একসঙ্গে বারবার। একটিকে বাড়িয়ে অন্যটি না বাড়ানোর সুযোগ নেই।
- Regular রূপটি এর একটি বিশেষ ক্ষেত্রের মতো: প্রতিটি regular language context-free, তাই সেখানেও এই uvxyz বিভাজন পাওয়া যায়।
Lemma-র ছবি: গাছের ভেতরে একই variable দুবার
বড় ত্রিভুজ পুরো parse tree. একটি লম্বা পথে variable R দুবার এসেছে। নিচের R-এর উপগাছের পাতা x; ওপরের R-এর উপগাছের পাতা vxy; বাকি গাছের পাতা u আর z.
Non-CFL প্রমাণে লাগে lemma-র অস্বীকার। পর্ব ১৭-এর মতো প্রতিটি ∃ হয়ে যায় ∀, প্রতিটি ∀ হয়ে যায় ∃:
| Lemma-তে | অস্বীকারে | খেলায় কে বাছে |
|---|---|---|
| ∃p ≥ 1 | ∀p ≥ 1 | প্রতিপক্ষ |
| ∀s ∈ L, |s| ≥ p | ∃s ∈ L, |s| ≥ p | আপনি (p দেখে) |
| ∃u, v, x, y, z (শর্তসহ) | ∀u, v, x, y, z (শর্তসহ) | প্রতিপক্ষ (সব বিভাজন সামলাতে হবে) |
| ∀i ≥ 0 : uvixyiz ∈ L | ∃i ≥ 0 : uvixyiz ∉ L | আপনি (বিভাজন দেখে) |
৩ · প্রমাণ — CNF parse tree, উচ্চতা আর পুনরাবৃত্ত variable
প্রমাণে পর্ব ২৯-এর দুটি তথ্য লাগে: প্রতিটি CFL-এর একটি Chomsky normal form grammar আছে, আর CNF-এ w-এর কোনো parse tree-র উচ্চতা h হলে |w| ≤ 2h−1 (উপপাদ্য ৩.২ সেখানে)। উল্টো করে পড়লে: লম্বা string-এর গাছ উঁচু হতে বাধ্য। এখানে yield মানে উপগাছের পাতাগুলো বাঁ থেকে ডানে পড়ে পাওয়া string.
প্রমাণ (উপপাদ্য ২.১):
- L context-free, তাই L-এর একটি CNF grammar G = (V, Σ, R, S0) আছে। k = |V| আর p = 2k নিন; k ≥ 1 বলে p ≥ 2. — CNF-এ রূপান্তর (পর্ব ২৯)
- s ∈ L আর |s| ≥ p নিন, আর s-এর যেকোনো একটি parse tree T, যার উচ্চতা h. তাহলে 2k = p ≤ |s| ≤ 2h−1, তাই h ≥ k + 1. — উচ্চতার সীমা
- T-এর মূল থেকে পাতা পর্যন্ত একটি সবচেয়ে লম্বা পথ নিন। এতে h-টি edge আর h + 1টি node; শেষ node একটি terminal পাতা, বাকি h ≥ k + 1টি node variable. — উচ্চতার সংজ্ঞা
- পথের সবচেয়ে নিচের k + 1টি variable দেখুন। variable-এর নাম মাত্র k-টি, তাই এদের মধ্যে কোনো R দুবার আসে। ওপরের ঘটনাকে R1, নিচেরটিকে R2 বলুন। — pigeonhole principle
- R2-এর উপগাছের yield x. R1-এর উপগাছের yield-এ x-এর বাঁয়ের অংশ v আর ডানের অংশ y, তাই yield = vxy. পুরো গাছের yield s = uvxyz. গাছ থেকে পড়া যায়: S0 ⇒∗ uRz, R ⇒∗ vRy, আর R ⇒∗ x. — উপগাছ ও yield
- |vy| ≥ 1: R1-এর নিচে আরেকটি variable আছে, তাই R1-এ নিয়মটি R → BC. R2 B বা C-এর কোনো একটির উপগাছে; অন্যটির yield ফাঁকা নয় (CNF-এ S0 ছাড়া কোনো variable ε দেয় না, আর S0 কোনো ডান দিকে নেই), আর সেই yield v বা y-এর অংশ। — CNF-এর দুই আকার
- |vxy| ≤ p: R1 নিচের k + 1টি variable-এর একটি, তাই পথে R1 থেকে পাতা পর্যন্ত বড়জোর k + 1টি edge. পথটি পুরো গাছে সবচেয়ে লম্বা, তাই R1-এর উপগাছেও এটি সবচেয়ে লম্বা; ফলে সেই উপগাছের উচ্চতা ≤ k + 1, আর তার yield-এর দৈর্ঘ্য ≤ 2k = p. — উচ্চতার সীমা আবার
- R ⇒∗ vRy বারবার খাটালে R ⇒∗ viRyi ⇒∗ vixyi, তাই প্রতিটি i ≥ 0-এ S0 ⇒∗ uvixyiz, অর্থাৎ uvixyiz ∈ L. i = 0-এ R1-এর উপগাছের জায়গায় সরাসরি R2-এর উপগাছ বসে। ∎ — derivation জোড়া লাগানো
দুটি সূক্ষ্ম বিষয় লক্ষ করুন। প্রথমত, “সবচেয়ে নিচের k + 1টি” থেকে পুনরাবৃত্তি খোঁজাই |vxy| ≤ p এনে দেয়; পথের ওপরের দিকের কোনো পুনরাবৃত্তি নিলে vxy প্রায় পুরো s হতে পারত। দ্বিতীয়ত, CNF না হলে |vy| ≥ 1 এমনি আসে না: R → R-এর মতো unit rule থাকলে v = y = ε হতে পারত। CNF ছাড়া প্রমাণ করতে চাইলে “সবচেয়ে কম node-এর parse tree” নিতে হয়, আর p-এর সূত্রও বদলায় (Sipser-এ p = b|V|+1, যেখানে b নিয়মের ডান দিকের সর্বোচ্চ দৈর্ঘ্য)।
নিচের stepper প্রমাণটিকে পর্ব ২৯-এর anbn-এর CNF grammar-এ চালায়: S0 → AX1 ∣ AB ∣ ε, S → AX1 ∣ AB, X1 → SB, A → a, B → b. এখানে k = 5, তাই p = 32. ছবি ছোট রাখতে s = aaabbb নেওয়া হলো, যা p-এর চেয়ে ছোট; তবু গাছটি যথেষ্ট উঁচু, তাই একই পদ্ধতি কাজ করে।
1grammar: k = 5, p = 322aaabbb-এর parse tree3সবচেয়ে লম্বা পথ4নিচ থেকে ওপরে: পুনরাবৃত্তি5u, v, x, y, z কাটা6i = 0 আর i = 2
| গাছ / পথ | |
| সংখ্যা | |
| শর্ত |
- Grammar. Variable পাঁচটি: S0, S, X1, A, B. তাই প্রমাণের p = 25 = 32. প্রতিটি নিয়ম A → BC বা A → a আকারের, অর্থাৎ grammar-টি CNF-এ।
- গাছ। aaabbb-এর parse tree-তে নিয়মগুলো ওপর থেকে: S0 → AX1, X1 → SB, S → AX1, X1 → SB, S → AB, আর প্রতিটি A → a, B → b. পাতা বাঁ থেকে ডানে aaabbb.
- লম্বা পথ। সবচেয়ে লম্বা একটি পথ S0, X1, S, X1, S, A, তারপর পাতা a: ৬টি edge, ৬টি variable. (A-এর বদলে শেষের B নিলেও সমান লম্বা।)
- Pigeonhole. নিচ থেকে ওপরে উঠুন: A, S, X1, তারপর আবার S. প্রথম পুনরাবৃত্তি S: গভীরতা ৪-এর S (R2) আর গভীরতা ২-এর S (R1). দুটিই পথের নিচের k + 1 = 6টি variable-এর মধ্যে।
- কাটা। নিচের S-এর yield ab, তাই x = ab. ওপরের S-এর yield aabb = v · x · y, তাই v = a, y = b. বাকি u = a, z = b. |vy| = 2 ≥ 1, |vxy| = 4 ≤ 32.
- Pump. i = 0: ওপরের S-এর জায়গায় নিচের S-এর উপগাছ, ফল uxz = aabb. i = 2: নিচের S-এর জায়গায় ওপরের S-এর পুরো উপগাছের একটি কপি, ফল uv2xy2z = aaaabbbb. দুটিই anbn-এ, কারণ a আর b একসঙ্গে বদলেছে।
প্রমাণটি গঠনমূলক: grammar আর s দিলে u, v, x, y, z যান্ত্রিকভাবে বের হয়। নিচের ব্লক ঠিক উপরের ধাপ ২–৫ কোডে লেখে: memoization-সহ (@cache) একটি parse tree খোঁজে, সবচেয়ে লম্বা পথ ধরে নামে, নিচের k + 1টি variable-এ প্রথম পুনরাবৃত্তি খোঁজে, তারপর pump করা string-গুলো ভাষায় আছে কি না দেখে। এবার |s| = p, অর্থাৎ lemma-র শর্ত পুরোপুরি মানা হয়েছে। দ্বিতীয় grammar জোড় দৈর্ঘ্যের palindrome wwR-এর CNF রূপ।
from functools import cache
ANBN = {"S0": [("A", "X1"), ("A", "B")], "S": [("A", "X1"), ("A", "B")],
"X1": [("S", "B")], "A": ["a"], "B": ["b"]} # a^n b^n, n >= 1
PAL = {"S0": [("A", "X"), ("B", "Y"), ("A", "A"), ("B", "B")],
"S": [("A", "X"), ("B", "Y"), ("A", "A"), ("B", "B")],
"X": [("S", "A")], "Y": [("S", "B")], "A": ["a"], "B": ["b"]} # w w^R
def pump_point(R, s): # the proof of the lemma, as code
@cache
def tree(v, i, j): # a parse tree of s[i:j] from v
for rhs in R[v]:
if rhs == s[i:j]: return (v, i, j)
if isinstance(rhs, tuple):
for m in range(i + 1, j):
l, r = tree(rhs[0], i, m), tree(rhs[1], m, j)
if l and r: return (v, i, j, l, r)
h = lambda t: 1 if len(t) == 3 else 1 + max(h(t[3]), h(t[4]))
t = tree("S0", 0, len(s)); path = [t]
while len(t) == 5: # walk down a longest root-to-leaf path
t = t[3] if h(t[3]) >= h(t[4]) else t[4]; path.append(t)
k, seen = len(R), {}
for nd in reversed(path[-(k + 1):]): # bottom k+1 variables, going up
if nd[0] in seen: up, low = nd, seen[nd[0]]; break
seen[nd[0]] = nd
print(f"|V|={k} p={2 ** k} |s|={len(s)} height={len(path)} bottom:",
" ".join(nd[0] for nd in path[-(k + 1):]), "->", up[0])
return s[:up[1]], s[up[1]:low[1]], s[low[1]:low[2]], s[low[2]:up[2]], s[up[2]:]
def anbn(t): return t == "a" * (len(t) // 2) + "b" * (len(t) // 2)
def even_pal(t): return t == t[::-1] and len(t) % 2 == 0
w = "abbab" * 6 + "aa" # |w w^R| = 64 = 2^6
for R, s, in_L in [(ANBN, "a" * 16 + "b" * 16, anbn), (PAL, w + w[::-1], even_pal)]:
u, v, x, y, z = pump_point(R, s)
print(f" u=..{u[-3:]} v={v} x={x} y={y} z={z[:3]}.. |vxy|={len(v + x + y)}",
"pumped i=0..5 in L:", all(in_L(u + v * i + x + y * i + z) for i in range(6)))আসল আউটপুট (ব্রাউজারের Python):
|V|=5 p=32 |s|=32 height=32 bottom: S X1 S X1 S A -> S
u=..aaa v=a x=ab y=b z=bbb.. |vxy|=4 pumped i=0..5 in L: True
|V|=6 p=64 |s|=64 height=64 bottom: X S Y S X S A -> S
u=..bab v=a x=aa y=a z=bab.. |vxy|=4 pumped i=0..5 in L: True
প্রথম লাইনে a16b16-এর গাছের উচ্চতা ৩২, যা ন্যূনতম সীমা k + 1 = 6-এর অনেক বেশি: এই grammar-এর গাছ একটি লম্বা “শিকল”, প্রতিটি স্তরে একটি a আর একটি b যোগ হয়। নিচের ৬টি variable S X1 S X1 S A, আর নিচ থেকে প্রথম পুনরাবৃত্তি S. সবচেয়ে গুরুত্বপূর্ণ পর্যবেক্ষণ: u = a14, অর্থাৎ vxy = aabb বসেছে string-এর একেবারে মাঝখানে, শুরুতে নয়। Regular lemma-র |xy| ≤ p-এর সঙ্গে এখানেই পার্থক্য, যা অংশ ৬-এর ভুল প্রমাণে কাজে লাগবে। দ্বিতীয় grammar-এ ছয়টি variable, তাই p = 64, আর s = wwR-এর দৈর্ঘ্যও 64. পুনরাবৃত্তি আবার মাঝখানে: v = a আর y = a দুটি আয়না-প্রতিবিম্ব অবস্থানে, তাই একসঙ্গে বাড়ালেও string palindrome থাকে। দুই ক্ষেত্রেই i = 0 থেকে 5 পর্যন্ত প্রতিটি pump করা string ভাষায় আছে।
৪ · প্রতিপক্ষের খেলা — anbncn context-free নয়
পর্ব ১৭-এর adversary argument এখানে হুবহু খাটে, শুধু প্রতিপক্ষের চাল এখন পাঁচ ভাগের বিভাজন। ছকটি তাই:
- বিরোধের জন্য ধরুন L context-free; lemma একটি অজানা p দেয়। — proof by contradiction
- p দিয়ে লেখা একটি s ∈ L বাছুন, |s| ≥ p.
- যেকোনো বিভাজন s = uvxyz নিন, যেখানে |vy| ≥ 1 আর |vxy| ≤ p. vxy কোন কোন খণ্ড ছুঁতে পারে, তা দিয়ে ক্ষেত্র ভাগ করুন।
- প্রতিটি ক্ষেত্রে একটি i দেখান, যাতে uvixyiz ∉ L.
- এটি lemma-র শর্ত ৩-এর বিরোধী, তাই L context-free নয়। ∎
সবচেয়ে পরিচিত উদাহরণটি পূর্ণভাবে। Stepper-এ p = 4 বসিয়ে একটি নির্দিষ্ট বিভাজন দেখানো হয়েছে, কিন্তু প্রতিটি ধাপের যুক্তি যেকোনো p আর যেকোনো বিভাজনে খাটে।
1ধরি L CFL; প্রতিপক্ষ p দেন2আপনি: s = aᵖbᵖcᵖ3প্রতিপক্ষ: s = uvxyz4∣vxy∣ ≤ p ⇒ a আর c একসঙ্গে নয়5ক্ষেত্র ১: v বা y-তে দুই রকম চিহ্ন6ক্ষেত্র ২: v, y একরকম চিহ্নের7বিরোধ ∎
| string | |
| কে বাছল | |
| যুক্তি |
- অনুমান। বিরোধের জন্য ধরুন L = {anbncn : n ≥ 0} context-free. Lemma একটি pumping length p দেয়, যার মান আপনি জানেন না।
- s বাছাই। s = apbpcp নিন। তিন চিহ্ন সমান সংখ্যক, তাই s ∈ L, আর |s| = 3p ≥ p.
- বিভাজন। প্রতিপক্ষ যেকোনো বৈধ বিভাজন দিতে পারেন, যেমন u = aaa, v = a, x = bb, y = b, z = bcccc. আপনি এটি বাছেননি, তাই পরের ধাপে সব বিভাজন একসঙ্গে সামলাতে হবে।
- সাধারণ ধর্ম। s-এ শেষ a আর প্রথম c-এর মাঝে p-টি b. vxy একটানা আর দৈর্ঘ্যে ≤ p, তাই vxy-তে a আর c একসঙ্গে থাকতে পারে না। ফলে v আর y মিলে বড়জোর দুই রকম চিহ্ন, আর তৃতীয় চিহ্নটি তারা ছোঁয় না।
- ক্ষেত্র ১। v বা y-এর কোনো একটিতে দুই রকম চিহ্ন, যেমন v = ab. i = 2 নিলে uv2xy2z-এ abab দেখা যায়, অর্থাৎ a∗b∗c∗ ক্রমই ভেঙে যায়: ∉ L.
- ক্ষেত্র ২। v আর y প্রতিটি এক রকম চিহ্নের (বা ফাঁকা)। |vy| ≥ 1, তাই অন্তত একটি চিহ্নের সংখ্যা i = 2-এ বাড়ে, কিন্তু ধাপ ৪ অনুযায়ী অন্তত একটি চিহ্ন অছোঁয়া থাকে, যার সংখ্যা p-ই থাকে। উদাহরণের বিভাজনে a5b5c4: ∉ L.
- উপসংহার। প্রতিটি বৈধ বিভাজনে i = 2 string-টিকে L-এর বাইরে পাঠায়, যা lemma-র শর্ত ৩-এর বিরোধী। তাই anbncn context-free নয়। ∎ (i = 0-ও কাজ করে: তখন অছোঁয়া চিহ্নটি অন্যদের চেয়ে বেশি থাকে।)
এই প্রমাণ থেকে আসে প্রথম পরিচিত non-CFL. ফল হিসেবে মডিউল ৬-এর একটি বড় সিদ্ধান্তও আসে: anbncm আর ambncn দুটিই CFL, কিন্তু তাদের ছেদ anbncn, তাই CFL ছেদে বদ্ধ নয়; complement নিয়েও একই কথা। এই closure property-এর পূর্ণ হিসাব পর্ব ৩৭-এ (CFL-এর closure আর decision property).
নিচের ব্লক প্রতিপক্ষের সব চাল একসঙ্গে পরীক্ষা করে। p = 1 থেকে 5-এ s = apbpcp-এর প্রতিটি বৈধ বিভাজন তৈরি করে আর দেখে i = 0 আর i = 2 দুটিতেই string ভাষায় থাকে এমন বিভাজন (প্রতিপক্ষের জয়) আছে কি না। তুলনার জন্য দ্বিতীয় ভাষা anbncm, যা CFL, তাই সেখানে প্রতিপক্ষের জেতার কথা। শেষ লাইন গোনে, v আর y মিলে কোন কোন চিহ্ন ছুঁতে পারে।
import re
from collections import Counter
def splits(s, p): # every u v x y z with |vxy| <= p and |vy| >= 1
for a in range(len(s) + 1): # vxy = s[a:e]
for e in range(a, min(len(s), a + p) + 1):
for b in range(a, e + 1): # v = s[a:b], x = s[b:c]
for c in range(b, e + 1): # y = s[c:e]
if b - a + e - c >= 1: yield a, b, c, e
def pump(s, a, b, c, e, i):
return s[:a] + s[a:b] * i + s[b:c] + s[c:e] * i + s[e:]
def abc(w): # a^n b^n c^n
n = len(w) // 3
return w == "a" * n + "b" * n + "c" * n
def ab_c(w): # a^n b^n c^m, a context-free language
return re.fullmatch(r"a*b*c*", w) and w.count("a") == w.count("b")
for name, in_L in [("a^n b^n c^n", abc), ("a^n b^n c^m", ab_c)]:
print(name)
for p in range(1, 6):
s = "a" * p + "b" * p + "c" * p
alive = [sp for sp in splits(s, p)
if all(in_L(pump(s, *sp, i)) for i in (0, 2))]
total = sum(1 for _ in splits(s, p))
msg = f" p={p} splits={total:4} adversary wins: {len(alive)}"
if alive:
a, b, c, e = alive[0]
msg += f" e.g. v={s[a:b] or 'ε'} y={s[c:e] or 'ε'}"
print(msg)
s, p = "aaaabbbbcccc", 4 # which letters can v and y contain together?
kinds = Counter("".join(sorted(set(s[a:b] + s[c:e]))) for a, b, c, e in splits(s, p))
print("p=4, letters in vy:", dict(sorted(kinds.items())))আসল আউটপুট (ব্রাউজারের Python):
a^n b^n c^n
p=1 splits= 6 adversary wins: 0
p=2 splits= 37 adversary wins: 0
p=3 splits= 121 adversary wins: 0
p=4 splits= 295 adversary wins: 0
p=5 splits= 605 adversary wins: 0
a^n b^n c^m
p=1 splits= 6 adversary wins: 2 e.g. v=ε y=c
p=2 splits= 37 adversary wins: 11 e.g. v=a y=b
p=3 splits= 121 adversary wins: 32 e.g. v=a y=b
p=4 splits= 295 adversary wins: 72 e.g. v=a y=b
p=5 splits= 605 adversary wins: 138 e.g. v=a y=b
p=4, letters in vy: {'a': 65, 'ab': 45, 'b': 75, 'bc': 45, 'c': 65}
বিভাজনের সংখ্যা দ্রুত বাড়ে: p = 5-এ ৬০৫টি, যা হাতে গোনা অসম্ভব; তাই প্রমাণে ক্ষেত্র ভাগ করে সব একসঙ্গে সামলাতে হয়। anbncn-এ একটি বিভাজনও টেকেনি। anbncm-এ প্রতিপক্ষের জয়ী চাল স্বাভাবিক: v = a আর y = b সীমানার দুই পাশে, একসঙ্গে বাড়ালে সমতা অটুট। p = 1-এ |vxy| ≤ 1, তাই দুটি একসঙ্গে নেওয়া যায় না; তখন y = c একাই জেতে, কারণ c-এর সংখ্যা স্বাধীন। শেষ লাইনটি stepper-এর ধাপ ৪-এর কোড-রূপ: ২৯৫টি বিভাজনে vy-এর চিহ্ন-সেট শুধু a, ab, b, bc বা c; “ac” বা “abc” একবারও আসেনি। মনে রাখুন, এটি শুধু p ≤ 5 দেখে; সব p-এর নিশ্চয়তা দেয় stepper-এর যুক্তি।
৫ · পরিচিত প্রমাণ — ww, an² আর i ≤ j ≤ k
প্রতিটি প্রমাণের আসল কাজ s বাছাই আর ক্ষেত্র ভাগ। CFL-এ ভালো s সাধারণত কয়েকটি লম্বা একরকম খণ্ড, প্রতিটি অন্তত p দৈর্ঘ্যের, যাতে |vxy| ≤ p থেকে বোঝা যায় vxy বড়জোর দুটি পাশাপাশি খণ্ড ছোঁয়। নিচের প্রতিটি যুক্তি scratch-এ ছোট p-তে সব বিভাজন কোড দিয়ে যাচাই করা হয়েছে।
s = apbpapbp নিন। i = 0 নিন, ফল t = uxz, |t| = 4p − m, যেখানে m = |vy|, 1 ≤ m ≤ p. m বিজোড় হলে |t| বিজোড়, তাই ∉ ww. m জোড় হলে t-এর অর্ধেকের দৈর্ঘ্য 2p − m/2. |vxy| ≤ p বলে তিনটি ক্ষেত্র:
(ক) vxy প্রথম অর্ধেকে (apbp): t-এর শেষ p চিহ্ন b, আর প্রথম অর্ধেকের শেষ চিহ্ন দ্বিতীয় a-খণ্ডের একটি a. দুই অর্ধেকের শেষ চিহ্ন আলাদা।
(খ) vxy দ্বিতীয় অর্ধেকে: প্রথম অর্ধেক শুরু হয় a দিয়ে, দ্বিতীয় অর্ধেক শুরু হয় প্রথম b-খণ্ডের বাকি b দিয়ে।
(গ) vxy মাঝের bpap-এর ভেতরে: t = apbjakbp, j বা k < p. t = ww হলে w ap দিয়ে শুরু আর bp দিয়ে শেষ, তাই |w| ≥ 2p; কিন্তু |w| = 2p − m/2 < 2p.
তিন ক্ষেত্রেই t ∉ ww. ∎
s = ap². এখানে একটিমাত্র চিহ্ন, তাই vy = ak, আর 1 ≤ k ≤ |vxy| ≤ p. i = 2-এ দৈর্ঘ্য p² + k, আর p² < p² + k ≤ p² + p < (p + 1)², তাই পূর্ণবর্গ নয়। ∎ প্রমাণটি পর্ব ১৭-এর প্রায় হুবহু। কারণটি গভীর: একক-চিহ্নের alphabet-এ প্রতিটি CFL আসলে regular (অংশ ৮-এর Parikh-এর theorem), তাই সেখানে regular-এর সব non-regular প্রমাণই non-CFL প্রমাণ।
s = apbpcp. v বা y-তে দুই রকম চিহ্ন থাকলে i = 2-এ ক্রম ভাঙে। নইলে, |vxy| ≤ p বলে vy-তে a আর c একসঙ্গে নেই। দুই ক্ষেত্র:
(ক) vy-তে অন্তত একটি a (তাই কোনো c নেই): i = 2 নিন। a বেড়ে p + α, b হয় p + β, c থাকে p. β = 0 হলে a > b; β ≥ 1 হলে b > c. দুইভাবেই i ≤ j ≤ k ভাঙে।
(খ) vy-তে কোনো a নেই: i = 0 নিন। vy-তে b থাকলে b কমে p-এর নিচে, অথচ a = p, তাই a > b; vy-তে শুধু c থাকলে c কমে, অথচ b = p, তাই b > c.
দুই ক্ষেত্রে দুই আলাদা i লাগে; শুধু i = 2 দিয়ে চেষ্টা করলে (খ) ক্ষেত্রে আটকে যাবেন। ∎
Regular-এ যে s কাজ করত, এখানে তা হারায়। পর্ব ১৭-এ ww-এর জন্য s = apbapb যথেষ্ট ছিল, কারণ y থাকত শুরুর a-খণ্ডে। CFL lemma-য় প্রতিপক্ষ vxy মাঝখানে বসাতে পারেন: u = ap−1, v = a, x = b, y = a, z = ap−1b. তখন uvixyiz = ap−1+ibap−1+ib, যা প্রতিটি i-তে ww-এর সদস্য। নিচের JavaScript ব্লক p = 3-এ ঠিক এই বিভাজন খুঁজে পায়। শিক্ষা: CFL-এ s-এর প্রতিটি “সীমানা” এত দূরে দূরে রাখুন যে vxy দুটির বেশি খণ্ড ছুঁতে না পারে, আর মাঝের সীমানাতেও pump করলে কিছু ভাঙে।
৬ · সাধারণ ভুল — |vxy| ≤ p ভুল পড়া, বিভাজন বেছে নেওয়া, একটি ক্ষেত্র বাদ
CFL pumping প্রমাণে regular-এর সব ভুল তো আছেই, সঙ্গে একটি নতুন ভুল যোগ হয়, যা সবচেয়ে বিপজ্জনক: |vxy| ≤ p-কে “vxy শুরুর p চিহ্নে” পড়া। নিচের stepper এমন একটি ভুল প্রমাণ দেখায়, যা একটি CFL-কেও non-CFL বলে দেয়।
1দাবি: aⁿbⁿ non-CFL2s = aᵖbᵖ3“vxy প্রথম p চিহ্নে” ✗4i = 2 ⇒ a বেশি ⇒ ∉ L5কিন্তু S → aSb ∣ ε আছে6প্রতিপক্ষের আসল চাল
| যুক্তি | |
| কে বাছল | |
| ফল |
- দাবি। কেউ লিখলেন: “anbn context-free নয়। প্রমাণ: ধরি এটি CFL, আর p তার pumping length.” শুরুটি নিখুঁত।
- s বাছাই। “s = apbp নিই।” s ∈ L আর |s| = 2p ≥ p, তাই এই চালও বৈধ।
- ভুলের জায়গা। “|vxy| ≤ p, তাই vxy s-এর প্রথম p চিহ্নে, যেখানে সব a; অর্থাৎ v আর y শুধু a.” এটি regular lemma-র |xy| ≤ p-এর যুক্তি, যা এখানে খাটে না। |vxy| ≤ p শুধু দৈর্ঘ্য বেঁধে দেয়; vxy s-এর যেকোনো জায়গায় হতে পারে।
- “উপসংহার”। “i = 2 নিলে a বাড়ে কিন্তু b বাড়ে না, তাই ∉ L; বিরোধ।” হিসাবটি শুধু সেইসব বিভাজনে ঠিক, যেখানে vxy a-খণ্ডে। প্রতিপক্ষ সেগুলো দেবেন না।
- বাস্তব। Grammar S → aSb ∣ ε ঠিক anbn তৈরি করে (পর্ব ২৫), তাই এটি CFL. ভুল প্রমাণের সবচেয়ে বড় লক্ষণ: একটি মিথ্যা সিদ্ধান্ত।
- প্রতিপক্ষের চাল। u = ap−1, v = a, x = ε, y = b, z = bp−1. |vy| = 2 আর |vxy| = 2 ≤ p (p ≥ 2 হলে)। uvixyiz = ap−1+ibp−1+i, প্রতিটি i-তে সমান: ∈ L. অংশ ৩-এর Python ব্লকেও vxy ঠিক এভাবে মাঝখানে বসেছিল।
অন্য ভুলগুলোর তালিকা, প্রতিটির পাশে ঠিক কী:
| ভুল | কেন ভুল, আর ঠিক কী |
|---|---|
| |vxy| ≤ p মানে “শুরুর p চিহ্ন” | এটি দৈর্ঘ্যের সীমা; vxy যেকোনো জায়গায়, তাই প্রতিটি সীমানার কাছে vxy-এর অবস্থান আলাদা ক্ষেত্র |
| |vxy| ≤ p একেবারে ব্যবহার না করা | তখন v আর y দূরের দুই খণ্ডে থাকতে পারে; anbmcndm-এ v = a, y = c একসঙ্গে বাড়লে string ভাষাতেই থাকে, প্রমাণ আটকে যায় |
| বিভাজন নিজে বেছে নেওয়া (“ধরি v = a, y = b”) | বিভাজন প্রতিপক্ষের; সব বৈধ বিভাজন ক্ষেত্র ভাগ করে সামলাতে হয় |
| p-এর মান বসিয়ে দেওয়া (“ধরি p = 3”) | p প্রতিপক্ষের; যুক্তি সব p-এর জন্য লিখতে হয় |
| “v আর y-তে একরকম চিহ্ন” ধরে নেওয়া | v = ab-ও সম্ভব; সেই ক্ষেত্রে আলাদা যুক্তি লাগে (সাধারণত i = 2-এ ক্রম ভাঙে) |
| v বা y-এর একটি ফাঁকা হতে পারে, তা ভুলে যাওয়া | |vy| ≥ 1 মানে অন্তত একটি ফাঁকা নয়; v = ε, y = c বৈধ বিভাজন |
| সব ক্ষেত্রে একই i (শুধু i = 2) | i ≤ j ≤ k-এর মতো ভাষায় কিছু ক্ষেত্রে i = 0 লাগে |
| “শর্ত পূরণ করে, তাই CFL” | Lemma প্রয়োজনীয় শর্ত মাত্র; অংশ ৭-এর Ld শর্ত পূরণ করে, তবু CFL নয় |
নিচের JavaScript ব্লকটি খেলাটি সরাসরি খেলায়। প্রতিটি সারিতে একটি ভাষা, আপনার s (p দেখে) আর আপনার i; প্রোগ্রামটি প্রতিপক্ষ, যে p = 1 থেকে 5-এ সব বৈধ বিভাজন খুঁজে দেখে কোনোটিতে আপনার i দিয়ে string ভাষায় থেকে যায় কি না। শেষ সারিতে |vxy| ≤ p শর্তটি ইচ্ছা করে বাদ দেওয়া হয়েছে। সারি বদলে নিজের কৌশল পরীক্ষা করুন।
// The CFL pumping game. You give s (for each p) and i; the program is the
// adversary: it tries every split u v x y z with |vy| >= 1 (and |vxy| <= p).
const cnt = (w, c) => [...w].filter(ch => ch === c).length, R = (c, n) => c.repeat(n);
const anbn = w => /^a*b*$/.test(w) && cnt(w, "a") === cnt(w, "b");
const abc = w => /^a*b*c*$/.test(w) && cnt(w, "a") === cnt(w, "b") && cnt(w, "b") === cnt(w, "c");
const ww = w => w.length % 2 === 0 && w.slice(0, w.length / 2) === w.slice(w.length / 2);
const abcd = w => /^a*b*c*d*$/.test(w) && cnt(w, "a") === cnt(w, "c") && cnt(w, "b") === cnt(w, "d");
const sABCD = p => R("a", p) + R("b", p) + R("c", p) + R("d", p);
const games = [ // [name, language, your s, your i, use |vxy| <= p?]
["a^n b^n c^n", abc, p => R("a", p) + R("b", p) + R("c", p), 2, true],
["a^n b^n (a CFL)", anbn, p => R("a", p) + R("b", p), 2, true],
["ww, s = a^p b a^p b", ww, p => R("a", p) + "b" + R("a", p) + "b", 0, true],
["ww, s = a^p b^p a^p b^p", ww, p => R(R("a", p) + R("b", p), 2), 0, true],
["a^n b^m c^n d^m", abcd, sABCD, 0, true],
["same, |vxy| <= p dropped", abcd, sABCD, 0, false],
];
for (const [name, inL, pickS, i, bound] of games) {
let lost = null;
for (let p = 1; p <= 5 && !lost; p++) {
const s = pickS(p), n = s.length;
for (let a = 0; a <= n && !lost; a++)
for (let e = a; e <= (bound ? Math.min(n, a + p) : n) && !lost; e++)
for (let b = a; b <= e && !lost; b++)
for (let c = b; c <= e && !lost; c++) {
if (b - a + e - c < 1) continue; // |vy| >= 1
const v = s.slice(a, b), y = s.slice(c, e);
const t = s.slice(0, a) + v.repeat(i) + s.slice(b, c) + y.repeat(i) + s.slice(e);
if (inL(t)) lost = `p=${p}: v=${v || "ε"}, y=${y || "ε"}`;
}
}
console.log(name.padEnd(25), lost ? "adversary wins, " + lost : "you win for p = 1..5");
}আসল আউটপুট (ব্রাউজারের JavaScript):
a^n b^n c^n you win for p = 1..5
a^n b^n (a CFL) adversary wins, p=2: v=a, y=b
ww, s = a^p b a^p b adversary wins, p=3: v=a, y=a
ww, s = a^p b^p a^p b^p you win for p = 1..5
a^n b^m c^n d^m you win for p = 1..5
same, |vxy| <= p dropped adversary wins, p=1: v=a, y=c
প্রথম সারি stepper-এর প্রমাণ মেলায়: i = 2 প্রতিটি বিভাজন হারায়। দ্বিতীয় সারি ভুল প্রমাণের কোড-রূপ: p = 2 থেকেই প্রতিপক্ষ সীমানায় v = a, y = b বসিয়ে জেতেন (p = 1-এ |vxy| ≤ 1 বলে দুটি একসঙ্গে নেওয়া যায় না)। তৃতীয় সারি অংশ ৫-এর সতর্কবার্তা: p = 3-এ vxy = aba মাঝের b ঘিরে বসে, তাই আগে নয়। চতুর্থ সারিতে উদাহরণ ৫.১-এর s আর i = 0 সব বিভাজন হারায়। পঞ্চম সারি অনুশীলন ২-এর ভাষা: |vxy| ≤ p থাকলে i = 0 যথেষ্ট। ষষ্ঠ সারিতে একই ভাষা, একই s, একই i, শুধু |vxy| ≤ p বাদ: এবার প্রতিপক্ষ v = a আর y = c দূরের দুই খণ্ডে বসিয়ে জেতেন। শর্তটি ছাড়া lemma সত্যই থাকে, কিন্তু এই প্রমাণের কাজে লাগে না। আর আবারও: “p = 1..5-এ জয়” প্রমাণ নয়, প্রমাণ হলো সব p-এর জন্য লেখা যুক্তি।
৭ · Ogden-এর lemma — চিহ্নিত অবস্থান দিয়ে বাড়তি জোর
পর্ব ১৭-এর মতোই CFL lemma শুধু একটি প্রয়োজনীয় শর্ত। নিচের ভাষাটি এর মানক পাল্টা-উদাহরণ:
প্রতিপক্ষের কৌশল: p = 1, আর যেকোনো s-এ v = s-এর প্রথম চিহ্ন, u = x = y = ε. s a দিয়ে শুরু হলে pump শুধু a-এর সংখ্যা বদলায়; শূন্যে নামলে string a-হীন শাখায় পড়ে, নইলে j = k = l অটুট। s b, c বা d দিয়ে শুরু হলে তাতে কোনো a নেই, আর pump করেও আসে না। তাই Ld সাধারণ lemma-র শর্ত পুরো পূরণ করে, তবু এটি CFL নয়। সমস্যা হলো, প্রতিপক্ষ সবসময় “নিরীহ” a-খণ্ডে pump করেন, আর আপনার হাতে তাঁকে আসল অংশে টেনে আনার উপায় নেই। Ogden-এর lemma সেই উপায় দেয়।
L context-free হলে একটি p ≥ 1 আছে, যাতে L-এর প্রতিটি s-এর জন্য, আর s-এর অন্তত p-টি অবস্থান যেভাবেই “চিহ্নিত” করা হোক, s = uvxyz লেখা যায়, এমনভাবে যে:
১. vy-তে অন্তত একটি চিহ্নিত অবস্থান আছে;
২. vxy-তে সর্বোচ্চ p-টি চিহ্নিত অবস্থান আছে;
৩. প্রতিটি i ≥ 0-এ uvixyiz ∈ L.
s-এর প্রতিটি অবস্থান চিহ্নিত করলে এটি হুবহু সাধারণ lemma. জোরটা আসে এখান থেকে যে চিহ্ন আপনি দেন, খেলায় s বাছার সঙ্গেই: প্রতিপক্ষকে তখন এমন বিভাজন দিতে হয়, যার pump করা অংশ আপনার চিহ্নিত এলাকা ছোঁয়। প্রমাণের রূপরেখা: অংশ ৩-এর মতো একটি CNF parse tree নিন, কিন্তু উচ্চতার বদলে “শাখা-বিন্দু” গুনুন: যে node-এর দুই সন্তানের নিচেই চিহ্নিত পাতা আছে। মূল থেকে প্রতিবার বেশি চিহ্নিত পাতার দিকে নামলে, চিহ্নিত পাতা ≥ 2k+1 হলে পথে অন্তত k + 1টি শাখা-বিন্দু পাওয়া যায়, আর pigeonhole এগুলোর মধ্যে একটি পুনরাবৃত্ত variable দেয়। p-এর মান আর পূর্ণ প্রমাণ এখানে বাদ রাখা হলো; দেখুন Ogden-এর মূল প্রবন্ধ (১৯৬৮) বা উচ্চতর formal language-এর পাঠ্যবই।
ধরুন Ld CFL, আর p Ogden-এর সংখ্যা। s = abpcpdp নিন আর শুধু b-গুলো চিহ্নিত করুন (ঠিক p-টি)। যেকোনো বৈধ বিভাজনে vy-তে অন্তত একটি b. i = 2 নিন:
(ক) v বা y-তে দুই রকম চিহ্ন থাকলে a∗b∗c∗d∗ ক্রম ভাঙে: ∉ Ld.
(খ) নইলে v আর y প্রতিটি একটি খণ্ডের ভেতরে, আর তাদের একটি b-খণ্ডে; তাই v আর y মিলে বড়জোর দুটি খণ্ড ছোঁয়, যার একটি b. b-এর সংখ্যা বাড়ে, কিন্তু c আর d দুটিই বাড়তে পারে না। a-এর সংখ্যা অন্তত ১ থাকে (i = 2 কিছু মোছে না), তাই j = k = l লাগত, যা ভেঙেছে: ∉ Ld. ∎
নিচের ব্লক দুই খেলা পাশাপাশি চালায়: একই s = abpcpdp-এ সব অবস্থান চিহ্নিত (সাধারণ lemma) আর শুধু b চিহ্নিত (Ogden). প্রতিটি বৈধ বিভাজনে i = 0 থেকে 3 সবগুলোতে string ভাষায় থাকলে সেটি প্রতিপক্ষের জয়।
import re
def in_L(w): # a^i b^j c^k d^l with i = 0 or j = k = l
m = re.fullmatch(r"(a*)(b*)(c*)(d*)", w)
return bool(m) and (not m[1] or len(m[2]) == len(m[3]) == len(m[4]))
def splits(s, p, mark): # vy has >= 1 marked, vxy has <= p marked
n = len(s)
for a in range(n + 1):
for e in range(a, n + 1):
if sum(mark[a:e]) > p: break
for b in range(a, e + 1):
for c in range(b, e + 1):
if sum(mark[a:b]) + sum(mark[c:e]) >= 1:
yield a, b, c, e
def pump(s, a, b, c, e, i):
return s[:a] + s[a:b] * i + s[b:c] + s[c:e] * i + s[e:]
for p in range(1, 6):
s = "a" + "b" * p + "c" * p + "d" * p
every = [1] * len(s) # ordinary lemma: all marked
only_b = [int(ch == "b") for ch in s] # Ogden: mark just the b's
res = []
for mark in (every, only_b):
sp = list(splits(s, p, mark))
win = [t for t in sp if all(in_L(pump(s, *t, i)) for i in range(4))]
by2 = all(not in_L(pump(s, *t, 2)) for t in sp)
res.append(f"{len(sp):4} splits, adversary wins {len(win):3}"
+ (" (v={} y={})".format(s[win[0][0]:win[0][1]] or "ε",
s[win[0][2]:win[0][3]] or "ε") if win else "")
+ f", i=2 beats all: {by2}")
print(f"p={p} s={s}\n all marked: {res[0]}\n b's marked: {res[1]}")আসল আউটপুট (ব্রাউজারের Python):
p=1 s=abcd
all marked: 8 splits, adversary wins 2 (v=ε y=a), i=2 beats all: False
b's marked: 32 splits, adversary wins 0, i=2 beats all: True
p=2 s=abbccdd
all marked: 44 splits, adversary wins 3 (v=ε y=a), i=2 beats all: False
b's marked: 191 splits, adversary wins 0, i=2 beats all: True
p=3 s=abbbcccddd
all marked: 137 splits, adversary wins 4 (v=ε y=a), i=2 beats all: False
b's marked: 637 splits, adversary wins 0, i=2 beats all: True
p=4 s=abbbbccccdddd
all marked: 325 splits, adversary wins 5 (v=ε y=a), i=2 beats all: False
b's marked: 1595 splits, adversary wins 0, i=2 beats all: True
p=5 s=abbbbbcccccddddd
all marked: 655 splits, adversary wins 6 (v=ε y=a), i=2 beats all: False
b's marked: 3355 splits, adversary wins 0, i=2 beats all: True
সব অবস্থান চিহ্নিত থাকলে প্রতিপক্ষের p + 1টি জয়ী বিভাজন, প্রতিটিতে pump করা অংশটি একমাত্র a (প্রথমটি দেখানো: v = ε, y = a). a মুছে গেলে string a-হীন শাখায় ঢোকে, আর a বাড়লে কিছুই ভাঙে না। শুধু b চিহ্নিত করলে বৈধ বিভাজন অনেক বেশি (চিহ্নহীন a, c, d-গুলো vxy-এর সীমায় গোনা হয় না, তাই vxy অনেক লম্বা হতে পারে), কিন্তু প্রতিটিকে vy-তে একটি b ছুঁতে হয়, আর i = 2 প্রতিটি হারায়: উদাহরণ ৭.২-এর যুক্তি কোডে মিলল। চিহ্ন দিয়ে আপনি প্রতিপক্ষকে “নিরীহ” a থেকে সরিয়ে আসল গণনার এলাকায় টেনে এনেছেন।
Ogden ১৯৬৮ সালে এই lemma দিয়েছিলেন inherent ambiguity প্রমাণের জন্য: পর্ব ২৭-এর {aibjck : i = j অথবা j = k} যে একটি inherently ambiguous language, তার প্রচলিত প্রমাণে এর রূপ ব্যবহার হয়। মনে রাখুন, Ogden-এর lemma-ও শুধু প্রয়োজনীয় শর্ত; CFL-কে পুরোপুরি চিহ্নিত করার মতো Myhill–Nerode-ধরনের কোনো সরল উপপাদ্য context-free স্তরে নেই।
আরও গভীরে: Ogden-এর মূল রূপ আরও শক্ত: সেখানে বাড়তি শর্ত আছে যে হয় u আর v দুটিতেই, নয়তো y আর z দুটিতেই চিহ্নিত অবস্থান থাকবে; Bader আর Moura ১৯৮২ সালে একে আরও সাধারণ করেন, যেখানে কিছু অবস্থান “নিষিদ্ধ”-ও চিহ্নিত করা যায়। অন্য দিকে Parikh-এর theorem (Rohit Parikh; ১৯৬১ সালের একটি প্রতিবেদন, ১৯৬৬ সালে JACM-এ প্রকাশিত বলে পরিচিত) বলে, একটি CFL-এর প্রতিটি string-এ কোন চিহ্ন কতবার আছে, সেই গণনা-ভেক্টরগুলোর সেট semilinear, অর্থাৎ কোনো regular language-এর গণনা-সেটের সমান। ফল: একক-চিহ্নের alphabet-এ প্রতিটি CFL regular, তাই তার দৈর্ঘ্য-সেট ultimately periodic, আর an², a2n বা prime দৈর্ঘ্য কখনো CFL নয়। অর্থাৎ stack-এর বাড়তি জোর আসে শুধু চিহ্নগুলোর ক্রম থেকে, গণনা থেকে নয়।
৮ · কোন হাতিয়ার কখন — pumping, Ogden, closure না Parikh
Non-CFL প্রমাণের চারটি প্রধান পথ, প্রতিটির নিজস্ব জোর:
| হাতিয়ার | কী দেখাতে হয় | কখন সুবিধাজনক | সীমা |
|---|---|---|---|
| CFL pumping (অংশ ২–৫) | একটি s, আর প্রতিটি বিভাজনে একটি i | তিন বা বেশি সংখ্যা মেলানো (anbncn), দূরের মিল (ww, anbmcndm) | শুধু প্রয়োজনীয় শর্ত; Ld-এ অচল |
| Ogden-এর lemma (অংশ ৭) | s, চিহ্নিত অবস্থান, আর প্রতিটি বিভাজনে i | ভাষায় একটি “নিরীহ” শাখা আছে, যেখানে প্রতিপক্ষ লুকাতে পারেন | এটিও শুধু প্রয়োজনীয় শর্ত |
| Closure (পর্ব ৩৭) | L ∩ (regular), homomorphism ইত্যাদিতে একটি জানা non-CFL পাওয়া | যেমন {w : a, b, c সমান সংখ্যক} ∩ a∗b∗c∗ = anbncn | আগে থেকে জানা একটি non-CFL লাগে; CFL ∩ CFL চলে না |
| Parikh-এর theorem | গণনা-সেট semilinear নয় | একক-চিহ্নের ভাষা: an², a2n, prime দৈর্ঘ্য | শুধু গণনা দেখে; anbncn-এর মতো ক্রমের সমস্যা ধরে না |
একটি ব্যবহারিক পরামর্শ: প্রমাণ শুরুর আগে ভাবুন, একটি stack দিয়ে ভাষাটি চেনা যায় কি না। “একটি সংখ্যা push করে পরে pop করে মেলানো” বা “প্রথম অর্ধেক উল্টো ক্রমে মেলানো” (wwR) চলে; “একই ক্রমে মেলানো” (ww) বা “দুটি আলাদা গণনা একে অপরকে ছেদ করে মেলানো” (anbmcndm) চলে না, কারণ stack-এর ওপরে যা আছে শুধু সেটিই আগে পাওয়া যায়। সন্দেহ থাকলে আগে একটি CFG লেখার চেষ্টা করুন; {aibjck : i = j অথবা j = k} শুনতে কঠিন, কিন্তু দুটি সরল grammar-এর union (অনুশীলন ১)।
CFL-এর pumping lemma Yehoshua Bar-Hillel, Micha Perles আর Eli Shamir-এর ১৯৬১ সালের প্রবন্ধ “On formal properties of simple phrase structure grammars”-এর সঙ্গে যুক্ত; তাই একে অনেক বইয়ে Bar-Hillel lemma-ও বলা হয়। একই প্রবন্ধে CFL-এর কয়েকটি closure আর decision ফলও আছে বলে উল্লেখ পাওয়া যায়। William Ogden-এর “A helpful result for proving inherent ambiguity” প্রকাশিত হয় ১৯৬৮ সালে Mathematical Systems Theory জার্নালে। Rohit Parikh-এর theorem প্রথমে ১৯৬১ সালের একটি MIT প্রতিবেদনে আসে, আর ১৯৬৬ সালে “On context-free languages” নামে Journal of the ACM-এ প্রকাশিত হয় বলে পরিচিত। সাল নিয়ে সূত্রভেদে সামান্য পার্থক্য দেখা যায়।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- CFL-এর pumping lemma বলুন, আর regular রূপের সঙ্গে পার্থক্য দেখান। uvxyz, |vy| ≥ 1, |vxy| ≤ p; দুটি টুকরো একসঙ্গে pump হয়, আর vxy যেকোনো জায়গায়।
- Lemma-টি প্রমাণ করুন। CNF, p = 2|V|, উচ্চতা ≥ |V| + 1, লম্বা পথের নিচের |V| + 1টি variable-এ pigeonhole.
- anbncn (বা ww) CFL নয় প্রমাণ করুন। s = apbpcp; vxy a আর c একসঙ্গে ছোঁয় না; i = 2. ww-এ s = apbpapbp, i = 0.
- CFL কি ছেদ আর complement-এ বদ্ধ? না: anbncm ∩ ambncn = anbncn.
- এই “প্রমাণে” ভুল কোথায়? সাধারণত vxy-কে শুরুর p চিহ্নে ধরা, বিভাজন নিজে বাছা, বা v = ab-এর মতো ক্ষেত্র বাদ দেওয়া।
৯ · AI-এর যুগে CFL pumping lemma
AI assistant-কে “X context-free নয়, প্রমাণ করো” বললে উত্তর প্রায়ই দেখতে নিখুঁত হয়। কিন্তু CFL প্রমাণে ক্ষেত্র অনেক বেশি, আর AI-এর ভুলও তাই বেশি জায়গায় লুকাতে পারে।
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
| regular lemma-র যুক্তি টেনে আনা: “|vxy| ≤ p, তাই vxy শুরুতে” | প্রমাণে vxy-এর অবস্থান নিয়ে প্রতিটি দাবির পাশে লিখুন কোন শর্ত থেকে এল |
| শুধু “v আর y দুটিই a-খণ্ডে” বা “দুটিই b-খণ্ডে” ধরা, সীমানা-জোড়া ক্ষেত্র আর v = ab বাদ | adversary_abc.py-এর মতো কোডে ছোট p-তে সব বিভাজন পরীক্ষা করুন |
| একটি CFL-কে non-CFL “প্রমাণ” করা (যেমন {aibjck : i = j অথবা j = k}) | আগে একটি CFG লেখার চেষ্টা করুন, আর ছোট দৈর্ঘ্যে grammar আর সংজ্ঞা brute force-এ মেলান |
| Lemma-র শর্ত ভুল লেখা: |v| ≥ 1 আর |y| ≥ 1 দুটিই, বা |vxy| ≥ p | Sipser বা Hopcroft–Motwani–Ullman-এর বক্তব্যের সঙ্গে শব্দে শব্দে মেলান |
| “শর্ত পূরণ করে, তাই CFL” বা Ogden-কে পূর্ণ চিহ্নিতকরণ বলা | Ld-এর মতো পাল্টা-উদাহরণ মনে রাখুন |
| বানানো রেফারেন্স বা ভুল সাল (যেমন lemma-কে Chomsky-র নামে চালানো) | পাঠ্যবই বা মূল প্রবন্ধের তথ্য নিজে খুঁজে দেখুন |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: প্রতিটি ক্ষেত্র আলাদা করে লিখতে বলা, প্রতিটি বাছাই কার তা চিহ্নিত করতে বলা, আর একটি যাচাই-কোড চাওয়া, যা আপনি নিজে চালাবেন।
(নিজে যাচাই করুন: ভালো উত্তরে s = apbpcp, আর দুই ক্ষেত্রে দুই i থাকবে: vy-তে a থাকলে i = 2, না থাকলে i = 0. উদাহরণ ৫.৩ আর অনুশীলন ৩ দেখুন।)
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১CFL-এ দুটি টুকরো একসঙ্গে pump হয়, regular-এ একটি। এই পার্থক্য stack-যুক্ত যন্ত্রের ক্ষমতা আর সীমা সম্পর্কে কী বলে?
Regular lemma-য় একটি DFA-র পথে চক্র থাকে, আর চক্রটি একটিমাত্র টুকরো y. যন্ত্র চক্রটি কতবার ঘুরল তা মনে রাখতে পারে না, তাই y যতবারই আসুক, শেষ অবস্থা একই। CFL lemma-য় parse tree-র ভেতরে একটি variable নিজের ভেতরে আবার আসে। PDA-র ভাষায় এটি এমন: যন্ত্র কিছু চিহ্ন পড়তে পড়তে stack-এ কিছু জমায় (v), তারপর ভেতরের অংশ x পড়ে, তারপর জমানো জিনিসগুলো তুলে মেলায় (y). জমানো আর তোলা জোড়ায় জোড়ায় ঘটে, তাই v আর y একসঙ্গে বাড়ে-কমে। এটিই stack-এর ক্ষমতা: বাঁ দিকের কিছু অংশের সঙ্গে ডান দিকের কিছু অংশ মেলানো, ঠিক বন্ধনী মেলানোর মতো।
সীমাটিও এখান থেকে বোঝা যায়। একটি pump-জোড়া মাত্র দুটি টুকরো, আর |vxy| ≤ p বলে টুকরো দুটি কাছাকাছি। তাই stack একসঙ্গে দুটি জায়গার মিল রাখতে পারে, তিনটির নয়; আর যে মিলগুলো একে অপরকে “ছেদ” করে (a-এর সঙ্গে c, আবার b-এর সঙ্গে d), সেগুলো stack-এর last-in-first-out নিয়মে খাটে না। বন্ধনী nested হয়: ( [ ] ), কিন্তু ( [ ) ] হয় না। anbmcndm ঠিক এই দ্বিতীয় ধরনের, আর ww-ও তাই: প্রথম অর্ধেকের প্রথম চিহ্ন মেলাতে হয় দ্বিতীয় অর্ধেকের প্রথম চিহ্নের সঙ্গে, অথচ stack-এর ওপরে থাকে শেষে push করা চিহ্ন। wwR-এ মিল nested, তাই সেটি CFL.
এই অন্তর্দৃষ্টি বাস্তবেও কাজে লাগে। প্রোগ্রামিং ভাষার বন্ধনী, block আর function call nested, তাই CFG দিয়ে syntax লেখা যায় (পর্ব ৩৮–৪২-এ parsing). কিন্তু “প্রতিটি variable ব্যবহারের আগে declare করা হয়েছে” বা “function call-এ argument-সংখ্যা definition-এর সঙ্গে মেলে” ধরনের শর্ত আসলে ww-জাতীয় দূরের মিল; এগুলো সাধারণত CFG-এর বাইরে, আর compiler এগুলো parsing-এর পরে symbol table দিয়ে আলাদা ধাপে যাচাই করে। পরে একটি Programming Languages & Compilers কোর্সে এই semantic analysis-এর বিস্তারিত আসবে।
মূল উপলব্ধি: দুই টুকরোর pump মানে stack-এর push-pop জোড়া। Stack nested মিল রাখতে পারে, কিন্তু তিনটি একসঙ্গে বা ছেদ করা মিল নয়; non-CFL প্রমাণ ঠিক এই ফাঁক কাজে লাগায়।
প্র ০২CNF ছাড়া কি lemma প্রমাণ করা যায়? CNF কেন প্রমাণকে এত পরিষ্কার করে, আর p-এর মান কতটা গুরুত্বপূর্ণ?
যায়, তবে দুটি জায়গায় বাড়তি সতর্কতা লাগে। প্রথমত, উচ্চতার সীমা। সাধারণ CFG-এ একটি নিয়মের ডান দিকে সর্বোচ্চ b-টি চিহ্ন থাকলে প্রতিটি node-এর সর্বোচ্চ b-টি সন্তান, তাই উচ্চতা h-এর গাছে পাতা সর্বোচ্চ bh. Sipser এভাবেই প্রমাণ করেন, p = b|V|+1 নিয়ে, যাতে |s| ≥ p হলে উচ্চতা অন্তত |V| + 1 হয়। দ্বিতীয়ত, |vy| ≥ 1. সাধারণ grammar-এ unit rule (A → B) বা ε-rule থাকতে পারে, তখন একটি variable নিজের ঠিক নিচে আবার আসতে পারে এমনভাবে যে v = y = ε. সমাধান: s-এর এমন parse tree নেওয়া, যাতে node সবচেয়ে কম। v = y = ε হলে ওপরের R-এর উপগাছ সরিয়ে নিচেরটি বসালে একই s-এর একটি ছোট গাছ পাওয়া যেত, যা ন্যূনতমতার বিরোধী।
CNF এই দুই সমস্যা একসঙ্গে মিটিয়ে দেয়। প্রতিটি ভেতরের node-এর ঠিক দুটি সন্তান (পাতার ঠিক ওপরের node ছাড়া), তাই উচ্চতার সীমা |w| ≤ 2h−1 পরিষ্কার, যা পর্ব ২৯-এ induction-এ প্রমাণ হয়েছে। আর কোনো variable ε দেয় না, তাই A → BC-এর যে সন্তানের দিকে পুনরাবৃত্তি নেই, তার yield অবশ্যই ফাঁকা নয়, ফলে |vy| ≥ 1 বিনা খরচে আসে। এই কারণেই HMU আর অনেক পাঠ্যক্রম CNF-ভিত্তিক প্রমাণ পছন্দ করে।
p-এর মান নিয়ে একটি সাধারণ ভুল ধারণা আছে। প্রমাণ শুধু দেখায় যে কোনো একটি p আছে; non-CFL প্রমাণে p-এর আসল মান কখনো লাগে না, কারণ যুক্তি সব p-এর জন্য লেখা হয়। অংশ ৩-এর anbn grammar-এ প্রমাণের p = 32, অথচ আসলে p = 2-ই যথেষ্ট (v = a, y = b সবসময় পাওয়া যায়)। আর CNF-এ রূপান্তরে variable বেড়ে যায়, তাই প্রমাণের p প্রায়ই অনেক বড়। প্রমাণের p একটি ঊর্ধ্বসীমা, ন্যূনতম মান নয়; ন্যূনতম pumping length কত, সেটি আলাদা ও কঠিন প্রশ্ন।
মূল উপলব্ধি: CNF প্রমাণকে পরিষ্কার করে কারণ binary গাছে উচ্চতা আর দৈর্ঘ্যের সম্পর্ক সরল, আর ε না থাকায় pump-এর টুকরো ফাঁকা হতে পারে না। p শুধু অস্তিত্বের দাবি; প্রমাণে তার মান লাগে না।
প্র ০৩Ogden-এর lemma কেন inherent ambiguity প্রমাণের জন্য তৈরি হয়েছিল? “চিহ্নিত অবস্থান” ধারণা দিয়ে কোন ধরনের যুক্তি সম্ভব হয়?
পর্ব ২৭-এ দেখেছেন, কিছু grammar ambiguous, কিন্তু অন্য একটি grammar দিয়ে সেই ambiguity দূর করা যায়। কিছু ভাষার ক্ষেত্রে তা অসম্ভব: প্রতিটি grammar-ই ambiguous. মানক উদাহরণ {aibjck : i = j অথবা j = k}. এটি প্রমাণ করা কঠিন, কারণ দাবিটি সব সম্ভাব্য grammar সম্পর্কে। দরকার এমন একটি হাতিয়ার, যা যেকোনো grammar-এর parse tree-র ভেতরের গঠন সম্পর্কে নিশ্চিত কিছু বলে, আর সেটিও আপনার বেছে নেওয়া এলাকায়।
Ogden ১৯৬৮ সালে ঠিক এটিই দেন। প্রচলিত প্রমাণের ধারণা মোটামুটি এমন (পূর্ণ প্রমাণ দীর্ঘ, এখানে শুধু কাঠামো): anbncn+n!-এর মতো একটি string নিয়ে a-গুলো চিহ্নিত করলে, Ogden নিশ্চিত করে যে কোনো pump-জোড়া a ছোঁয়, আর |vxy| ও n!-এর হিসাব মিলিয়ে দেখানো যায় যে সেই pump a আর b একসঙ্গে বাড়ায়। ফলে i = j শাখার একটি গাছ পাওয়া যায়। একইভাবে c চিহ্নিত করে j = k শাখার একটি গাছ। তারপর ambmcm-এর মতো একটি string-এ দুই ধরনের গাছই হাজির হয়, আর দেখানো যায় তারা আলাদা: সেই string-এর দুটি parse tree, অর্থাৎ ambiguity. চিহ্ন দিয়ে আপনি বলতে পারছেন “pump এই জায়গায়ই হবে”, যা সাধারণ lemma বলতে পারে না।
সাধারণ ভাবে, চিহ্নিত অবস্থান হলো প্রতিপক্ষের স্বাধীনতা কমানোর উপায়। সাধারণ lemma-য় প্রতিপক্ষ যেকোনো জায়গায় pump বসাতে পারেন, তাই ভাষায় একটি “নিরীহ” অংশ থাকলে (Ld-এর a-খণ্ড) সেখানে লুকিয়ে থাকেন। Ogden-এ আপনি নিরীহ অংশ চিহ্নহীন রাখেন, আর প্রতিপক্ষকে চিহ্নিত এলাকায় আসতে বাধ্য করেন। এই নকশা পরে আরও শক্ত রূপ পেয়েছে, যেমন Bader–Moura-র ১৯৮২ সালের সাধারণীকরণ, যেখানে কিছু অবস্থান “নিষিদ্ধ”-ও করা যায়।
মূল উপলব্ধি: Ogden-এর lemma আপনাকে বলতে দেয় pump কোথায় হবে। এতে non-CFL প্রমাণ সহজ হয়, আর parse tree-র গঠন নিয়ে যুক্তি দেওয়া যায়, যা inherent ambiguity-র মতো “সব grammar” সম্পর্কিত দাবির জন্য দরকার।
প্র ০৪Parikh-এর theorem বলে, গণনার দিক থেকে প্রতিটি CFL একটি regular language-এর মতো। তাহলে stack আসলে কী বাড়তি দেয়?
একটি string-এর Parikh ভেক্টর মানে প্রতিটি চিহ্ন কতবার আছে তার তালিকা: aabcb-এর ভেক্টর (2, 2, 1). Parikh-এর theorem বলে, যেকোনো CFL-এর সব string-এর ভেক্টরের সেট semilinear: কয়েকটি “ভিত্তি + পর্যায়ের গুণিতক” রূপের সেটের union. আর এমন প্রতিটি সেট কোনো regular language-এরও ভেক্টর-সেট। যেমন anbn-এর ভেক্টর-সেট {(n, n)}, যা regular ভাষা (ab)∗-এরও ভেক্টর-সেট। অর্থাৎ “কোন চিহ্ন কতবার” প্রশ্নে CFL কোনো regular ভাষার চেয়ে বেশি কিছু করতে পারে না।
তাহলে stack-এর বাড়তি ক্ষমতা কোথায়? চিহ্নগুলোর বিন্যাসে। anbn আর (ab)∗-এ চিহ্নের সংখ্যা একই রকম, কিন্তু anbn চায় সব a আগে, তারপর সমান সংখ্যক b; এই “দূরের মিল” রাখতে stack লাগে। একক-চিহ্নের alphabet-এ বিন্যাস বলে কিছু নেই, শুধু দৈর্ঘ্য; তাই সেখানে stack কোনো কাজে আসে না, আর প্রতিটি unary CFL regular. এ কারণেই an² বা prime দৈর্ঘ্যের ভাষা CFL নয়: তাদের দৈর্ঘ্য-সেট ultimately periodic নয় (পর্ব ১৭-এর প্র ০৪)।
এই ফলের বাস্তব প্রয়োগও আছে। Program verification-এ অনেক সময় প্রশ্ন ওঠে, recursive প্রোগ্রামের কোনো execution-এ কোনো ঘটনা কতবার ঘটতে পারে; recursion-কে stack বা CFG হিসেবে দেখলে Parikh-এর theorem বলে, এই গণনাগুলো linear সমীকরণ আর অসমতা দিয়ে বর্ণনা করা যায়, যা automated tool দিয়ে পরীক্ষা করা সম্ভব। Semilinear সেট Presburger arithmetic-এ (শুধু যোগসহ পূর্ণসংখ্যার যুক্তি) ঠিক সংজ্ঞায়িত সেট বলে পরিচিত, তাই automata, logic আর সংখ্যাতত্ত্ব এখানে মিলে যায়।
মূল উপলব্ধি: Stack গণনায় কিছু যোগ করে না, যোগ করে ক্রম: কোন চিহ্নের সঙ্গে কোন চিহ্ন nested ভাবে মেলে। তাই unary ভাষায় CFL আর regular এক, আর an²-এর মতো ভাষা stack দিয়েও ধরা যায় না।
প্র ০৫Chomsky hierarchy-র প্রতিটি স্তরে “pumping”-ধরনের যুক্তি আছে কি? context-sensitive বা decidable স্তরে কী হয়?
Regular আর context-free স্তরে pumping কাজ করে, কারণ দুই ক্ষেত্রেই যন্ত্র বা grammar-এর একটি সসীম উপাদান (state বা variable) আছে, আর লম্বা গণনায় সেটি পুনরাবৃত্ত হতে বাধ্য। পুনরাবৃত্তি থেকে আসে কাটা-জোড়া করার স্বাধীনতা: চক্র বাদ দেওয়া বা বাড়ানো, উপগাছ বদলানো। পর্ব ১৭-এর ইতিহাস-অংশে দেখেছেন, Bar-Hillel, Perles আর Shamir-এর ১৯৬১ সালের কাজে CFL-এর lemma এসেছিল, আর regular রূপটি তার একটি বিশেষ ক্ষেত্র হিসেবেও দেখা যায়।
Context-sensitive স্তরে (linear bounded automaton) এই যুক্তি ভেঙে পড়ে। সেখানে যন্ত্রের মোট অবস্থা (state, tape-এর পুরো লেখা, মাথার অবস্থান) input-এর দৈর্ঘ্যের সঙ্গে ঘাতের হারে বাড়ে, তাই “সসীম উপাদান দুবার আসবে” বলার মতো স্থির সংখ্যা নেই। anbncn context-sensitive, আর a2n-এর মতো ভাষাও, যা কোনো pump সহ্য করে না। এই স্তরের ভাষা আলাদা করতে গবেষকেরা সাধারণত অন্য যুক্তি ব্যবহার করেন, যেমন জায়গা আর সময়ের সীমা গোনা বা diagonalization.
Decidable আর recognizable স্তরে pumping-এর জায়গা নেয় diagonalization (পর্ব ৫১)। সেখানে প্রশ্ন আর “কোন গঠন পুনরাবৃত্ত হয়” নয়, বরং “কোন যন্ত্র নিজের সম্পর্কে প্রশ্নের উত্তর দিতে পারে”। তবে একটি সূক্ষ্ম সম্পর্ক থেকে যায়: CFL-এর কিছু decision problem, যেমন emptiness আর finiteness, decidable, আর finiteness-এর algorithm ঠিক pumping-এর ধারণা কাজে লাগায়: CNF grammar-এর variable-graph-এ চক্র থাকা মানে কোনো variable নিজের ভেতরে আবার আসে, অর্থাৎ pump করা যায়, তাই ভাষা অসীম। এটি পর্ব ৩৭-এর বিষয়। অন্যদিকে দুটি CFG একই ভাষা দেয় কি না, এই প্রশ্ন undecidable (পর্ব ৫৪), আর সেখানে pumping কোনো সাহায্য করে না।
মূল উপলব্ধি: Pumping সসীম উপাদানের পুনরাবৃত্তির ফল, তাই এটি নিচের দুই স্তরের বৈশিষ্ট্য। ওপরের স্তরে যন্ত্রের অবস্থা সীমাহীন, তাই সেখানে diagonalization আর resource-গোনার মতো যুক্তি লাগে।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। adversary_abc.py ব্লকে নিজের ভাষা আর s বসিয়ে উত্তরও যাচাই করতে পারেন।
-
নকশা ও প্রতিপক্ষ: L = {aibjck : i = j অথবা j = k}. (ক) L-এর একটি CFG নকশা করুন। (খ) s = apbpcp দিয়ে কেউ L non-CFL প্রমাণের চেষ্টা করলেন। প্রতিপক্ষের একটি জয়ী বিভাজন দিন।
(ক) দুটি শাখার union: S → XC ∣ AY; X → aXb ∣ ε (anbn); C → cC ∣ ε (c∗); A → aA ∣ ε (a∗); Y → bYc ∣ ε (bncn). প্রথম শাখা দেয় i = j, দ্বিতীয়টি j = k. Scratch-এ দৈর্ঘ্য 8 পর্যন্ত সব string-এ (৪৭টি সদস্য) grammar আর সংজ্ঞা মিলেছে।
(খ) u = ap−1, v = a, x = ε, y = b, z = bp−1cp (p ≥ 2). uvixyiz = ap−1+ibp−1+icp, যেখানে a আর b সমান, তাই প্রতিটি i-তে ∈ L. L CFL বলেই এমন বিভাজন থাকবে; এটি পর্ব ২৭-এর inherently ambiguous ভাষা, কিন্তু non-CFL নয়। Scratch-এ p = 2 থেকে 6-এ i = 0 থেকে 7 যাচাই করা হয়েছে।
-
প্রমাণ: L = {anbmcndm : n, m ≥ 0} context-free নয়, প্রমাণ করুন। প্রমাণের কোন ধাপে |vxy| ≤ p অপরিহার্য, তাও দেখান।
- বিরোধের জন্য L CFL ধরুন, p তার pumping length. s = apbpcpdp ∈ L, |s| = 4p ≥ p. — আপনার চাল
- যেকোনো বিভাজন নিন। v বা y-তে দুই রকম চিহ্ন থাকলে i = 2 নিন: ক্রম ভাঙে (যেমন …abab…), তাই ∉ L. এখানে i = 0 নিরাপদ নয়, কারণ মুছে ফেললে ক্রম ভাঙে না। — ক্ষেত্র ১
- নইলে v আর y প্রতিটি একটি খণ্ডের ভেতরে। |vxy| ≤ p, আর প্রতিটি খণ্ড p দৈর্ঘ্যের, তাই vxy বড়জোর দুটি পাশাপাশি খণ্ড ছোঁয়: (a, b), (b, c) বা (c, d) জোড়া, বা একটি খণ্ড। — |vxy| ≤ p এখানেই লাগে
- i = 0 নিন। vy যে খণ্ডগুলো ছোঁয়, তাদের অন্তত একটির সংখ্যা কমে। a কমলে c কমে না (a আর c পাশাপাশি নয়), তাই a ≠ c; b কমলে d কমে না; c কমলে a কমে না; d কমলে b কমে না। প্রতিটি ক্ষেত্রে ∉ L. — ক্ষেত্র ২
- সব বিভাজনে একটি i পাওয়া গেল, তাই L CFL নয়। ∎
|vxy| ≤ p ছাড়া v = a, y = c বৈধ হতো, আর তখন a আর c একসঙ্গে বাড়ে-কমে: string ভাষাতেই থাকে। JavaScript ব্লকের শেষ সারি ঠিক এটি দেখায়।
-
Output অনুমান: L = {aibjck : i ≤ j ≤ k}, s = aabbcc, p = 2. adversary_abc.py-এর
splitsএখানে ৩৭টি বৈধ বিভাজন দেয়। (ক) শুধু i = 2 চেষ্টা করলে কয়টি বিভাজনে string L-এ থেকে যায়, আর সেগুলোর vy দেখতে কেমন? (খ) i ∈ {0, 2} দুটিই চেষ্টা করলে?(ক) ১১টি। ৯টিতে vy শুধু c দিয়ে গড়া: c বাড়লে a ≤ b ≤ c আরও সত্য হয়। বাকি ২টিতে v-অংশে বা x-এ b আর y = c: (v = ε, x = b, y = c) দেয় aabbccc, আর (v = b, y = c) দেয় aabbbccc; দুটিতেই b ≤ c টেকে। এগুলো উদাহরণ ৫.৩-এর ক্ষেত্র (খ), যেখানে i = 2 অচল।
(খ) শূন্য: ওই ১১টির প্রতিটিতে vy-তে কোনো a নেই, আর i = 0-এ c বা b কমে নিয়ম ভাঙে (যেমন aabbc-এ b > c). বাকি বিভাজনগুলো i = 2-এ হারে। Scratch-এ চালিয়ে ঠিক এই সংখ্যাগুলো এসেছে (৩৭, ১১, ০)।
-
CFL না non-CFL? প্রতিটির জন্য হয় একটি CFG দিন, নয়তো non-CFL প্রমাণ করুন: (ক) {anbncm : n, m ≥ 0}; (খ) {w ∈ {a, b, c}∗ : a, b আর c সমান সংখ্যক}; (গ) {a2n : n ≥ 0}; (ঘ) {wwR : w ∈ {a, b}∗}.
(ক) CFL: S → XC, X → aXb ∣ ε, C → cC ∣ ε.
(খ) Non-CFL. s = apbpcp; |vxy| ≤ p বলে vy-তে a আর c একসঙ্গে নেই, তাই i = 2-এ অন্তত একটি চিহ্নের সংখ্যা বাড়ে আর অছোঁয়া চিহ্নটি p থাকে: সংখ্যা অসমান, ∉ L. ∎ এখানে ক্রম কোনো ভূমিকা রাখে না, তাই “ক্রম ভাঙে” ক্ষেত্রটিও একই যুক্তিতে মেটে। Scratch-এ p = 1 থেকে 5-এ সব বিভাজন যাচাই করা হয়েছে। বিকল্প পথ: এটি CFL হলে a∗b∗c∗-এর সঙ্গে ছেদও CFL হতো (পর্ব ৩৭), কিন্তু ছেদটি anbncn.
(গ) Non-CFL. p দেওয়া থাকলে m নিন যাতে 2m > p, আর s = a2m. vy = ak, 1 ≤ k ≤ p < 2m. i = 2-এ দৈর্ঘ্য 2m + k, যা 2m আর 2m+1-এর কঠোরভাবে মাঝে: 2-এর ঘাত নয়। ∎ (Parikh-এর theorem থেকেও আসে: unary CFL regular হতো।)
(ঘ) CFL: S → aSa ∣ bSb ∣ ε. এটি nested মিল, তাই stack যথেষ্ট; ww-এর সঙ্গে পার্থক্যটি প্র ০১-এ।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমCFL pumping lemma-র প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- L-এর জন্য একটি CNF grammar নিয়ে p = 2|V| ধরা
- |s| ≥ p থেকে s-এর parse tree-র উচ্চতা অন্তত |V| + 1 দেখানো
- একটি সবচেয়ে লম্বা পথের নিচের |V| + 1টি variable-এ pigeonhole দিয়ে একটি পুনরাবৃত্ত variable R পাওয়া
- দুই R-এর উপগাছের yield থেকে s = uvxyz কাটা আর |vy| ≥ 1, |vxy| ≤ p দেখানো
- R ⇒∗ vRy বারবার খাটিয়ে প্রতিটি i-তে uvixyiz ∈ L দেখানো
Context-free language-এর pumping lemma-য় s = uvxyz বিভাজনের শর্ত কোনটি?
- |y| ≥ 1 আর |xy| ≤ p
- |v| ≥ 1, |y| ≥ 1 আর |uvx| ≤ p
- |vy| ≥ 1 আর |vxy| ≤ p
- |vy| ≥ 1 আর |vxy| ≥ p
anbncn-এর প্রমাণে s = apbpcp নেওয়া হলো। |vxy| ≤ p থেকে সরাসরি কোন সিদ্ধান্ত আসে?
- vxy s-এর প্রথম p চিহ্নে, তাই শুধু a
- vxy-তে a আর c একসঙ্গে থাকতে পারে না
- v আর y দুটিই একই চিহ্নের
- |vxy| ঠিক p
একজন লিখলেন: “anbn context-free নয়। s = apbp; |vxy| ≤ p, তাই vxy-তে শুধু a; i = 2 দিলে a বেশি, বিরোধ।” এই যুক্তি সম্পর্কে কোনটি ঠিক?
- ঠিক, anbn CFL নয়
- ভুল, কারণ s ∉ L
- ঠিক, তবে i = 0 নিলে আরও ভালো হতো
- ভুল, কারণ vxy সীমানায় বসতে পারে; anbn আসলে CFL
একটি CNF grammar-এ ৬টি variable. CFL pumping lemma-র CNF-ভিত্তিক প্রমাণে p কত নেওয়া হয়, আর |s| ≥ p হলে s-এর parse tree-র উচ্চতা কমপক্ষে কত?
- p = 64, উচ্চতা ≥ 7
- p = 6, উচ্চতা ≥ 6
- p = 64, উচ্চতা ≥ 6
- p = 36, উচ্চতা ≥ 7
L = {aibjckdl : i = 0 অথবা j = k = l} সাধারণ CFL pumping lemma-র শর্ত পূরণ করে। কোন উপায়ে দেখানো যায় যে L context-free নয়?
- দেখানো যায় না, কারণ শর্ত পূরণ করলে L CFL
- Ogden-এর lemma দিয়ে, শুধু b-গুলো চিহ্নিত করে
- L সসীম বলে দেখিয়ে
- Parikh-এর theorem দিয়ে, গণনা-সেট semilinear নয় দেখিয়ে
নিচের কোন ভাষাটি context-free (Σ = {a, b})?
- {ww : w ∈ {a, b}∗}
- {an² : n ≥ 0}
- {wwR : w ∈ {a, b}∗}
- {anbmanbm : n, m ≥ 0}
ww-এর জন্য s = apbapb নিলে CFL pumping প্রমাণ কেন ব্যর্থ হয়?
- প্রতিপক্ষ vxy-কে মাঝের b ঘিরে বসিয়ে দুই অর্ধেক একসঙ্গে বাড়াতে-কমাতে পারেন
- কারণ s ww-এ নেই
- কারণ |s| < p
- কারণ ww আসলে context-free
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- L context-free ⇒ ∃p ≥ 1, যাতে L-এর প্রতিটি s (|s| ≥ p) = uvxyz, |vy| ≥ 1, |vxy| ≤ p, আর প্রতিটি i ≥ 0-এ uvixyiz ∈ L.
- প্রমাণ: CNF, p = 2|V|; উঁচু গাছের লম্বা পথের নিচের |V| + 1টি variable-এ একটি পুনরাবৃত্তি; দুই উপগাছের yield থেকে v, x, y.
- |vxy| ≤ p দৈর্ঘ্যের সীমা, অবস্থানের নয়: vxy যেকোনো জায়গায়, কিন্তু বড়জোর দুটি পাশাপাশি খণ্ড ছোঁয়।
- Non-CFL: anbncn (i = 2), ww (s = apbpapbp, i = 0), an², i ≤ j ≤ k (দুই ক্ষেত্রে দুই i), anbmcndm.
- Lemma শুধু প্রয়োজনীয় শর্ত; Ogden-এর lemma চিহ্নিত অবস্থান দিয়ে প্রতিপক্ষকে আসল এলাকায় আনে; Parikh: unary CFL = regular.
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ১৭ · Regular language-এর pumping lemma — non-regular প্রমাণফিরে দেখুনপ্রতিপক্ষের খেলা, quantifier-এর ক্রম আর সাধারণ ভুল, যা এই পর্বে CFL-এ খাটানো হলো।
- পর্ব ২৯ · Chomsky normal form — রূপান্তর ধাপে ধাপেফিরে দেখুনCNF-এ রূপান্তর আর উচ্চতার সীমা |w| ≤ 2h−1, যার ওপর এই পর্বের প্রমাণ দাঁড়িয়ে।
- পর্ব ৩৪ · PDA আর CFG-এর সমতা — দুই দিকের রূপান্তরপটভূমিকেন “কোনো CFG নেই” আর “কোনো PDA নেই” একই কথা।
- পর্ব ২৭ · Ambiguity — দ্ব্যর্থক grammar আর inherent ambiguityপটভূমিযে inherently ambiguous ভাষার জন্য Ogden-এর lemma তৈরি হয়েছিল।
- পর্ব ৩৭ · CFL-এর closure আর decision property — কী decidable, কী নয়পরের পর্বছেদ আর complement-এ CFL বদ্ধ নয় কেন, আর emptiness ও finiteness-এর algorithm.
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৩৭ CFL-এর closure আর decision property.
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৩২ — Pigeonhole principleপাশের ট্র্যাককবুতরের খোপের নীতি, গণিতের দিক থেকে।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৬৫ — Tree-র ধর্ম আর m-ary tree-র হিসাবপাশের ট্র্যাকউচ্চতা আর পাতার সংখ্যার সম্পর্ক, যা প্রমাণের মূল হিসাব।