এই পর্বে যা শিখবেন
- Pumping lemma-র পূর্ণ বক্তব্য, চারটি quantifier-এর ক্রম আর প্রতিটি শর্তের অর্থ
- DFA-র state-এর ওপর pigeonhole দিয়ে lemma-র পূর্ণ প্রমাণ, আর Python-এ সেই প্রমাণ চালিয়ে দেখা
- প্রতিপক্ষের খেলা হিসেবে non-regular প্রমাণ লেখা: anbn, বন্ধনী, an², prime, ww, palindrome
- সবচেয়ে সাধারণ ভুলগুলো চেনা: বিভাজন নিজে বেছে নেওয়া, p-এর মান বসিয়ে দেওয়া, শুধু ওপরের দিকে pump করা
- কেন lemma যথেষ্ট শর্ত নয়, আর কখন closure property বা Myhill–Nerode বেশি সুবিধাজনক
১ · সসীম স্মৃতির সীমা — কেন নতুন হাতিয়ার দরকার
এ পর্যন্ত মডিউল ২ আর ৩-এ আপনি দেখেছেন, কোনো language regular প্রমাণ করা তুলনামূলক সহজ: একটি DFA, NFA বা regular expression বানিয়ে দেখালেই চলে। উল্টো প্রশ্নটি কঠিন। “এই language-এর জন্য কোনো DFA নেই” বলতে হলে পৃথিবীর সব সম্ভাব্য DFA, যত state-ই থাকুক, একসঙ্গে বাতিল করতে হয়। একটি একটি করে চেষ্টা করে সেটি কখনো শেষ হবে না। দরকার একটি সাধারণ যুক্তি, যা যেকোনো finite automaton-এর ওপর একবারে খাটে।
বাজারঘরের order query ভাষায় শর্তগুলো বন্ধনী দিয়ে জোড়া হয়। কেউ প্রস্তাব দিলেন, “বন্ধনী সুষম কি না, একটি regex দিয়েই যাচাই করি।” পর্ব ০১-এ আপনি দেখেছেন, এটি অসম্ভব: pigeonhole principle দিয়ে প্রমাণ হয়েছিল যে কোনো DFA সুষম বন্ধনীর language BAL চেনে না। পর্ব ০৪-এ একই যুক্তির সাধারণ রূপ এসেছিল: k-টি state-এর DFA দৈর্ঘ্য k-এর string পড়লে k + 1টি অবস্থানে কোনো state দুবার আসে। এই পর্ব সেই পর্যবেক্ষণকে একটি পূর্ণ উপপাদ্যে পরিণত করে, যা non-regular প্রমাণের সবচেয়ে পরিচিত হাতিয়ার।
ধরুন একজন রিকশাওয়ালা পুরান ঢাকার একটি এলাকায় ঘোরেন, যেখানে মোট ১০টি মোড়। তাঁর খাতায় শুধু লেখা থাকে এখন কোন মোড়ে আছেন, আর কিছু নয়। তিনি যদি ১০টির বেশি মোড় পার হন, তবে কোনো একটি মোড়ে তিনি অন্তত দুবার এসেছেন। দুবার আসার মাঝের পথটুকু একটি চক্কর। এখন মজার কথা: চক্করটি বাদ দিলে, বা একই চক্কর তিনবার দিলে, শেষে তিনি ঠিক একই জায়গায় পৌঁছাবেন, আর খাতা দেখে কেউ বুঝবে না কতবার ঘোরা হয়েছিল। Finite automaton ঠিক এই রিকশাওয়ালা: তার একমাত্র স্মৃতি “এখন কোন state”, তাই একটি চক্কর কতবার ঘোরা হলো, সেটি সে গুনতে পারে না।
এই অক্ষমতাই anbn = {ε, ab, aabb, aaabbb, …}-এর মতো language-কে regular হতে দেয় না। যন্ত্রটিকে মনে রাখতে হতো কয়টি a পড়া হয়েছে, আর সংখ্যাটি যেকোনো বড় হতে পারে। a-অংশের ভেতরে একটি চক্কর থাকলে, সেটি দুবার ঘুরিয়ে a-এর সংখ্যা বাড়ানো যায়, অথচ যন্ত্র একই state-এ থেকে একই b-অংশ গ্রহণ করে। ফলে যন্ত্রটি এমন string-ও গ্রহণ করে, যেখানে a বেশি আর b কম। Pumping lemma এই যুক্তিকে সব regular language-এর জন্য একটি সাধারণ ধর্ম হিসেবে লেখে।
এই পর্বের notation: DFA M = (Q, Σ, δ, q0, F), δ total (পর্ব ০৭)। |w| হলো w-এর দৈর্ঘ্য, ε ফাঁকা string (কিছু বইয়ে λ), আর yi মানে y-কে i বার পরপর লেখা, তাই y0 = ε (string-এর power). anbn দিয়ে বোঝানো হয়েছে {anbn : n ≥ 0}. কোডে state-এর নাম q0, q1, …; বাংলা লেখা তাদের অর্থ ব্যাখ্যা করে।
২ · Pumping lemma-র বক্তব্য — প্রতিটি quantifier সহ
উপপাদ্যটি ছোট, কিন্তু এর প্রতিটি শব্দের দাম আছে। বেশিরভাগ ভুল আসে quantifier-এর ক্রম গুলিয়ে ফেলা থেকে, তাই আগে পুরো বক্তব্যটি দেখুন।
L যদি একটি regular language হয়, তবে একটি পূর্ণসংখ্যা p ≥ 1 আছে (একে বলে pumping length), যাতে L-এর প্রতিটি string s, যার |s| ≥ p, তিন ভাগে লেখা যায়, s = xyz, এমনভাবে যে নিচের তিনটি শর্তই সত্য:
১. |y| ≥ 1 (y ফাঁকা নয়);
২. |xy| ≤ p (x আর y মিলে s-এর প্রথম p চিহ্নের মধ্যে থাকে);
৩. প্রতিটি i ≥ 0-এর জন্য xyiz ∈ L.
প্রতীকে লিখলে quantifier-এর ক্রম স্পষ্ট হয়:
প্রতিটি প্রতীক কথায়: ∃ মানে “অন্তত একটি আছে”, ∀ মানে “প্রতিটির জন্য”, ∧ মানে “এবং”, ⇒ মানে “হলে”। চারটি quantifier পালাক্রমে আসে: ∃∀∃∀. এমন পালাক্রমের nested quantifier-এ ক্রম বদলালে অর্থ পুরো বদলে যায় (ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ০৫)। শর্ত তিনটির প্রতিটি কেন আছে, সেটিও দেখুন:
- |y| ≥ 1 না থাকলে lemma অর্থহীন হতো: y = ε নিলে xyiz = s সব i-তে, তাই যেকোনো language “pump” করত।
- |xy| ≤ p বলে চক্রটি s-এর শুরুর দিকেই পাওয়া যায়। প্রমাণে এটি বিনা খরচে আসে, আর non-regular প্রমাণে এটিই সবচেয়ে কাজের শর্ত: s = apbp নিলে y-কে a-অংশের ভেতরেই থাকতে হয়।
- প্রতিটি i ≥ 0, শূন্যসহ। i = 0 মানে y বাদ দেওয়া (“pump down”), i ≥ 2 মানে y বারবার (“pump up”). i = 1 দিলে মূল s ফেরত আসে।
- |s| ≥ p শর্তটি ছোট string-গুলোকে ছাড় দেয়। তাই প্রতিটি সসীম language lemma-র শর্ত পূরণ করে: সবচেয়ে লম্বা string-এর চেয়ে বড় p নিলে কোনো s-ই বাকি থাকে না। এটি ঠিকই আছে, কারণ প্রতিটি সসীম language-ই regular.
Lemma-র ছবি: একটি পথ, একটি চক্র
উপরে: DFA-র ভেতরে s-এর পথ। x নিয়ে যায় q0 থেকে পুনরাবৃত্ত state q-তে, y হলো q থেকে q-তে ফেরার চক্র, z নিয়ে যায় accepting state-এ। নিচে: string-টির তিন ভাগ।
Non-regular প্রমাণে ব্যবহার হয় lemma-র contrapositive, অর্থাৎ “উপসংহার মিথ্যা হলে অনুমানও মিথ্যা” (proof by contradiction-এর কাছাকাছি)। উপসংহারটিকে অস্বীকার করলে প্রতিটি ∃ হয়ে যায় ∀, আর প্রতিটি ∀ হয়ে যায় ∃:
| Lemma-তে | অস্বীকারে (non-regular প্রমাণে) | খেলায় কে বাছে |
|---|---|---|
| ∃p ≥ 1 | ∀p ≥ 1 | প্রতিপক্ষ (আপনার যুক্তি যেকোনো p-তে চলতে হবে) |
| ∀s ∈ L, |s| ≥ p | ∃s ∈ L, |s| ≥ p | আপনি (p-এর ওপর নির্ভর করে s বাছেন) |
| ∃x, y, z (শর্তসহ) | ∀x, y, z (শর্তসহ) | প্রতিপক্ষ (সব বিভাজন সামলাতে হবে) |
| ∀i ≥ 0 : xyiz ∈ L | ∃i ≥ 0 : xyiz ∉ L | আপনি (বিভাজন দেখে i বাছেন) |
৩ · প্রমাণ — pigeonhole আর DFA-র চক্র
প্রমাণটি একটি DFA-র ভেতরের ঘটনাকে সোজাসুজি লেখে। এখানে DFA-র run মানে string পড়ার সময় যন্ত্র যে state-ক্রম পার হয়।
প্রমাণ (উপপাদ্য ২.১):
- L regular, তাই একটি DFA M = (Q, Σ, δ, q0, F) আছে যার L(M) = L. p = |Q| নিন, অর্থাৎ M-এর state-সংখ্যা; p ≥ 1, কারণ q0 ∈ Q. — regular language-এর সংজ্ঞা (পর্ব ০৭)
- ধরুন s = s1s2⋯sn ∈ L আর n ≥ p. M-এর run r0, r1, …, rn লিখুন: r0 = q0 আর rt = δ(rt−1, st). s ∈ L, তাই rn ∈ F. — DFA-র গ্রহণের সংজ্ঞা
- প্রথম p + 1টি state r0, r1, …, rp দেখুন (n ≥ p বলে এগুলো আছে)। এখানে p + 1টি অবস্থান কিন্তু state মাত্র p-টি, তাই কোনো 0 ≤ i < j ≤ p-তে ri = rj; এই state-কে বলুন q. — pigeonhole principle
- x = s1⋯si, y = si+1⋯sj, z = sj+1⋯sn নিন। তাহলে s = xyz, |y| = j − i ≥ 1, আর |xy| = j ≤ p. — i < j ≤ p
- Run থেকে: δ̂(q0, x) = q, δ̂(q, y) = q, আর δ̂(q, z) = rn ∈ F (δ̂ হলো পুরো string-এর transition; কিছু বইয়ে δ∗)। — run-এর টুকরো
- k-এর ওপর সহজ induction-এ δ̂(q, yk) = q প্রতিটি k ≥ 0-তে: k = 0-তে y0 = ε, আর k থেকে k + 1-এ δ̂(q, yky) = δ̂(q, y) = q. — induction on k
- তাই যেকোনো i ≥ 0-তে δ̂(q0, xyiz) = δ̂(δ̂(δ̂(q0, x), yi), z) = δ̂(q, z) ∈ F, অর্থাৎ xyiz ∈ L. ∎ — δ̂(q, uv) = δ̂(δ̂(q, u), v)
লক্ষ করুন, p কোনো জাদুকরি সংখ্যা নয়: এটি শুধু কোনো একটি DFA-র state-সংখ্যা। সেই DFA আপনি দেখেননি, তাই non-regular প্রমাণে p-এর মান জানা যায় না, শুধু জানা যায় যে এটি কোনো একটি সসীম সংখ্যা। ছোট DFA পেলে ছোট p-ও কাজ করে, আর p কাজ করলে তার চেয়ে বড় যেকোনো সংখ্যাও কাজ করে।
নিচের stepper প্রমাণটিকে পর্ব ০৮-এর DIV3 DFA-তে চালায়: Σ = {0, 1}-এর ওপর যে string-গুলোর binary মান ৩ দিয়ে বিভাজ্য, state মানে এ পর্যন্ত পড়া মানের ৩ দিয়ে ভাগশেষ। এখানে p = 3, আর s = 1001 (মান 9).
1p = 3, s = 10012প্রথম p চিহ্নের run3pigeonhole: একটি state দুবার4x, y, z কাটা5i = 0: চক্র বাদ6i = 2: চক্র দুবার
| পড়া অংশ | |
| state-ক্রম | |
| শর্ত |
- শুরু। DIV3-এর DFA-তে ৩টি state, তাই p = 3. s = 1001-এর মান 9, ৩ দিয়ে বিভাজ্য, তাই s ∈ L, আর |s| = 4 ≥ 3. প্রমাণ বলছে, s-কে xyz-এ ভাঙা যাবে।
- প্রথম p চিহ্ন। 1 পড়ে ভাগশেষ 1 (q1), 0 পড়ে 2 (q2), আরেকটি 0 পড়ে 4 mod 3 = 1 (আবার q1). r0 থেকে r3 পর্যন্ত চারটি অবস্থান: q0, q1, q2, q1.
- Pigeonhole. চারটি অবস্থান, তিনটি state: একটি state দুবার আসতেই হবে। এখানে r1 = r3 = q1, অর্থাৎ i = 1 আর j = 3.
- কাটা। x = s1 = 1, y = s2s3 = 00, z = s4 = 1. |y| = 2 ≥ 1 আর |xy| = 3 ≤ p. y পড়ে যন্ত্র q1 থেকে আবার q1-এ ফেরে: এটিই চক্র।
- Pump down. i = 0-তে xz = 11: q0 থেকে 1 পড়ে q1, আরেকটি 1 পড়ে q0. মান 3, ৩ দিয়ে বিভাজ্য, তাই গৃহীত। চক্র বাদ দেওয়ায় যন্ত্র কিছু টের পায়নি।
- Pump up. i = 2-তে 100001: চক্রটি q1-এ দুবার ঘোরে, তারপর শেষ 1 পড়ে q0. মান 33 = 3 × 11, গৃহীত। নিচের Python ব্লক i = 0 থেকে 5 পর্যন্ত সব ক্ষেত্র যাচাই করে।
প্রমাণটি গঠনমূলক (constructive): DFA আর s দেওয়া থাকলে x, y, z যান্ত্রিকভাবে বের করা যায়। নিচের ব্লক ঠিক উপরের ধাপ ১–৪ কোডে লেখে, তারপর xyiz-গুলো DFA-তে চালিয়ে দেখে। চারটি ভিন্ন s দেওয়া হয়েছে।
# DIV3 DFA: binary value mod 3 (state = remainder so far)
D = {("q0", "0"): "q0", ("q0", "1"): "q1", ("q1", "0"): "q2",
("q1", "1"): "q0", ("q2", "0"): "q1", ("q2", "1"): "q2"}
START, FINAL = "q0", {"q0"}
p = 3 # number of states = pumping length
def run(w):
q = START
for c in w: q = D[q, c]
return q
def split(s): # the proof of the lemma, as code
seen, q = {START: 0}, START # state -> first position
for t, c in enumerate(s[:p], start=1):
q = D[q, c]
if q in seen: # pigeonhole: a state repeats
i, j = seen[q], t
return s[:i], s[i:j], s[j:], q
seen[q] = t
for s in ["1001", "110", "10010", "111111"]:
x, y, z, q = split(s)
ok = all(run(x + y * i + z) in FINAL for i in range(6))
print(f"s={s:7} repeat {q}: x={x or 'ε'} y={y} z={z or 'ε'}",
f"|xy|={len(x + y)} i=0..5 all accepted: {ok}")
x, y, z, q = split("1001")
for i in range(4):
w = x + y * i + z
print(f" i={i}: {w:9} value {int(w, 2):4} ends in {run(w)}")আসল আউটপুট (ব্রাউজারের Python):
s=1001 repeat q1: x=1 y=00 z=1 |xy|=3 i=0..5 all accepted: True
s=110 repeat q0: x=ε y=11 z=0 |xy|=2 i=0..5 all accepted: True
s=10010 repeat q1: x=1 y=00 z=10 |xy|=3 i=0..5 all accepted: True
s=111111 repeat q0: x=ε y=11 z=1111 |xy|=2 i=0..5 all accepted: True
i=0: 11 value 3 ends in q0
i=1: 1001 value 9 ends in q0
i=2: 100001 value 33 ends in q0
i=3: 10000001 value 129 ends in q0
split function-টি প্রমাণের মতোই প্রথম p চিহ্ন পড়ে আর প্রথম যে state দ্বিতীয়বার আসে, সেখানেই থামে। seen dictionary মনে রাখে কোন state প্রথম কোন অবস্থানে এসেছিল; এটিই pigeonhole-এর খোপ। 110-এ চক্রটি শুরুতেই: q0 থেকে 11 পড়ে আবার q0 (মান 3), তাই x = ε. চারটি ক্ষেত্রেই |xy| ≤ 3, আর i = 0 থেকে 5 পর্যন্ত প্রতিটি pump করা string গৃহীত। শেষ চার লাইনে 1(00)i1-এর মান 3, 9, 33, 129: প্রতিটি ৩ দিয়ে বিভাজ্য। এটি কাকতালীয় নয়: x-এর পরে একটি 00 ঢোকালে x-অংশের মান 4 দিয়ে গুণ হয় আর z-অংশের মান একই থাকে (y-এর নিজের মান 0), আর 4 mod 3 = 1, তাই ভাগশেষ বদলায় না। এখানে মনে রাখুন, এই ব্লক lemma-কে একটি regular language-এ পরীক্ষা করছে; non-regular প্রমাণের কৌশল আসছে পরের অংশে।
৪ · প্রতিপক্ষের খেলা — non-regular প্রমাণের ছক
পালাক্রমের quantifier মনে রাখার সবচেয়ে সহজ উপায় হলো এটিকে দুই খেলোয়াড়ের একটি খেলা ভাবা। এটি একটি adversary argument: একজন প্রতিপক্ষ দাবি করছেন L regular, আর তাঁর হাতে একটি গোপন DFA আছে। আপনি দেখাতে চান দাবিটি মিথ্যা। প্রতিপক্ষ সবসময় নিজের সবচেয়ে সুবিধাজনক চাল দেন, তাই আপনার কৌশলকে তাঁর প্রতিটি সম্ভাব্য চালের বিরুদ্ধে জিততে হয়।
চার চালের খেলা
নীল ঘর প্রতিপক্ষের চাল, সবুজ ঘর আপনার। শেষ ঘরে আপনি জিতলে, আর সেটি প্রতিপক্ষের যেকোনো চালের বিরুদ্ধে ঘটলে, L regular নয়।
একটি non-regular প্রমাণ তাই সবসময় একই ছকে লেখা হয়:
- বিরোধের জন্য ধরুন L regular. তাহলে lemma একটি pumping length p দেয়, যার মান আপনি জানেন না।
- p দিয়ে লেখা একটি নির্দিষ্ট s ∈ L বাছুন, যাতে |s| ≥ p.
- যেকোনো বিভাজন s = xyz নিন, যেখানে |y| ≥ 1 আর |xy| ≤ p. শর্ত দুটি থেকে x আর y সম্পর্কে যা জানা যায়, লিখুন।
- প্রতিটি সম্ভাব্য ক্ষেত্রে একটি i দেখান, যাতে xyiz ∉ L.
- এটি lemma-র শর্ত ৩-এর বিরোধী, তাই L regular নয়। ∎
এবার সবচেয়ে পরিচিত উদাহরণটি পূর্ণভাবে। Stepper-এ ধারণা স্পষ্ট করতে p = 4 বসিয়ে একটি নির্দিষ্ট বিভাজন দেখানো হয়েছে, কিন্তু প্রতিটি ধাপের যুক্তি যেকোনো p আর যেকোনো বিভাজনে খাটে।
1ধরি L regular; প্রতিপক্ষ p দেন2আপনি: s = aᵖbᵖ3প্রতিপক্ষ: s = xyz4|xy| ≤ p ⇒ y-তে শুধু a5আপনি: i = 2 (বা 0)6বিরোধ ∎
| string | |
| কে বাছল | |
| যুক্তি |
- অনুমান। বিরোধের জন্য ধরুন L = {anbn : n ≥ 0} regular. Lemma একটি pumping length p দেয়। p-এর মান আপনি জানেন না; উদাহরণে 4 দেখানো হলেও যুক্তি যেকোনো p-এর।
- s বাছাই। s = apbp নিন। a আর b সমান সংখ্যক, তাই s ∈ L, আর |s| = 2p ≥ p. s-এর রূপ p দিয়ে লেখা, কারণ প্রতিপক্ষের p দেখেই s বাছার অধিকার আপনার আছে।
- বিভাজন। প্রতিপক্ষ যেকোনো বৈধ বিভাজন দিতে পারেন, যেমন x = a, y = aa, z = ab4. আপনি তাঁর বিভাজন বাছতে পারেন না; তাই পরের ধাপে সব বিভাজন একসঙ্গে সামলাতে হবে।
- সাধারণ রূপ। |xy| ≤ p, আর s-এর প্রথম p চিহ্নের সবগুলোই a. তাই x আর y দুটিতেই শুধু a আছে: y = ak, যেখানে 1 ≤ k ≤ p (|y| ≥ 1 থেকে)। এই এক লাইনে প্রতিপক্ষের সব বিভাজন ধরা হলো।
- i বাছাই। i = 2 নিন: xy2z = ap+kbp. k ≥ 1 বলে a-এর সংখ্যা b-এর চেয়ে বেশি, তাই এটি L-এ নেই। i = 0-ও কাজ করে: ap−kbp-এ a কম।
- উপসংহার। প্রতিটি বৈধ বিভাজনের জন্য একটি i পাওয়া গেল যাতে xyiz ∉ L, যা lemma-র শর্ত ৩-এর বিরোধী। তাই অনুমান মিথ্যা: anbn regular নয়। ∎
এই প্রমাণ থেকে একটি non-regular language-এর প্রথম পূর্ণ উদাহরণ পাওয়া গেল। anbn অবশ্য একটি context-free language: S → aSb ∣ ε grammar এটি তৈরি করে (পর্ব ২৫), আর একটি stack-যুক্ত যন্ত্র এটি চেনে (পর্ব ৩২)। অর্থাৎ সসীম স্মৃতির সঙ্গে একটি stack যোগ করলেই সমস্যা মেটে।
নিচের ব্লকটি খেলার প্রতিপক্ষের চাল সব একসঙ্গে পরীক্ষা করে। একটি নির্দিষ্ট p আর s দিলে এটি |xy| ≤ p আর |y| ≥ 1 মানা প্রতিটি বিভাজন তৈরি করে, আর প্রতিটির জন্য দেখে কোন i (0 থেকে 3) দিয়ে string-টিকে L-এর বাইরে পাঠানো যায়। দ্বিতীয় ভাষাটি (ab)∗, যা regular, তাই সেখানে প্রতিপক্ষের জেতার কথা।
import re
def splits(s, p): # every split the adversary may choose
for j in range(1, p + 1): # j = |xy| <= p
for i in range(j): # y = s[i:j], so |y| >= 1
yield s[:i], s[i:j], s[j:]
def challenge(name, in_L, s, p, pumps=range(4)):
assert in_L(s) and len(s) >= p, "s must be in L with |s| >= p"
print(f"{name}: p={p}, s={s}")
lost = 0
for x, y, z in splits(s, p):
out = [i for i in pumps if not in_L(x + y * i + z)]
lost += not out
print(f" x={x or 'ε':4} y={y:5}",
f"out of L for i in {out}" if out else "ADVERSARY WINS")
print(" every split refuted:", lost == 0)
def anbn(w):
return re.fullmatch(r"a*b*", w) is not None and w.count("a") == w.count("b")
challenge("a^n b^n", anbn, "aaaabbbb", 4)
def ab_star(w): # (ab)*, a regular language
return re.fullmatch(r"(ab)*", w) is not None
challenge("(ab)*", ab_star, "abababab", 4)আসল আউটপুট (ব্রাউজারের Python):
a^n b^n: p=4, s=aaaabbbb
x=ε y=a out of L for i in [0, 2, 3]
x=ε y=aa out of L for i in [0, 2, 3]
x=a y=a out of L for i in [0, 2, 3]
x=ε y=aaa out of L for i in [0, 2, 3]
x=a y=aa out of L for i in [0, 2, 3]
x=aa y=a out of L for i in [0, 2, 3]
x=ε y=aaaa out of L for i in [0, 2, 3]
x=a y=aaa out of L for i in [0, 2, 3]
x=aa y=aa out of L for i in [0, 2, 3]
x=aaa y=a out of L for i in [0, 2, 3]
every split refuted: True
(ab)*: p=4, s=abababab
x=ε y=a out of L for i in [0, 2, 3]
x=ε y=ab ADVERSARY WINS
x=a y=b out of L for i in [0, 2, 3]
x=ε y=aba out of L for i in [0, 2, 3]
x=a y=ba ADVERSARY WINS
x=ab y=a out of L for i in [0, 2, 3]
x=ε y=abab ADVERSARY WINS
x=a y=bab out of L for i in [0, 2, 3]
x=ab y=ab ADVERSARY WINS
x=aba y=b out of L for i in [0, 2, 3]
every split refuted: False
p = 4-এ বৈধ বিভাজন ঠিক ১০টি: |xy| = j হলে y-এর শুরু বাছার j-টি উপায়, তাই 1 + 2 + 3 + 4 = 10. anbn-এ প্রতিটি বিভাজনে y শুধু a দিয়ে গড়া, আর i = 0, 2, 3 তিনটিই string-কে বাইরে পাঠায়, ঠিক stepper-এর ধাপ ৪–৫-এর মতো। (ab)∗-এ চারটি বিভাজনে প্রতিপক্ষ জেতেন: y = ab, ba, abab বা x = ab-এর পর ab. যেমন x = a, y = ba, z = babab নিলে xyiz = a(ba)ibabab, যা প্রতিটি i-তে (ab)∗-এর সদস্য। একটি regular language-এ ঠিক এটাই হওয়ার কথা। সতর্কতা: এই ব্লক শুধু একটি p দেখে। প্রমাণ হতে হলে যুক্তিটি সব p-তে খাটতে হয়, যা stepper-এর বীজগণিত করে; কোড কেবল যুক্তিটি ছোট উদাহরণে মিলিয়ে দেখে।
৫ · পরিচিত প্রমাণ — বন্ধনী, an², prime, ww আর palindrome
প্রতিটি প্রমাণের আসল কাজ দুটি সিদ্ধান্তে: কোন s বাছবেন, আর কোন i. ভালো s এমন যে |xy| ≤ p শর্ত y-এর রূপ প্রায় পুরো ঠিক করে দেয়। নিচের প্রতিটি প্রমাণ একই ছকে, আর প্রতিটির যুক্তি scratch-এ p = 1 থেকে 7 পর্যন্ত সব বিভাজনে কোড দিয়ে যাচাই করা হয়েছে।
Σ = {(, )}. s = (p)p নিন। |xy| ≤ p, তাই y = (k, 1 ≤ k ≤ p. i = 0 নিলে (p−k)p, যেখানে “)” বেশি, তাই এটি সুষম নয়। ∎ পর্ব ০১-এর pigeonhole প্রমাণ একই কথা অন্যভাবে বলে; এখানে সেটি lemma-র একটি প্রয়োগ মাত্র।
s = ap² নিন; |s| = p² ≥ p. যেকোনো বিভাজনে y = ak, 1 ≤ k ≤ p. i = 2 নিলে দৈর্ঘ্য p² + k, আর
p² < p² + k ≤ p² + p < p² + 2p + 1 = (p + 1)²
দুটি পরপর পূর্ণবর্গের মাঝে কোনো পূর্ণবর্গ নেই, তাই xy2z ∉ L. ∎ মূল কৌশল: pump করে দৈর্ঘ্য এতটুকু বাড়ানো, যা পরের পূর্ণবর্গে পৌঁছাতে পারে না।
Prime অসীম সংখ্যক, তাই একটি prime q ≥ max(p, 2) আছে; s = aq. y = ak, k ≥ 1. i = q + 1 নিলে দৈর্ঘ্য q + qk = q(1 + k). দুটি গুণনীয়কই ≥ 2, তাই দৈর্ঘ্যটি prime নয়। ∎ লক্ষ করুন, এখানে i নির্ভর করে s-এর ওপর; এটি বৈধ, কারণ i আপনার চাল।
s = apbapb নিন (w = apb). y = ak প্রথম a-খণ্ডের ভেতরে। i = 0-তে ap−kbapb. এতে ঠিক দুটি b; ww রূপের string-এ দুটি b থাকলে প্রতিটি অর্ধেকে একটি করে, তাই string-টি ambamb হতো। এখানে দুই a-খণ্ড p − k ≠ p, তাই ∉ L. ∎
s = apbap. y = ak প্রথম খণ্ডে। i = 2-তে ap+kbap: একটিমাত্র b, তাই palindrome হতে হলে b-এর দুই পাশে সমান a লাগত। p + k ≠ p, তাই ∉ L. ∎
ভুল s বাছলে খেলা হারবেন। ww-এর জন্য s = a2p নিলে এটি ww-তে আছে ঠিকই (w = ap), কিন্তু প্রতিপক্ষ y = aa দেবেন: তখন xyiz = a2p+2(i−1), দৈর্ঘ্য সবসময় জোড়, তাই সবসময় ww-তে। Scratch-এ p = 2 থেকে 5 প্রতিটিতে এমন বিভাজন পাওয়া গেছে। একইভাবে {w : a আর b সমান সংখ্যক}-এর জন্য s = (ab)p নিলে প্রতিপক্ষ y = ab দিয়ে জেতেন, অথচ s = apbp নিলে আপনি জেতেন। ভুল s কিছুই প্রমাণ করে না, অপ্রমাণও করে না; শুধু অন্য s চেষ্টা করতে হয়।
একটি নিয়ম এখান থেকে পাওয়া যায়: এমন s বাছুন, যার প্রথম p চিহ্ন একরকম (যেমন সব a), আর যার “গঠন” ভাঙলে বাইরে যাওয়া সহজ। আর কখনো কখনো closure property সরাসরি pumping-এর চেয়ে সহজ পথ দেয়। যেমন EQ = {w ∈ {a, b}∗ : a আর b সমান সংখ্যক}. EQ regular হলে EQ ∩ a∗b∗ = anbn-ও regular হতো, কারণ দুটি regular language-এর ছেদ regular (product construction, পর্ব ০৮)। কিন্তু anbn regular নয়, তাই EQ-ও নয়। এই closure property-ভিত্তিক কৌশলের পূর্ণ তালিকা পর্ব ১৬-এ।
৬ · সাধারণ ভুল — বিভাজন বেছে নেওয়া, p বসিয়ে দেওয়া, শুধু ওপরে pump
Pumping lemma-র প্রমাণ দেখতে সহজ, তাই ভুলও সহজে ঢোকে। সবচেয়ে বিপজ্জনক ভুলগুলো এমন “প্রমাণ” তৈরি করে, যা একটি regular language-কেও non-regular বলে দেয়। নিচের stepper এমন একটি ভুল প্রমাণ ধাপে ধাপে দেখায়। ভাষাটি EVEN = {w ∈ {a, b}∗ : a-এর সংখ্যা জোড়}, যা স্পষ্টতই regular: দুটি state-এর একটি DFA “এ পর্যন্ত a জোড় না বিজোড়” মনে রাখে।
1দাবি: EVEN non-regular2s = a²ᵖ3“ধরি y = a” ✗4i = 2 ⇒ বিজোড় ⇒ ∉ L5কিন্তু ২-state DFA আছে6প্রতিপক্ষের আসল চাল
| যুক্তি | |
| কে বাছল | |
| ফল |
- দাবি। কেউ লিখলেন: “EVEN regular নয়। প্রমাণ: ধরি EVEN regular, আর p তার pumping length.” শুরুটি নিখুঁত।
- s বাছাই। “s = a2p নিই।” a-এর সংখ্যা 2p, জোড়, তাই s ∈ EVEN আর |s| ≥ p. এই চালও বৈধ, কারণ s বাছা আপনার অধিকার।
- ভুলের জায়গা। “ধরি x = ε, y = a, z = a2p−1.” এখানেই প্রমাণ ভেঙে পড়ে। বিভাজন প্রতিপক্ষের চাল (lemma-তে ∃x, y, z), তাই একটি সুবিধাজনক বিভাজন বেছে নিলে কিছুই প্রমাণ হয় না। দেখাতে হতো সব বৈধ বিভাজনে আপনি জেতেন।
- “উপসংহার”। “i = 2 নিলে a2p+1, বিজোড়, তাই ∉ EVEN; বিরোধ।” হিসাবটি ঠিক, কিন্তু এটি শুধু একটি বিভাজনের বিরুদ্ধে জয়। প্রতিপক্ষ এই বিভাজন দিতেন না।
- বাস্তব। EVEN-এর DFA: q0 (জোড়, accepting) আর q1 (বিজোড়), a পড়লে state বদলায়, b পড়লে একই থাকে। তাই EVEN regular, আর উপরের “প্রমাণ” একটি মিথ্যা সিদ্ধান্তে পৌঁছেছে। ভুল প্রমাণের সবচেয়ে বড় লক্ষণ এটাই।
- প্রতিপক্ষের চাল। DFA-তে ২টি state, তাই প্রতিপক্ষ p = 2 দেন। s = aaaa-এ run q0, q1, q0: অবস্থান 0 আর 2-এ একই state, তাই x = ε, y = aa, z = aa. xyiz-এ a-এর সংখ্যা 2i + 2, সবসময় জোড়: প্রতিটি i-তে ∈ EVEN. খেলা প্রতিপক্ষের।
এই ভুল ছাড়াও আরও কয়েকটি ভুল বারবার দেখা যায়। প্রতিটির পাশে কেন ভুল, সেটি লেখা হলো:
| ভুল | কেন ভুল, আর ঠিক কী |
|---|---|
| বিভাজন নিজে বেছে নেওয়া (“ধরি y = a”) | বিভাজন প্রতিপক্ষের; সব বৈধ বিভাজন সামলাতে হয়, ক্ষেত্র ভাগ করে হলেও |
| p-এর মান বসিয়ে দেওয়া (“ধরি p = 3”) | p প্রতিপক্ষের; যুক্তি সব p-এর জন্য লিখতে হয়। p = 3-এ জেতা মানে শুধু “৩ বা তার কম state-এর কোনো DFA নেই” |
| |s| < p বা s ∉ L নেওয়া | Lemma শুধু L-এর দৈর্ঘ্য ≥ p-এর string সম্পর্কে কথা বলে; অন্য s-এ কোনো প্রতিশ্রুতি নেই |
| শুধু ওপরের দিকে pump (i ≥ 2) | কিছু language-এ শুধু i = 0 কাজ করে; নিচের উদাহরণ দেখুন |
| |xy| ≤ p ভুলে যাওয়া | তখন y b-অংশে বা দুই অংশ জুড়ে থাকতে পারে, ক্ষেত্র অনেক বেড়ে যায়; শর্তটি ব্যবহার করলে প্রমাণ ছোট হয় |
| “শর্ত পূরণ করে, তাই regular” | Lemma প্রয়োজনীয় শর্ত মাত্র; উল্টো দিক মিথ্যা (অংশ ৭) |
শুধু i = 0 কাজ করে এমন উদাহরণ: GT = {aibj : i > j}. s = ap+1bp নিন; y = ak, 1 ≤ k ≤ p. ওপরের দিকে pump করলে a আরও বাড়ে, তাই string GT-তেই থাকে: সেখানে আপনি হারবেন। কিন্তু i = 0-তে ap+1−kbp, আর p + 1 − k ≤ p, তাই a আর b-এর চেয়ে বেশি নয়: ∉ GT. ∎ অনুশীলন ৩-এ এই হিসাবটি কোডে মিলিয়ে দেখবেন।
নিচের JavaScript ব্লকটি খেলাটি সরাসরি খেলায়। প্রতিটি ভাষার জন্য আপনি দুটি function দেন: pickS (p দেখে s বাছে) আর pickI (বিভাজন দেখে i বাছে)। প্রোগ্রামটি প্রতিপক্ষ: p = 1 থেকে 6 প্রতিটিতে সব বৈধ বিভাজন খুঁজে দেখে, এমন কোনো বিভাজন আছে কি না যেখানে আপনার i দিয়ে string L-এর ভেতরেই থাকে। Function দুটি বদলে নিজের কৌশল পরীক্ষা করুন।
// The pumping game. You choose s (for each p) and i; the program is the
// adversary and searches every split x y z with |xy| <= p and |y| >= 1.
const count = (w, c) => [...w].filter(ch => ch === c).length;
const games = [
{ name: "a^n b^n", inL: w => /^a*b*$/.test(w) && count(w, "a") === count(w, "b"),
pickS: p => "a".repeat(p) + "b".repeat(p), // your s
pickI: (x, y, z) => 2 }, // your i
{ name: "#a = #b, s = (ab)^p", inL: w => count(w, "a") === count(w, "b"),
pickS: p => "ab".repeat(p), pickI: (x, y, z) => 0 },
{ name: "even #a (regular)", inL: w => count(w, "a") % 2 === 0,
pickS: p => "a".repeat(2 * p), pickI: (x, y, z) => 2 },
];
for (const g of games) {
const lost = [];
for (let p = 1; p <= 6; p++) {
const s = g.pickS(p);
if (!g.inL(s) || s.length < p) { lost.push(`p=${p}: bad s`); continue; }
let win = null; // adversary looks for a split
for (let j = 1; j <= p && !win; j++)
for (let k = 0; k < j && !win; k++) {
const [x, y, z] = [s.slice(0, k), s.slice(k, j), s.slice(j)];
if (g.inL(x + y.repeat(g.pickI(x, y, z)) + z)) win = `y=${y}`;
}
if (win) lost.push(`p=${p}: adversary ${win}`);
}
console.log(g.name.padEnd(20), lost.length ? "you lose -> " + lost.slice(0, 2).join(", ")
: "you win for p = 1..6");
}আসল আউটপুট (ব্রাউজারের JavaScript):
a^n b^n you win for p = 1..6
#a = #b, s = (ab)^p you lose -> p=2: adversary y=ab, p=3: adversary y=ab
even #a (regular) you lose -> p=2: adversary y=aa, p=3: adversary y=aa
প্রথম সারিতে s = apbp আর i = 2 প্রতিটি p-তে প্রতিটি বিভাজন হারিয়েছে, stepper-এর প্রমাণের মতোই। দ্বিতীয় সারির ভাষা (a আর b সমান সংখ্যক) আসলে non-regular, কিন্তু s = (ab)p একটি দুর্বল চাল: প্রতিপক্ষ y = ab দেন, যা যতবারই যোগ বা বাদ দেওয়া হোক, সংখ্যা সমান থাকে। p = 1-এ অবশ্য s = ab-এর একমাত্র বিভাজন y = a, তাই সেখানে আপনি জেতেন; সেজন্যই তালিকা p = 2 থেকে শুরু। হার এখানে ভাষার দোষ নয়, s-এর দোষ: pickS বদলে p => "a".repeat(p) + "b".repeat(p) দিলে এই সারিও জিতবে। তৃতীয় সারি ভুল প্রমাণের stepper-এর কোড-রূপ: regular ভাষায় প্রতিপক্ষ y = aa দিয়ে সবসময় জেতেন। মনে রাখুন, “p = 1..6-এ জয়” কোনো প্রমাণ নয়; প্রমাণ হলো সব p-এর জন্য লেখা যুক্তি।
৭ · প্রয়োজনীয়, কিন্তু যথেষ্ট নয় — যে language pump করে, তবু regular নয়
Lemma বলে: “regular ⇒ pump করে”। এর উল্টো, “pump করে ⇒ regular”, মিথ্যা। অর্থাৎ lemma একটি প্রয়োজনীয় শর্ত, যথেষ্ট শর্ত নয়। একটি language lemma-র শর্ত পূরণ করলে সেটি regular কি না, সে বিষয়ে lemma কিছুই বলে না। এই মডিউলের মানক উদাহরণটি দেখুন:
অর্থাৎ হয় কোনো a নেই (তখন b আর c যেকোনো সংখ্যক), নয়তো b আর c সমান সংখ্যক। যেমন bbc, ccc, aabbcc, a ∈ Lc, কিন্তু abbc ∉ Lc.
1Lc = {aⁱbʲcᵏ : i = 0 বা j = k}2প্রতিপক্ষ: p = 1, y = প্রথম চিহ্ন3s a দিয়ে শুরু4s b বা c দিয়ে শুরু5Lc ∩ ab∗c∗ = {abʲcʲ}6closure ⇒ Lc non-regular
| উদাহরণ | |
| যুক্তি | |
| ফল |
- ভাষা। Lc-এ দুটি শাখা: a ছাড়া যেকোনো bjck, অথবা a থাকলে b আর c সমান। abbc-এ a আছে কিন্তু b দুটি, c একটি, তাই এটি নেই।
- প্রতিপক্ষের কৌশল। প্রতিপক্ষ p = 1 দেন, আর যেকোনো s-এর জন্য x = ε, y = s-এর প্রথম চিহ্ন। |y| = 1 আর |xy| = 1 ≤ p, তাই বিভাজন বৈধ। দেখাতে হবে, প্রতিটি i-তে xyiz ∈ Lc.
- a দিয়ে শুরু। s-এ a আছে, তাই j = k. Pump শুধু a-এর সংখ্যা বদলায়। i = 0-তে a-এর সংখ্যা এক কমে; শূন্য হলেও string a-হীন শাখায় পড়ে, আর না হলে j = k অটুট। যেমন s = abbcc-এ i = 0 দেয় bbcc, i = 2 দেয় aabbcc: দুটিই Lc-এ।
- b বা c দিয়ে শুরু। তখন s-এ কোনো a নেই (a শুধু শুরুতে আসতে পারে), আর y একটি b বা c. Pump করলেও a আসে না, আর a∗b∗c∗ রূপও ভাঙে না। তাই প্রতিটি i-তে ∈ Lc. অর্থাৎ Lc lemma-র শর্ত পুরো পূরণ করে।
- ছেদ। a b∗c∗ একটি regular language. Lc ∩ ab∗c∗-এ ঠিক একটি a, তাই j = k বাধ্য: {abjcj : j ≥ 0}. Python ব্লক দৈর্ঘ্য 7 পর্যন্ত এটি দেখায়: a, abc, abbcc, abbbccc.
- উপসংহার। {abjcj} pump করে না: s = abpcp; y-তে a থাকলে i = 0 a মুছে দেয়, আর y শুধু b হলে i = 2 b বাড়ায়। Lc regular হলে ছেদটিও regular হতো (closure), তাই Lc regular নয়। ∎
নিচের ব্লক তিনটি দাবি কোড দিয়ে মেলায়: দৈর্ঘ্য 1 থেকে 10-এর Lc-এর প্রতিটি string প্রতিপক্ষের “প্রথম চিহ্ন” কৌশলে pump করে; ab∗c∗-এর সঙ্গে ছেদ ঠিক abjcj; আর s = abpcp-এ মূল ভাষায় প্রতিপক্ষ জেতেন, ছেদে জেতেন না।
import re
from itertools import product
def in_L(w): # a^i b^j c^k with i = 0 or j = k
m = re.fullmatch(r"(a*)(b*)(c*)", w)
return bool(m) and (len(m[1]) == 0 or len(m[2]) == len(m[3]))
# 1) L satisfies the pumping condition with p = 1: x = ε, y = first symbol
checked = failed = 0
for n in range(1, 11):
for t in product("abc", repeat=n):
s = "".join(t)
if not in_L(s): continue
checked += 1
y, z = s[0], s[1:]
if not all(in_L(y * i + z) for i in range(8)): failed += 1
print("strings of L, length 1..10:", checked, " pumping fails:", failed)
# 2) but L ∩ a b* c* = { a b^j c^j }, a language that does not pump
inter = sorted({"".join(t) for n in range(1, 8) for t in product("abc", repeat=n)
if in_L("".join(t)) and re.fullmatch(r"ab*c*", "".join(t))},
key=len)
print("L ∩ ab*c* up to length 7:", inter)
def survivors(lang, s, p): # splits the adversary can still win with
return [(s[:i], s[i:j]) for j in range(1, p + 1) for i in range(j)
if all(lang(s[:i] + s[i:j] * k + s[j:]) for k in range(4))]
one_a = lambda w: in_L(w) and re.fullmatch(r"ab*c*", w) is not None
for p in range(1, 7):
s = "a" + "b" * p + "c" * p
print(f"p={p} s={s}: winning splits in L: {survivors(in_L, s, p)[:1]},",
f"in L ∩ ab*c*: {survivors(one_a, s, p)}")আসল আউটপুট (ব্রাউজারের Python):
strings of L, length 1..10: 95 pumping fails: 0
L ∩ ab*c* up to length 7: ['a', 'abc', 'abbcc', 'abbbccc']
p=1 s=abc: winning splits in L: [('', 'a')], in L ∩ ab*c*: []
p=2 s=abbcc: winning splits in L: [('', 'a')], in L ∩ ab*c*: []
p=3 s=abbbccc: winning splits in L: [('', 'a')], in L ∩ ab*c*: []
p=4 s=abbbbcccc: winning splits in L: [('', 'a')], in L ∩ ab*c*: []
p=5 s=abbbbbccccc: winning splits in L: [('', 'a')], in L ∩ ab*c*: []
p=6 s=abbbbbbcccccc: winning splits in L: [('', 'a')], in L ∩ ab*c*: []
দৈর্ঘ্য 1 থেকে 10-এর Lc-এ ৯৫টি string (a-হীন শাখায় ৬৫টি, a-যুক্ত শাখায় ৩০টি), আর প্রতিটিতে i = 0 থেকে 7 পর্যন্ত pump করা string Lc-এ থেকেছে: একবারও ব্যর্থ নয়। দ্বিতীয় লাইন ছেদের প্রথম চারটি সদস্য দেখায়। শেষ ছয় লাইন মূল কথাটি স্পষ্ট করে: একই s = abpcp-এ মূল ভাষায় প্রতিপক্ষের জয়ের বিভাজন আছে (x = ε, y = a), কারণ a মুছে গেলে string a-হীন শাখায় ঢুকে পড়ে; কিন্তু ছেদের ভাষায় কোনো বিভাজনই টেকে না (খালি তালিকা)। ছেদ নেওয়া “পালানোর পথ” বন্ধ করে দিয়েছে। তবে আবারও: brute force সসীম দৈর্ঘ্য দেখে; সব দৈর্ঘ্যের নিশ্চয়তা দেয় stepper-এর প্রমাণ।
আরও গভীরে: Lemma-কে শক্তিশালী করে “যদি এবং কেবল যদি” করা যায় কি? Jaffe ১৯৭৮ সালে একটি pumping-ধরনের শর্ত দেন, যা regular language-কে ঠিকঠাক চিহ্নিত করে বলে পরিচিত; Ehrenfeucht, Parikh আর Rozenberg ১৯৮১ সালে আরেকটি রূপ দেন, যা block cancellation নামে পরিচিত: string-কে যথেষ্ট খণ্ডে ভাগ করলে কোনো পরপর খণ্ড-গুচ্ছ মুছে ফেলা যায়, আর তাতে কোনো suffix-এর সঙ্গেই ভাষায় থাকা-না-থাকা বদলায় না। এসব শর্তের পেছনের মূল ধারণাটি পর্ব ১৮-এর Myhill–Nerode theorem-এ সবচেয়ে পরিষ্কার: L regular ⇔ “ভবিষ্যৎ দিয়ে আলাদা করা যায় না” সম্পর্কের class সসীম। আর একটি অবাক করা তথ্য: একক-চিহ্নের alphabet-এ (যেমন শুধু a) একটি language regular ⇔ তার দৈর্ঘ্যের সেট ultimately periodic, অর্থাৎ একটি বিন্দুর পর পর্যায়ক্রমিক; তাই an² বা prime দৈর্ঘ্য regular হতে পারে না।
৮ · কোন হাতিয়ার কখন — pumping, closure না Myhill–Nerode
Non-regular প্রমাণের তিনটি প্রধান হাতিয়ার আছে, আর প্রতিটির নিজস্ব জোর। Pumping lemma সবচেয়ে পরিচিত, কিন্তু সবসময় সবচেয়ে সহজ নয়, আর কখনো কাজই করে না (যেমন Lc-এ)।
| হাতিয়ার | কী দেখাতে হয় | কখন সুবিধাজনক | সীমা |
|---|---|---|---|
| Pumping lemma (এই পর্ব) | একটি s, আর প্রতিটি বিভাজনে একটি i | anbn-ধরনের গোনা, একক-চিহ্নের দৈর্ঘ্য-শর্ত (n², prime) | শুধু প্রয়োজনীয় শর্ত; Lc-এর মতো ভাষায় অচল |
| Closure property (পর্ব ১৬) | L থেকে regular operation দিয়ে একটি জানা non-regular ভাষা পাওয়া | EQ ∩ a∗b∗, complement, homomorphism দিয়ে পরিচিত রূপে আনা | আগে থেকে জানা একটি non-regular ভাষা লাগে |
| Myhill–Nerode (পর্ব ১৮) | অসীম সংখ্যক string, যাদের প্রতি জোড়া কোনো suffix আলাদা করে | “কত তথ্য মনে রাখতে হয়” স্পষ্ট হলে: an-এর পর কতটি b লাগবে | কোনো সীমা নেই: শর্তটি প্রয়োজনীয় ও যথেষ্ট |
তৃতীয় সারির ধারণাটি আপনি আগেই দেখেছেন। দুটি distinguishable string কোনো DFA একই state-এ রাখতে পারে না (পর্ব ০৮), আর এমন k-টি string-এর fooling set থাকলে যেকোনো DFA-তে অন্তত k-টি state লাগে (পর্ব ১০)। anbn-এর জন্য a, aa, aaa, … প্রতিটি জোড়া ai, aj (i ≠ j)-কে suffix bi আলাদা করে, তাই অসীম fooling set, আর কোনো সসীম DFA যথেষ্ট নয়। এই যুক্তি প্রায়ই pumping-এর চেয়ে ছোট, আর Lc-এর ক্ষেত্রেও কাজ করে: ab, abb, abbb, … প্রতিটি জোড়াকে cj আলাদা করে।
একটি ব্যবহারিক পরামর্শ: প্রশ্নে “pumping lemma দিয়ে প্রমাণ করুন” বলা থাকলে সেটিই লিখুন। বলা না থাকলে আগে দেখুন, ভাষাটি কোনো পরিচিত non-regular ভাষার সঙ্গে ছেদ বা complement-এ যুক্ত কি না; তারপর ভাবুন, কোন অসীম string-গুচ্ছ যন্ত্রকে আলাদা করে মনে রাখতে হয়। আর ভাষাটি regular কি না সন্দেহ থাকলে (যেমন “01 আর 10 সমান সংখ্যক”, যা পর্ব ১৫-এ regular প্রমাণ হয়েছে), প্রমাণ শুরুর আগে ছোট দৈর্ঘ্যে একটি DFA বানানোর চেষ্টা করুন।
Regular language-এর pumping lemma সাধারণত Michael Rabin আর Dana Scott-এর ১৯৫৯ সালের প্রবন্ধ “Finite Automata and Their Decision Problems”-এর সঙ্গে যুক্ত করা হয়, যেখানে একই পুনরাবৃত্ত-state যুক্তি আছে; এই প্রবন্ধেই NFA আর subset construction-এর ধারণা আসে (পর্ব ১০)। ১৯৬১ সালে Yehoshua Bar-Hillel, Micha Perles আর Eli Shamir context-free language-এর জন্য একটি pumping lemma প্রমাণ করেন (পর্ব ৩৬), আর regular রূপটি সেখান থেকে একটি সরল বিশেষ ক্ষেত্র হিসেবেও পাওয়া যায় বলে উল্লেখ পাওয়া যায়। “Pumping” নামটি পরে পাঠ্যবইয়ে জনপ্রিয় হয়; উৎস নিয়ে সূত্রগুলো পুরোপুরি একমত নয়।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- Pumping lemma বলুন আর প্রমাণ করুন। ∃p ∀s ∃xyz ∀i, শর্ত |y| ≥ 1, |xy| ≤ p; প্রমাণ p = state-সংখ্যা নিয়ে প্রথম p চিহ্নে pigeonhole.
- anbn (বা সুষম বন্ধনী) non-regular প্রমাণ করুন। s = apbp, |xy| ≤ p থেকে y = ak, i = 2 বা 0.
- {an²} বা prime দৈর্ঘ্য non-regular প্রমাণ করুন। দৈর্ঘ্য p² + k দুই পূর্ণবর্গের মাঝে; prime-এ i = q + 1 দিলে দৈর্ঘ্য q(1 + k).
- একটি language pumping lemma-র শর্ত পূরণ করে; সেটি কি regular? বলা যায় না; lemma শুধু প্রয়োজনীয় শর্ত, উদাহরণ {aibjck : i = 0 বা j = k}.
- এই “প্রমাণে” ভুল কোথায়? সাধারণত বিভাজন নিজে বেছে নেওয়া, p-এর মান বসানো, বা |s| ≥ p না মানা।
৯ · AI-এর যুগে pumping lemma
AI assistant-কে “X non-regular প্রমাণ করো” বললে সে প্রায়ই আত্মবিশ্বাসী, সুন্দর গঠনের একটি প্রমাণ দেয়। গঠন সুন্দর হলেই প্রমাণ সঠিক হয় না, আর pumping lemma-র ক্ষেত্রে ভুলগুলো প্রায় সবসময় একই জায়গায়: কে কী বাছে।
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
| “ধরি y = a” বা “y-কে মাঝখানে নিই”: বিভাজন নিজে বেছে নেওয়া | প্রতিটি বাছাইয়ের পাশে লিখুন কে বাছল; বিভাজন হলে সব ক্ষেত্র আছে কি না দেখুন |
| শুধু একটি ক্ষেত্র pump করা, যেমন y শুধু a-অংশে ধরা অথচ s-এর রূপে |xy| ≤ p তা নিশ্চিত করে না | adversary.py-এর মতো কোডে ছোট p-তে সব বিভাজন পরীক্ষা করুন |
| শুধু i = 2 চেষ্টা, যেখানে i = 0 লাগে (যেমন {aibj : i > j}) | i = 0 আর i = 2 দুটিই হাতে হিসাব করুন |
| একটি regular language-কে non-regular “প্রমাণ” করা (যেমন “01 আর 10 সমান সংখ্যক”) | আগে ছোট দৈর্ঘ্যে DFA বানানোর চেষ্টা; brute force-এ সন্দেহজনক ভাষার গঠন দেখুন |
| “Pumping lemma-র শর্ত পূরণ করে, তাই regular” ধরনের সিদ্ধান্ত | Lc-এর মতো পাল্টা-উদাহরণ মনে রাখুন; lemma শুধু প্রয়োজনীয় শর্ত |
| বানানো রেফারেন্স, ভুল সাল বা ভুল নাম (যেমন lemma-কে Kleene-এর নামে চালানো) | Sipser বা Hopcroft–Motwani–Ullman-এ নিজে খুঁজে দেখুন |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: প্রমাণের প্রতিটি বাছাই কার, সেটি স্পষ্ট লিখতে বলা, আর একটি ছোট যাচাই-কোড চাওয়া, যা আপনি নিজে চালাবেন।
(নিজে যাচাই করুন: ভালো উত্তরে s = ap+1bp, y = ak (1 ≤ k ≤ p), আর i = 0 থাকবে। i = 2 কাজ করে না, কারণ a আরও বাড়লে i > j আরও সত্য হয়। অংশ ৬-এর শেষ অনুচ্ছেদ আর অনুশীলন ৩ দেখুন।)
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Pumping lemma শুধু একটি প্রয়োজনীয় শর্ত কেন? এমন কোনো “pumping” শর্ত কি আছে, যা regular language-কে ঠিকঠাক চিহ্নিত করে?
Lemma-র প্রমাণ একটি DFA-র একটিমাত্র ঘটনা ব্যবহার করে: প্রথম p চিহ্নের মধ্যে কোনো state দুবার আসে। এটি regular language-এর একটি খুব দুর্বল ছাপ। একটি non-regular ভাষাও এমন হতে পারে যে তার প্রতিটি লম্বা string-এর শুরুতে কোনো “নিরীহ” অংশ আছে, যা মুছলে বা বাড়ালে ভাষার ভেতরেই থাকে। Lc-এ ঠিক তাই: শুরুর a-গুলো যেকোনো সংখ্যক হতে পারে, কারণ a শূন্য হলে অন্য শাখা দায়িত্ব নেয়। Lemma শুধু শুরুর দিকের একটি চক্র দেখে; ভাষার “আসল জটিলতা” (b আর c সমান) অনেক পরে, যেখানে lemma তাকায়ই না।
শর্তটিকে শক্তিশালী করার দুটি পরিচিত পথ আছে। প্রথম, শর্তটি string-এর যেকোনো জায়গায় প্রয়োগ করা: যেকোনো p-দৈর্ঘ্যের খণ্ডের ভেতরে একটি pump-যোগ্য অংশ থাকতে হবে। এটি Lc-কে ধরে ফেলে, কারণ b-অংশের ভেতরে pump করলে j = k ভাঙে। কিন্তু এটিও সব non-regular ভাষা ধরে না। দ্বিতীয়, Jaffe ১৯৭৮ সালে এমন একটি শর্ত দেন বলে পরিচিত, যেখানে pump করার পর string শুধু ভাষায় থাকলেই চলে না, বরং যেকোনো suffix জুড়ে দিলেও ভাষায় থাকা-না-থাকার আচরণ একই থাকতে হয়। Ehrenfeucht, Parikh ও Rozenberg ১৯৮১ সালে খণ্ড (block) মুছে ফেলার ভিত্তিতে আরেকটি শর্ত দেন। এই রূপগুলো প্রয়োজনীয় ও যথেষ্ট দুটিই বলে পরিচিত, কিন্তু ব্যবহার করা কঠিন।
লক্ষ করুন, “যেকোনো suffix জুড়ে আচরণ একই” কথাটিই Myhill–Nerode-এর মূল ধারণা: দুটি string সমতুল্য, যদি কোনো ভবিষ্যৎ তাদের আলাদা করতে না পারে। Myhill (১৯৫৭) আর Nerode (১৯৫৮)-এর এই উপপাদ্য সরাসরি বলে, L regular ⇔ এমন সমতুল্য-শ্রেণি সসীম। তাই পূর্ণ চিহ্নিতকরণ চাইলে pumping-এর জটিল রূপের চেয়ে পর্ব ১৮-এর পথ সাধারণত পরিষ্কার।
মূল উপলব্ধি: Pumping lemma regular language-এর শুধু একটি দিক ধরে: শুরুর দিকের একটি চক্র। পূর্ণ চিহ্নিতকরণের জন্য “ভবিষ্যৎ দিয়ে আলাদা করা যায় কি না” প্রশ্নটি লাগে, যা Myhill–Nerode সরাসরি দেয়।
প্র ০২Non-regular প্রমাণকে “প্রতিপক্ষের খেলা” ভাবা কেন এত কার্যকর? Quantifier-এর পালাক্রম আর খেলার মধ্যে সম্পর্কটি কী?
গণিতে ∃ আর ∀ পালাক্রমে এলে মানুষের মাথা সহজেই গুলিয়ে যায়। “∃p ∀s ∃xyz ∀i” পড়ে কোন অংশ আপনি ঠিক করবেন আর কোনটি আপনার হাতে নেই, তা তাৎক্ষণিক বোঝা কঠিন। খেলার রূপে কিন্তু নিয়ম স্বাভাবিক: ∃ মানে “যে বলছে সত্য, সে বাছে”, ∀ মানে “তার বিরোধী বাছে”। একটি বাক্য সত্য হওয়া মানে ∃-খেলোয়াড়ের একটি জয়ী কৌশল আছে। যুক্তিবিদ্যায় এই ধারণাকে game semantics বলা হয়; Jaakko Hintikka-র মতো যুক্তিবিদরা এটি নিয়ে বিস্তারিত কাজ করেছেন বলে পরিচিত।
Non-regular প্রমাণে আপনি অস্বীকারের পক্ষে খেলছেন। তাই আপনার চাল s আর i, আর প্রতিপক্ষের চাল p আর বিভাজন। খেলার ভাষায় সবচেয়ে সাধারণ ভুলটি হাস্যকরভাবে স্পষ্ট হয়ে যায়: “ধরি y = a” মানে প্রতিপক্ষের হয়ে চাল দেওয়া, যেন দাবা খেলায় নিজেই প্রতিপক্ষের ঘুঁটি নিজের সুবিধামতো সরানো। অংশ ৬-এর EVEN-এর উদাহরণে এভাবে একটি regular ভাষাও “non-regular” হয়ে গিয়েছিল।
খেলার আরেকটি সুবিধা হলো কৌশলের ধারণা। আপনার s প্রতিপক্ষের p-এর ওপর নির্ভর করতে পারে, আর i বিভাজনের ওপর; কিন্তু উল্টো নয়। তাই s = apbp লেখা বৈধ, কিন্তু “s = a5b5” লিখে শুরু করা অবৈধ, কারণ তখন প্রতিপক্ষ p = 20 দিয়ে আপনার s-কে ছোট করে দেবেন। কোডেও ঠিক এটি দেখা যায়: pumping_game.js-এ pickS একটি function, যা p নেয়। এই ধারণা পরে অনেক জায়গায় ফিরে আসবে: CFL-এর pumping lemma (পর্ব ৩৬), আর algorithm-এর lower bound প্রমাণে adversary argument, যেখানে প্রতিপক্ষ input লুকিয়ে রেখে algorithm-কে সবচেয়ে খারাপ উত্তর দেয়।
মূল উপলব্ধি: প্রতিটি quantifier একটি চাল, আর ∃/∀ বলে কে চাল দেবে। প্রমাণকে খেলা হিসেবে লিখলে “কার বাছাই” প্রশ্নটি প্রতিটি লাইনে চোখে পড়ে, আর সবচেয়ে সাধারণ ভুলটি আর হয় না।
প্র ০৩বাস্তবের regex engine দিয়ে কি সুষম বন্ধনী মেলানো যায়? তাহলে কি pumping lemma বাস্তবে অচল?
Formal regular expression, অর্থাৎ ∅, ε, চিহ্ন, ∪, concatenation আর star দিয়ে গড়া সূত্র, সুষম বন্ধনী কখনো বর্ণনা করতে পারে না: Kleene-এর উপপাদ্য (পর্ব ১৫) অনুযায়ী প্রতিটি regex-এর language regular, আর BAL non-regular. এটি গাণিতিক নিশ্চয়তা, কোনো engine-এর দুর্বলতা নয়।
কিন্তু বাস্তবের অনেক engine formal regex-এর চেয়ে বেশি কিছু দেয়। Backreference (যেমন (a*)b\1) আগে মেলানো অংশ মনে রাখে, যা গণিতের অর্থে regular নয়; কিছু engine-এ (যেমন PCRE ধারার কিছু engine) recursion আছে, আর .NET-এর “balancing group” নামের সুবিধা দিয়েও nested বন্ধনী মেলানো যায় বলে পরিচিত। এসব সুবিধা আসলে regex-কে একটি stack-যুক্ত বা আরও শক্তিশালী যন্ত্রে বদলে দেয়, আর দাম হিসেবে আসে অনিশ্চিত সময়: backtracking engine-এ কিছু pattern-এ input-এর দৈর্ঘ্যের সঙ্গে সময় ঘাতের হারে বাড়ে। এর নাম ReDoS, আর এটি পর্ব ২১-এর বিষয়।
তাই pumping lemma বাস্তবে অচল নয়, বরং একটি নকশা-নির্দেশক। বাজারঘরের order query ভাষার জন্য কেউ “সব কাজ এক regex-এ” প্রস্তাব দিলে lemma বলে দেয়, formal regex বা DFA-ভিত্তিক দ্রুত engine (যেমন RE2-ধরনের, যা নিশ্চিত রৈখিক সময় দেয়) দিয়ে এটি অসম্ভব। ঠিক সমাধান হলো একটি parser: একটি context-free grammar (পর্ব ২৫) আর তার জন্য LL বা LR parser (পর্ব ৩৮–৩৯)। Lexer (পর্ব ২২) token আলাদা করে, কারণ token-এর গঠন regular; parser বন্ধনী আর nesting সামলায়, কারণ সেগুলো regular নয়। Compiler-এর এই দুই স্তরের বিভাজন আসলে Chomsky hierarchy-র একটি সীমারেখা মেনে চলে।
মূল উপলব্ধি: Lemma বলে কোন কাজ সসীম স্মৃতিতে অসম্ভব। বাস্তবের engine সেই সীমা পেরোতে বাড়তি স্মৃতি যোগ করে, কিন্তু তখন তা আর regular নয়, আর গতি ও নিশ্চয়তার দাম দিতে হয়; nested গঠনের জন্য parser-ই ঠিক হাতিয়ার।
প্র ০৪একক-চিহ্নের alphabet-এ (শুধু a) কোন language regular? an² আর prime দৈর্ঘ্যের প্রমাণ থেকে কোন সাধারণ নিয়ম বেরিয়ে আসে?
Σ = {a} হলে একটি language আসলে একটি সংখ্যার সেট: কোন কোন দৈর্ঘ্য অনুমোদিত। এমন একটি DFA-র গঠন খুব সরল। প্রতিটি state-এর একটিই বের-হওয়া তীর, তাই q0 থেকে শুরু করে একটি “লেজ” আর তারপর একটি “চক্র”, অনেকটা ইংরেজি অক্ষর ρ-এর মতো। লেজের দৈর্ঘ্য t আর চক্রের দৈর্ঘ্য c হলে, t-এর পর দৈর্ঘ্য n গৃহীত কি না, তা শুধু n mod c-এর ওপর নির্ভর করে। ফলে প্রতিটি unary regular language-এর দৈর্ঘ্যের সেট ultimately periodic: একটি বিন্দুর পর প্যাটার্ন একই ছন্দে ফিরে আসে। উল্টো দিকও সত্য: যেকোনো ultimately periodic সেটের জন্য এমন লেজ-চক্রের DFA বানানো যায়।
এই চিত্রে an² আর prime-এর প্রমাণ সহজ হয়ে যায়। পূর্ণবর্গের মধ্যে ফাঁক বাড়তেই থাকে, (n + 1)² − n² = 2n + 1, তাই কোনো নির্দিষ্ট পর্যায়ে তারা ফিরে আসতে পারে না। Prime-এর ক্ষেত্রে, যদি একটি বিন্দুর পর পর্যায় c থাকত, তবে একটি বড় prime q-এর পর q + c, q + 2c, …, q + qc সবও prime হতো; কিন্তু q + qc = q(1 + c) prime নয়। অংশ ৫-এ i = q + 1 বাছাইয়ের পেছনে ঠিক এই যুক্তি। একই কারণে a2n (দৈর্ঘ্য 2-এর ঘাত) বা Fibonacci দৈর্ঘ্যও regular নয়।
এই ক্ষেত্রটি গবেষণাতেও গুরুত্বপূর্ণ। Unary NFA-র একটি সাধারণ রূপ, যা Chrobak নামের সঙ্গে যুক্ত (১৯৮৬ সালের দিকে), দেখায় যে unary NFA-কে একটি লেজ আর কয়েকটি সমান্তরাল চক্রে সাজানো যায়। এখান থেকে জানা যায়, unary NFA থেকে DFA-তে গেলে state-এর বিস্ফোরণ সাধারণ 2n-এর চেয়ে কম, তবু polynomial-এর চেয়ে দ্রুত হতে পারে। সংখ্যাতত্ত্ব আর automata এখানে সরাসরি মেলে।
মূল উপলব্ধি: একক চিহ্নে DFA মানে একটি লেজ আর একটি চক্র, তাই unary regular language ঠিক সেগুলো, যাদের দৈর্ঘ্য-সেট শেষমেশ পর্যায়ক্রমিক। পূর্ণবর্গ, prime, 2-এর ঘাত, কোনোটিই এমন নয়।
প্র ০৫Pumping lemma-র ইতিহাস কী, আর regular ও context-free রূপের সম্পর্ক কোথায়? কেন একই ধারণা দুই স্তরে আসে?
১৯৫০-এর দশকের শেষে automata তত্ত্ব দ্রুত গড়ে উঠছিল। Rabin আর Scott-এর ১৯৫৯ সালের প্রবন্ধে NFA, subset construction আর finite automaton-এর decision problem-এর সঙ্গে একটি পুনরাবৃত্ত-state যুক্তিও আছে, যা আজকের regular pumping lemma-র মূল; এই কাজের জন্য তাঁরা পরে ১৯৭৬ সালের Turing Award পান। ১৯৬১ সালে Bar-Hillel, Perles আর Shamir context-free grammar-এর বিস্তৃত বিশ্লেষণ প্রকাশ করেন, যেখানে context-free language-এর জন্য একটি pumping lemma আছে। দুটি lemma-র মধ্যে কোনটি কার অনুপ্রেরণা, আর “pumping” নামটি কে প্রথম ব্যবহার করেন, সে বিষয়ে সূত্রগুলো পুরোপুরি একমত নয়; তাই নির্দিষ্ট দাবি এড়িয়ে চলা ভালো।
দুই রূপের গঠন একই নকশা মানে। Regular রূপে সসীম state-এর ওপর pigeonhole: একটি পথে state দুবার এলে চক্র, আর চক্র একটি অংশ y. Context-free রূপে সসীম variable-এর ওপর pigeonhole: একটি parse tree-র লম্বা পথে কোনো variable দুবার এলে সেই উপ-গাছ নিজের ভেতরে বসানো যায়, আর তাতে দুটি অংশ v আর y একসঙ্গে pump হয়: uvixyiz. শর্তগুলোও সমান্তরাল: |vy| ≥ 1 (regular-এর |y| ≥ 1) আর |vxy| ≤ p (regular-এর |xy| ≤ p).
দুটি pump একসঙ্গে চলে বলেই anbn context-free: v = a আর y = b একসঙ্গে বাড়ালে সংখ্যা সমান থাকে। কিন্তু anbncn-এ তিনটি সংখ্যা মেলাতে হয়, আর দুটি pump-এ সেটি সম্ভব নয়: এটি context-free নয় (পর্ব ৩৬)। অর্থাৎ যন্ত্রে যত বেশি গঠন, তত জটিল pump সে সহ্য করতে পারে। একই নকশা Chomsky hierarchy-র প্রতিটি স্তরের সীমা বুঝতে সাহায্য করে, যদিও decidable স্তরে গিয়ে pumping-এর জায়গা নেয় diagonalization (পর্ব ৫১)।
মূল উপলব্ধি: দুই pumping lemma একই ধারণা দুই যন্ত্রে: সসীম উপাদানের ওপর pigeonhole থেকে পুনরাবৃত্তি, আর পুনরাবৃত্তি থেকে pump. Regular-এ একটি চক্র, context-free-এ একটি নিজের-ভেতরে-বসা উপ-গাছ।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। adversary.py ব্লকে নিজের ভাষা আর s বসিয়ে উত্তরও যাচাই করতে পারেন।
-
নকশা ও বিভাজন: Σ = {0, 1}-এর ওপর L = {w : w-এ 1-এর সংখ্যা ৩ দিয়ে বিভাজ্য}. (ক) L-এর একটি DFA নকশা করুন। (খ) প্রমাণের p কত? (গ) s = 10101-এর জন্য প্রমাণের পদ্ধতিতে x, y, z বের করুন আর দেখান, প্রতিটি i-তে xyiz ∈ L.
(ক) তিনটি state: q0 (এ পর্যন্ত 1-এর সংখ্যা mod 3 = 0, শুরু ও accepting), q1 (= 1), q2 (= 2). 0 পড়লে একই state; 1 পড়লে q0 → q1 → q2 → q0. ঠিকতা: invariant “state = এ পর্যন্ত 1-এর সংখ্যা mod 3”, |w|-এর ওপর induction-এ (পর্ব ০৪)।
(খ) p = state-সংখ্যা = 3.
(গ) s = 10101-এ তিনটি 1, তাই s ∈ L, |s| = 5 ≥ 3. Run: r0 = q0, 1 পড়ে r1 = q1, 0 পড়ে r2 = q1. প্রথম পুনরাবৃত্তি r1 = r2, তাই x = 1, y = 0, z = 101. |y| = 1, |xy| = 2 ≤ 3. xyiz = 10i101: 0 যোগ বা বাদে 1-এর সংখ্যা বদলায় না, সবসময় তিনটি, তাই প্রতিটি i-তে ∈ L. Scratch-এ একই কোডে এই বিভাজন এসেছে, আর i = 0 থেকে 4 সবগুলো গৃহীত।
-
প্রমাণ (দুই পথে): NEQ = {0n1m : n ≠ m} regular নয়, প্রমাণ করুন। (ক) closure property দিয়ে। (খ) সরাসরি pumping lemma দিয়ে; ইঙ্গিত: s = 0p1p+p!.
(ক) NEQ regular ধরুন। Regular language complement-এ বদ্ধ, তাই NEQ-এর complement regular, আর 0∗1∗-এর সঙ্গে ছেদও regular. কিন্তু complement ∩ 0∗1∗ = {0n1n}, যা অংশ ৪-এর প্রমাণে (a, b-এর জায়গায় 0, 1) non-regular. বিরোধ, তাই NEQ regular নয়। ∎ — complement আর ∩-এর closure
(খ) s = 0p1p+p! ∈ NEQ (p! ≥ 1 বলে n ≠ m), |s| ≥ p. |xy| ≤ p, তাই y = 0k, 1 ≤ k ≤ p, আর k দিয়ে p! বিভাজ্য। i = 1 + p!/k নিন: 0-এর সংখ্যা p + (i − 1)k = p + p!, যা 1-এর সংখ্যার সমান। তাই xyiz ∉ NEQ. ∎ সরাসরি পথে কেন এমন অদ্ভুত s লাগে, তা লক্ষ করুন: সহজ s = 0p1p+1 নিলে প্রতিপক্ষ y = 00 দিয়ে সমতা এড়াতে পারেন। Closure-এর পথ এখানে অনেক ছোট। Scratch-এ p = 1 থেকে 6 পর্যন্ত (খ)-এর প্রতিটি বিভাজন কোডে যাচাই করা হয়েছে।
-
Output অনুমান: GT = {aibj : i > j}. adversary.py-এর
challengefunction-এ s = aaaabbb (a4b3) আর p = 3 দিন। (ক)pumps=range(1, 4)দিলে (অর্থাৎ শুধু i = 1, 2, 3) কয়টি বিভাজনে “ADVERSARY WINS” আসবে? (খ) ডিফল্টrange(4)-এ (i = 0 সহ)?p = 3-এ বৈধ বিভাজন 1 + 2 + 3 = 6টি, আর প্রতিটিতে y = ak, 1 ≤ k ≤ 3 (প্রথম তিন চিহ্ন সব a).
(ক) ছয়টিতেই “ADVERSARY WINS”: i ≥ 1-এ a-এর সংখ্যা 4 + (i − 1)k ≥ 4 > 3, তাই string GT-তেই থাকে। শুধু ওপরে pump করলে আপনি একটি বিভাজনও হারাতে পারেন না।
(খ) একটিও নয়: i = 0-তে a-এর সংখ্যা 4 − k ≤ 3, যা b-এর সংখ্যার চেয়ে বেশি নয়, তাই ∉ GT; শেষ লাইনে “every split refuted: True”. Scratch-এ চালিয়ে ঠিক এই দুই ফল এসেছে (৬টি টিকে যায়, তারপর ০টি)।
-
Regular না non-regular? প্রতিটির জন্য হয় একটি DFA/regex দিন, নয়তো non-regular প্রমাণ করুন: (ক) {anbm : n, m ≥ 0}; (খ) {w ∈ {0, 1}∗ : 01 আর 10 substring সমান সংখ্যকবার}; (গ) {anbn : 0 ≤ n ≤ 100}; (ঘ) {a2n : n ≥ 0}.
(ক) Regular: regex a∗b∗. কোনো গোনা নেই, শুধু “b-এর পর a নেই”।
(খ) Regular, যদিও শুনতে গোনার মতো: এটি ঠিক “ফাঁকা, অথবা প্রথম আর শেষ চিহ্ন সমান” (পর্ব ১৫-এর ৫-state DFA). Scratch-এ দৈর্ঘ্য 12 পর্যন্ত সব string-এ দুই সংজ্ঞা মিলেছে।
(গ) Regular, কারণ সসীম (১০১টি string): প্রতিটি সসীম language regular. এখানে pumping lemma-র শর্ত ফাঁকা অর্থে সত্য, কারণ p = 201 নিলে দৈর্ঘ্য ≥ p-এর কোনো সদস্যই নেই।
(ঘ) Non-regular. প্রমাণ: p দেওয়া থাকলে একটি m নিন যাতে 2m > p, আর s = a2m. y = ak, 1 ≤ k ≤ p < 2m. i = 2-তে দৈর্ঘ্য 2m + k, আর 2m < 2m + k < 2m+1, তাই 2-এর ঘাত নয়: ∉ L. ∎ সতর্কতা: শুধু 2m ≥ p নিলে k = p = 2m হতে পারে, তখন দৈর্ঘ্য 2m+1, একটি ঘাত; তাই কঠোর অসমতা লাগে। Scratch-এ p = 1 থেকে 39 পর্যন্ত সব বিভাজনে যাচাই করা হয়েছে।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমPumping lemma দিয়ে একটি language non-regular প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- বিরোধের জন্য L regular ধরে lemma-র অজানা pumping length p নেওয়া
- p দিয়ে লেখা একটি s ∈ L বাছা, যাতে |s| ≥ p
- |y| ≥ 1 আর |xy| ≤ p মানা যেকোনো বিভাজন s = xyz নিয়ে y-এর সাধারণ রূপ বের করা
- প্রতিটি ক্ষেত্রে একটি i দেখানো, যাতে xyiz ∉ L
- Lemma-র শর্ত ৩-এর বিরোধ থেকে সিদ্ধান্ত: L regular নয়
Regular language-এর pumping lemma-তে quantifier-গুলোর সঠিক ক্রম কোনটি (p pumping length, s ∈ L আর |s| ≥ p, s = xyz শর্তসহ, i ≥ 0)?
- ∀s ∃p ∃xyz ∀i
- ∃p ∀s ∃xyz ∀i
- ∀p ∃s ∀xyz ∃i
- ∃p ∀s ∀xyz ∀i
একটি non-regular প্রমাণে কোন দুটি জিনিস প্রমাণকারী নিজে বেছে নিতে পারেন?
- p আর বিভাজন x, y, z
- s আর বিভাজন x, y, z
- s আর i
- p আর i
Σ = {a, b}-এর ওপর GT = {aibj : i > j}-এর জন্য s = ap+1bp নেওয়া হলো, আর |xy| ≤ p থেকে y = ak (1 ≤ k ≤ p). কোন i দিয়ে xyiz সবসময় GT-এর বাইরে যায়?
- i = 0
- i = 1
- i = 2
- যেকোনো i ≥ 2
একটি language L pumping lemma-র শর্ত পূরণ করে (একটি p আছে যাতে প্রতিটি লম্বা s pump করে)। L সম্পর্কে কী বলা যায়?
- L অবশ্যই regular
- L অবশ্যই non-regular
- L অবশ্যই context-free
- শুধু এ থেকে L regular কি না বলা যায় না
{an² : n ≥ 0}-এর প্রমাণে s = ap² আর y = ak (1 ≤ k ≤ p). i = 2-তে দৈর্ঘ্য p² + k কেন পূর্ণবর্গ নয়?
- কারণ p² + k সবসময় বিজোড়
- কারণ k = 1, আর p² + 1 কখনো পূর্ণবর্গ নয়
- কারণ দৈর্ঘ্যটি p² আর (p + 1)²-এর কঠোরভাবে মাঝখানে
- কারণ k একটি prime সংখ্যা
একজন লিখলেন: “EVEN = {w ∈ {a, b}∗ : a-এর সংখ্যা জোড়} regular নয়। s = a2p, ধরি y = a; i = 2 দিলে a বিজোড়, বিরোধ।” এই যুক্তি সম্পর্কে কোনটি ঠিক?
- ভুল, কারণ s ∉ EVEN
- ভুল, কারণ বিভাজন বাছার অধিকার প্রমাণকারীর নেই; EVEN আসলে regular
- ঠিক, EVEN non-regular
- ঠিক, তবে i = 0 নিলে আরও ভালো হতো
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- L regular ⇒ ∃p ≥ 1, যাতে L-এর প্রতিটি s (|s| ≥ p) = xyz, |y| ≥ 1, |xy| ≤ p, আর প্রতিটি i ≥ 0-এ xyiz ∈ L.
- প্রমাণ: p = DFA-র state-সংখ্যা; প্রথম p চিহ্নের p + 1টি অবস্থানে pigeonhole দিয়ে একটি state দুবার, মাঝের অংশ y একটি চক্র।
- খেলা: প্রতিপক্ষ p আর বিভাজন বাছেন, আপনি s আর i. প্রতিটি বৈধ বিভাজনে একটি i দেখাতে হয়; বিভাজন বা p নিজে বসালে প্রমাণ হয় না।
- কৌশল: এমন s, যার প্রথম p চিহ্ন একরকম (apbp, apbapb); i = 0 ভুলবেন না (aibj, i > j).
- Lemma শুধু প্রয়োজনীয় শর্ত: {aibjck : i = 0 বা j = k} pump করে, তবু non-regular; তখন closure বা Myhill–Nerode.
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ০৪ · Theory of Computation-এর প্রমাণ — string-এর ওপর induction, construction আর diagonalizationফিরে দেখুনPigeonhole দিয়ে DFA-র পুনরাবৃত্ত state, যার ওপর এই পর্বের প্রমাণ দাঁড়িয়ে।
- পর্ব ১৮ · Myhill–Nerode theorem — equivalence class দিয়ে regularityপরের পর্বRegularity-র পূর্ণ চিহ্নিতকরণ, যা pumping lemma-র সীমা পেরিয়ে যায়।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ১৮ Myhill–Nerode theorem.
- পর্ব ০১ · গণনার তত্ত্বের মানচিত্র — কী গণনা করা যায়, কত দ্রুতপটভূমিসুষম বন্ধনী যে কোনো DFA চেনে না, তার প্রথম pigeonhole প্রমাণ।
- পর্ব ০৮ · DFA নকশা — product construction, complement আর গণনার কৌশলপটভূমিClosure-ভিত্তিক non-regular প্রমাণে লাগা product construction আর complement.
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৩২ — Pigeonhole principleপাশের ট্র্যাককবুতরের খোপের নীতি আর তার সাধারণ রূপগুলো, গণিতের দিক থেকে।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৪ — Finite automaton আর regular expression-এর পরিচয়পটভূমিPumping lemma-র একটি ছোট প্রথম পরিচয়।