সরাসরি পর্বে যান
পর্ব ৩৭ · ৮৫-এর মধ্যে · মডিউল ৬

CFL-এর closure আর decision property — কী decidable, কী নয়

Closure and Decision Properties of Context-Free Languages — Grammar Constructions, PDA × DFA, Non-Closure, Emptiness, Finiteness and Undecidable Questions

Taught in Bangla, this lesson shows context-free languages are closed under union, concatenation, star, reversal and homomorphisms by simple grammar edits, and under intersection with a regular language with a PDA × DFA product. It proves closure fails for intersection and complement, uses closure to prove languages non-context-free, decides membership, emptiness and finiteness with in-page Python (Pyodide) checks, and lists undecidable questions such as universality, equivalence and ambiguity of grammars.

এই পর্বে যা শিখবেন

  • CFL-এর closure-তালিকা, প্রতিটির grammar বা PDA নির্মাণ আর প্রমাণ
  • PDA × DFA product নির্মাণ, আর কেন PDA × PDA একইভাবে চলে না
  • ∩ আর complement-এ closure না থাকার প্রমাণ, আর closure দিয়ে non-CFL প্রমাণের কৌশল
  • Emptiness আর finiteness-এর algorithm, সঠিকতার প্রমাণ আর Python-এ witness-সহ চালানো
  • কোন প্রশ্ন undecidable, কোন পর্বে তার প্রমাণ, আর বাস্তবের parser-কাজে এর মানে

১ · একই প্রশ্ন, নতুন শ্রেণি — CFL-এর closure

বাজারঘরের অর্ডার-query ভাষার জন্য দলের হাতে এখন দুটি grammar-ভিত্তিক checker আছে। একটি দেখে বন্ধনী সুষম কি না; আরেকটি দেখে AND আর OR ঠিকভাবে বসেছে কি না। নতুন নিয়ম এল: “query দুটি শর্তই মানবে, আর মোট দৈর্ঘ্য ২০০ অক্ষরের বেশি হবে না”। প্রশ্ন দুটি। প্রথমত, দুটি checker জুড়ে কি আবার একটি grammar বা PDA পাওয়া যায়? দ্বিতীয়ত, কেউ grammar একটু বদলালে কোনো program কি নিশ্চিত করে বলতে পারে যে language বদলায়নি?

প্রথম প্রশ্নটি closure property-র, দ্বিতীয়টি decision property-র। পর্ব ১৬ আর পর্ব ২০-এ regular language-এর জন্য দুটি প্রশ্নেরই উত্তর ছিল প্রায় সবসময় “হ্যাঁ”। Context-free language-এ ছবিটি মিশ্র, আর এই মিশ্রণই এই পর্বের মূল শিক্ষা।

রেলের টিকিট কাউন্টারের কথা ভাবুন। একজন কর্মী একটি খাতা (stack) রেখে যাত্রীর সারি সামলাতে পারেন। তাঁর সঙ্গে একটি ছোট নিয়মের কার্ড (DFA) জুড়ে দিলে কাজ চলে, কারণ কার্ডে কোনো খাতা নেই। কিন্তু দুজন কর্মীর দুটি খাতা একটিতে মেলাতে গেলে হিসাব জট পাকায়: দুজনেরই খাতার ওপরের পাতা আলাদা জায়গায়। CFL-এর closure-এর গল্পও ঠিক এটি।

এক নজরে পুরো ছবি। শেষ কলামে deterministic CFL (DCFL), যা পর্ব ৩৫-এর বিষয়; এখানে শুধু তুলনার জন্য।

OperationRegularCFLDCFL
Union L1 ∪ L2হ্যাঁহ্যাঁ (অংশ ২)না
Concatenation, starহ্যাঁহ্যাঁ (অংশ ২)না
Reversal, homomorphismহ্যাঁহ্যাঁ (অংশ ২)না
Inverse homomorphismহ্যাঁহ্যাঁ (অংশ ৩)হ্যাঁ
∩ regular languageহ্যাঁহ্যাঁ (অংশ ৩)হ্যাঁ
∩ (দুটি একই শ্রেণির)হ্যাঁনা (অংশ ৪)না
Complementহ্যাঁনা (অংশ ৪)হ্যাঁ

এই পর্বের notation: CFG G = (V, Σ, R, S); বড় হাতের অক্ষর variable, ছোট হাতের অক্ষর terminal; “A → α ∣ β” মানে দুটি নিয়ম। PDA P = (Q, Σ, Γ, δ, q0, F), transition “a, x → y” (a পড়ে, x তুলে, y রাখে), configuration (q, w, γ)-এ stack-এর ওপর বাঁয়ে, আর গ্রহণ final state দিয়ে, পর্ব ৩২-এর মতো। DFA D = (Q′, Σ, δ′, s0, F′). PDA আর CFG যে একই শ্রেণি চেনে, সেটি পর্ব ৩৪-এর উপপাদ্য; তাই প্রতিটি প্রমাণে যেটি সুবিধার, সেটি নেওয়া যায়।

২ · Grammar দিয়ে closure — union, concatenation, star, reversal, homomorphism

পর্ব ২৫-এ union, concatenation আর star-এর grammar দেখেছেন। এখানে পাঁচটি নির্মাণ একসঙ্গে, প্রতিটির ছোট প্রমাণসহ। ধরুন G1 = (V1, Σ, R1, S1) আর G2 = (V2, Σ, R2, S2), আর V1 ∩ V2 = ∅. দরকার হলে আগে একটির variable-এর নাম বদলে নিন; নইলে দুই grammar-এর নিয়ম একে অন্যের variable-এ ঢুকে পড়ে ভুল language দেয়।

উপপাদ্য ২.১ (regular operation)

নতুন start S নিয়ে, R1 ∪ R2-এর সঙ্গে যোগ করুন:
Union: S → S1 ∣ S2  ·  Concatenation: S → S1S2  ·  Star (শুধু G1): S → SS1 ∣ ε.
তিনটি grammar যথাক্রমে L(G1) ∪ L(G2), L(G1)L(G2) আর L(G1)∗ তৈরি করে।

প্রমাণের রূপরেখা (concatenation): S থেকে প্রথম ধাপ বাধ্যতামূলকভাবে S ⇒ S1S2. V1 আর V2 আলাদা বলে S1-এর বংশধর আর S2-এর বংশধর কখনো মেশে না, তাই প্রতিটি derivation দুটি স্বাধীন derivation-এ ভাগ হয়: S1 ⇒∗ u আর S2 ⇒∗ v, ফল uv. উল্টো দিকে u ∈ L(G1) আর v ∈ L(G2)-এর derivation দুটি পাশাপাশি বসালেই S ⇒∗ uv. Union আর star-এর যুক্তিও একই ধাঁচের; star-এ k বার S → SS1 খাটালে ঠিক k-টি টুকরো আসে। ∎

উপপাদ্য ২.২ (reversal আর homomorphism)

(ক) G-এর প্রতিটি নিয়ম A → X1⋯Xk-কে A → Xk⋯X1 বানালে নতুন grammar L(G)R তৈরি করে।
(খ) Homomorphism h : Σ → Γ∗ হলে প্রতিটি নিয়মের ডান দিকে প্রতিটি terminal a-এর জায়গায় h(a) বসালে নতুন grammar h(L(G)) তৈরি করে।

প্রমাণ (ক), derivation-এর দৈর্ঘ্যের ওপর induction. দাবি: G-তে A ⇒∗ w ঠিক তখন, যখন নতুন grammar GR-এ A ⇒∗ wR.

  1. ভিত্তি: এক ধাপের derivation A → w (w-এ শুধু terminal), আর GR-এ নিয়মটি A → wR. — নির্মাণের সংজ্ঞা
  2. ধাপ: প্রথম নিয়ম A → X1⋯Xk হলে w = w1⋯wk, যেখানে Xi ⇒∗ wi ছোট derivation-এ। — CFG-তে প্রতিটি variable স্বাধীনভাবে বাড়ে
  3. Induction hypothesis-এ GR-এ Xi ⇒∗ wiR; আর GR-এর নিয়ম A → Xk⋯X1 থেকে A ⇒∗ wkR⋯w1R. — উল্টো নিয়ম
  4. wkR⋯w1R = (w1⋯wk)R = wR. উল্টো দিক একই যুক্তিতে, কারণ (GR)R = G. ∎ — (uv)R = vRuR

(খ)-এর প্রমাণও একই ধাঁচের: প্রতিটি parse tree-র প্রতিটি পাতায় a-এর জায়গায় h(a) বসালে নতুন grammar-এর একটি parse tree পাওয়া যায়, আর উল্টোটিও। Homomorphism-এর আরও সাধারণ রূপ substitution: প্রতিটি terminal a-এর জায়গায় একটি পুরো CFL s(a). প্রমাণ একই: a-এর জায়গায় s(a)-এর grammar-এর start variable বসান। CFL substitution-এও বদ্ধ।

একটি কথা লক্ষ করুন: এই পাঁচটি নির্মাণে grammar-এর আকার প্রায় বাড়ে না। Union আর concatenation-এ একটি নতুন নিয়ম, star-এ দুটি; reversal-এ নিয়ম-সংখ্যা একই। Regular language-এর reversal-এ DFA 2n state পর্যন্ত বাড়তে পারত; grammar-এর জগতে reversal বিনামূল্যে। অংশ ৪-এর Python ব্লক এই নির্মাণগুলো সত্যিই চালিয়ে সংজ্ঞার সঙ্গে মেলায়।

৩ · Regular language-এর সঙ্গে ছেদ — PDA × DFA

বাজারঘরের নতুন নিয়মে “দৈর্ঘ্য ২০০-এর বেশি নয়” একটি regular শর্ত, কারণ সসীম language সবসময় regular. তাই প্রশ্নটি দাঁড়ায়: CFL ∩ regular কি CFL? উত্তর হ্যাঁ, আর নির্মাণটি পর্ব ০৮-এর product construction-এর সরাসরি বড় ভাই।

উপপাদ্য ৩.১ (CFL ∩ regular)

P = (Q, Σ, Γ, δ, q0, F) একটি PDA আর D = (Q′, Σ, δ′, s0, F′) একটি DFA হলে নিচের PDA P × D ঠিক L(P) ∩ L(D) চেনে:
State (q, s) ∈ Q × Q′; শুরু (q0, s0); accepting F × F′; আর প্রতিটি (r, y) ∈ δ(q, a, x)-এর জন্য
a ∈ Σ হলে ((r, δ′(s, a)), y) ∈ δ×((q, s), a, x); a = ε হলে ((r, s), y) ∈ δ×((q, s), ε, x).

কথায়: PDA যখন একটি চিহ্ন পড়ে, DFA-ও সেই চিহ্ন পড়ে এক পা এগোয়; PDA যখন ε-move করে, DFA দাঁড়িয়ে থাকে। Stack পুরোটাই PDA-র; DFA-র কোনো stack নেই, তাই দুটিকে একটি stack-এই ধরে রাখা যায়।

প্রমাণ (move-এর সংখ্যার ওপর induction). দাবি: সব k ≥ 0-এর জন্য

((q0, s0), w, ε) ⊢k ((q, s), ε, γ)  ⇔  (q0, w, ε) ⊢k (q, ε, γ) আর δ̂′(s0, w) = s
  1. ভিত্তি k = 0: দুই দিকেই w = ε, q = q0, s = s0, γ = ε. — ⊢0 মানে কিছুই না বদলানো
  2. ধাপ: শেষ move যদি একটি চিহ্ন a পড়ে, তাহলে w = va, আর আগের k − 1 move-এ v পড়া হয়েছে। নির্মাণ অনুযায়ী product-এর শেষ move-টি P-এর একটি move, আর DFA-অংশ s1 থেকে δ′(s1, a)-তে যায়। — δ×-এর প্রথম নিয়ম
  3. Induction hypothesis-এ v পড়ার পর DFA-অংশ s1 = δ̂′(s0, v), তাই এখন s = δ′(δ̂′(s0, v), a) = δ̂′(s0, va). — δ̂′-এর সংজ্ঞা
  4. শেষ move ε-move হলে w বদলায় না, DFA-অংশও বদলায় না, আর P-এর অংশে একটি ε-move. — δ×-এর দ্বিতীয় নিয়ম
  5. এখন w ∈ L(P × D) ⇔ কোনো (q, s) ∈ F × F′-এ পৌঁছানো যায় ⇔ q ∈ F-এ পৌঁছানো যায় আর δ̂′(s0, w) ∈ F′ ⇔ w ∈ L(P) ∩ L(D). ∎ — accepting সেট F × F′

এর সঙ্গে আসে একটি ছোট কিন্তু কাজের ফল: L CFL আর R regular হলে L ∖ R = L ∩ R̄-ও CFL, কারণ regular language-এর complement regular. বাজারঘরের দলের দৈর্ঘ্যের শর্ত, “কোনো নিষিদ্ধ শব্দ নেই” ধরনের শর্ত, সবই এভাবে CFL-এর ভেতরে থেকে যোগ করা যায়।

নিচের stepper-এ একটি নির্দিষ্ট product. P হলো EQ-এর PDA (a আর b সমান সংখ্যক; stack-এর ওপরে বিপরীত চিহ্ন থাকলে pop, নইলে push), আর D হলো “bb নেই”-এর DFA: s0 মানে শেষ চিহ্ন b নয়, s1 মানে শেষ চিহ্ন b, আর d একটি dead state. Product-এর language হলো “a আর b সমান সংখ্যক, আর পাশাপাশি দুটি b নেই”।

যন্ত্রTransitionশুরু / accepting
P (EQ)q1 → q2: ε, ε → $
q2 → q2: a, b → ε ∣ b, a → ε ∣ a, ε → a ∣ b, ε → b
q2 → q3: ε, $ → ε
q1 / {q1, q3}
D (NOBB)s0: a → s0, b → s1
s1: a → s0, b → d
d: a, b → d
s0 / {s0, s1}
1product প্রস্তুত2ε, ε → $3a পড়া4b পড়া5a পড়া6b পড়া7ε, $ → ε8abba চালানো
এই ধাপের configuration
configuration
PDA-অংশ
DFA-অংশ
  1. প্রস্তুতি। Product-এর state হলো জোড়া (q, s), লেখায় q·s. শুরু q1·s0, accepting সেট {q1, q3} × {s0, s1}, অর্থাৎ চারটি জোড়া। P-এর ৬টি move × D-এর ৩টি state থেকে ১৮টি product-move.
  2. ε-move. P কিছু না পড়ে $ রাখে। ε-move-এ DFA-অংশ এগোয় না, তাই s0-তেই থাকে। Configuration (q2·s0, abab, $).
  3. a পড়া। ওপরে $, বিপরীত চিহ্ন b নেই, তাই P a push করে। একই চিহ্ন a পড়ে DFA s0 থেকে s0-তে। এই ধাপে দুই যন্ত্র একসঙ্গে এক পা এগোল।
  4. b পড়া। ওপরে a, তাই P b, a → ε move-এ a pop করে; stack-এ আবার শুধু $. DFA b পড়ে s1-এ: শেষ চিহ্ন b.
  5. a পড়া। P আবার a push করে; DFA a পড়ে s1 থেকে s0-তে ফেরে। এ পর্যন্ত পড়া aba-তে পাশাপাশি দুটি b নেই।
  6. b পড়া। P a pop করে, stack-এ শুধু $; DFA s0 থেকে s1. Input শেষ, কিন্তু q2 accepting নয়, তাই আরেকটি ε-move লাগবে।
  7. শেষ ε-move. ε, $ → ε দিয়ে P q3-তে, DFA-অংশ s1-এই। q3 ∈ F আর s1 ∈ F′, তাই q3·s1 accepting: abab গৃহীত। এটি দুই শর্তই মানে।
  8. abba. P একা abba গ্রহণ করত (দুটি a, দুটি b). কিন্তু তৃতীয় চিহ্ন b পড়ে DFA-অংশ s1 থেকে d-তে যায়, আর d থেকে আর ফেরা নেই। শেষে q3·d, যা accepting নয়: বাতিল। Product ঠিক “EQ এবং bb নেই” চেনে।

নিচের ব্লকটি উপপাদ্যটি সরাসরি কোডে লেখে। run হলো পর্ব ৩২-এর মতো configuration-এর ওপর BFS, stack-এর উচ্চতায় |w| + 2 সীমা রেখে (এই PDA প্রতিটি push-এ একটি চিহ্ন পড়ে, তাই stack কখনো |w| + 1-এর বেশি ওঠে না, আর সীমাটি কোনো গৃহীত পথ কাটে না)। product_pda উপপাদ্যের δ×, অক্ষরে অক্ষরে। তারপর দৈর্ঘ্য ৮ পর্যন্ত সব string-এ product-কে সংজ্ঞার সঙ্গে মেলানো হয়।

from collections import deque
from itertools import product
def run(P, w):     # BFS over (state, rest, stack), top = st[0]; "" means ε
    start = (P["q0"], w, ""); parent, todo = {start: None}, deque([start])
    while todo:
        c = todo.popleft(); q, rest, st = c
        if rest == "" and q in P["F"]:
            path = []
            while c: path.append(c); c = parent[c]
            return path[::-1]
        for (p, a, x), moves in P["d"].items():
            if p == q and rest.startswith(a) and st.startswith(x):
                for r, y in moves:
                    n = (r, rest[len(a):], y + st[len(x):])
                    if len(n[2]) <= len(w) + 2 and n not in parent:
                        parent[n] = c; todo.append(n)
EQ = {"q0": "q1", "F": {"q1", "q3"}, "d": {("q1", "", ""): [("q2", "$")],  # #a = #b
    ("q2", "a", "b"): [("q2", "")], ("q2", "b", "a"): [("q2", "")],
    ("q2", "a", ""): [("q2", "a")], ("q2", "b", ""): [("q2", "b")],
    ("q2", "", "$"): [("q3", "")]}}
NOBB = {"s0": {"a": "s0", "b": "s1"}, "s1": {"a": "s0", "b": "d"}, "d": {"a": "d", "b": "d"}}
def product_pda(P, D, s0, DF):     # DFA "no bb" above: d = dead; ε-move: s stays
    d = {}
    for (q, a, x), moves in P["d"].items():
        for s in D:
            t = D[s][a] if a else s
            d.setdefault(((q, s), a, x), []).extend(((r, t), y) for r, y in moves)
    return {"q0": (P["q0"], s0), "F": {(q, s) for q in P["F"] for s in DF}, "d": d}
X = product_pda(EQ, NOBB, "s0", {"s0", "s1"})
ws = ["".join(t) for k in range(9) for t in product("ab", repeat=k)]
ok = sum((run(X, w) is not None) == (w.count("a") == w.count("b") and "bb" not in w) for w in ws)
print(f"{sum(map(len, X['d'].values()))} product moves; agrees on {ok} of {len(ws)} strings")
for w in ["abab", "abba"]:
    path = run(X, w); print(w, "ACCEPT" if path else "REJECT")
    for (q, s), rest, st in path or []: print(f"   ({q}·{s}, {rest or 'ε'}, {st or 'ε'})")

আসল আউটপুট (ব্রাউজারের Python):

18 product moves; agrees on 511 of 511 strings
abab ACCEPT
   (q1·s0, abab, ε)
   (q2·s0, abab, $)
   (q2·s0, bab, a$)
   (q2·s1, ab, $)
   (q2·s0, b, a$)
   (q2·s1, ε, $)
   (q3·s1, ε, ε)
abba REJECT

১৮টি product-move, ঠিক ৬ × ৩. দৈর্ঘ্য 0 থেকে 8-এর সব ৫১১টি string-এ product-এর উত্তর আর “a, b সমান সংখ্যক এবং bb নেই” একমত। abab-এর পথ stepper-এর সাতটি configuration-এর সঙ্গে হুবহু মেলে। abba-র জন্য BFS সব শাখা ঘুরে কোনো accepting configuration পায়নি, কারণ DFA-অংশ d-তে আটকে যায়। EQ-এর PDA nondeterministic: “a, ε → a” move-টি ওপরে b থাকলেও খাটে, তাই BFS অনেক বাড়তি শাখা দেখে; তবু ভুল শাখা কখনো গ্রহণে পৌঁছায় না, কারণ stack শেষে ফাঁকা হতে হলে প্রতিটি push-এর জোড়া pop লাগে।

Inverse homomorphism. h : Σ → Γ∗ আর L ⊆ Γ∗ একটি CFL হলে h−1(L) = {w : h(w) ∈ L}-ও CFL. পর্ব ১৬-এ DFA-র জন্য প্রতিটি তীর ছিল h(a)-এর একটি গোটা যাত্রা। PDA-তে একটি a-এর জন্য h(a) পড়তে কয়েকটি move আর মাঝে ε-move লাগতে পারে, তাই নির্মাণে একটি সসীম buffer যোগ হয়: নতুন PDA-র state (q, u), যেখানে u হলো কোনো h(a)-এর একটি suffix. a পড়লে buffer-এ h(a) ভরে; তারপর ε-move দিয়ে পুরোনো PDA buffer থেকে চিহ্ন খায়; buffer ফাঁকা হলে পরের চিহ্ন পড়া চলে। সব h(a) সসীম, তাই suffix-ও সসীম, আর state-সংখ্যা সসীম থাকে। পূর্ণ প্রমাণ Hopcroft–Motwani–Ullman-এর CFL-অধ্যায়ে আছে; এখানে বাদ।

৪ · যেখানে closure ভাঙে — দুটি CFL-এর ছেদ আর complement

PDA × DFA কাজ করল, কারণ মাত্র একটি stack ছিল। দুটি PDA পাশাপাশি চালাতে দুটি stack লাগে, আর একটি stack-এ দুটি stack মেশানো যায় না: একটি PDA যখন নিচের চিহ্ন চায়, অন্যটির চিহ্ন ওপরে বসে থাকে। দুটি stack-ওয়ালা যন্ত্র আসলে Turing machine-এর সমান শক্তিশালী (দুই-stack PDA, পর্ব ৩২-এর অংশ ৮)। তাই আশঙ্কা জাগে, দুটি CFL-এর ছেদ CFL না-ও হতে পারে। আশঙ্কাটি সত্য।

উপপাদ্য ৪.১ (∩ আর complement-এ closure নেই)

Σ = {a, b, c}-এর ওপর CFL-এর শ্রেণি intersection-এ বদ্ধ নয়, আর complement-এও বদ্ধ নয়।

1L1 = aⁿbⁿcᵐ2L2 = aᵐbⁿcⁿ3একটিতে আছে, অন্যটিতে নেই4দুটিতেই আছে5ছেদ হিসাব6pumping lemma7complement-এর পালা
এই ধাপের যুক্তি
দাবি
কারণ
  1. L1. L1 = {anbncm : n, m ≥ 0}. Grammar: S → XC, X → aXb ∣ ε (সমান সংখ্যক a আর b), C → cC ∣ ε (যত খুশি c). তাই L1 একটি CFL.
  2. L2. L2 = {ambncn : n, m ≥ 0}. Grammar: S → AY, A → aA ∣ ε, Y → bYc ∣ ε. এটিও CFL. প্রতিটির PDA-কে মাত্র একটি তুলনা করতে হয়, এক stack-এই সম্ভব।
  3. আলাদা ফল। aabbc-তে a আর b সমান (২টি করে), তাই L1-এ আছে; কিন্তু b দুটি আর c একটি, তাই L2-এ নেই। abbcc উল্টো: L2-এ আছে, L1-এ নেই।
  4. দুটিতেই। aabbcc-তে a, b, c তিনটিই দুটি করে, তাই দুই language-এই আছে।
  5. ছেদ। a∗b∗c∗ আকারের string দুটিতেই থাকে ঠিক তখন, যখন #a = #b (L1) আর #b = #c (L2). তাই L1 ∩ L2 = {anbncn}. নিচের Python ব্লক দৈর্ঘ্য ≤ 12-এ ঠিক এই পাঁচটি string পায়।
  6. Pumping lemma. {anbncn} CFL নয়: পর্ব ৩৬-এর CFL pumping lemma-র মানক প্রমাণ (vxy-এর দৈর্ঘ্য ≤ p, তাই এটি বড়জোর দুই রকম অক্ষর ছোঁয়, আর pump করলে তিনটি গুনতি সমান থাকে না)। দুটি CFL-এর ছেদ CFL নয়, তাই ∩-এ closure নেই। ∎
  7. Complement. ধরুন CFL complement-এ বদ্ধ। Union-এ তো বদ্ধই। তাহলে De Morgan-এর সূত্রে L1 ∩ L2 = (L̄1 ∪ L̄2)-এর complement-ও CFL হতো, যা ধাপ ৬-এর বিরোধী। তাই complement-এ closure নেই। ∎

নিচের ব্লক একটি ছোট fixpoint function lang দিয়ে grammar থেকে দৈর্ঘ্য ≤ n-এর সব string বের করে: প্রতিটি variable-এর string-সেট খালি থেকে শুরু করে প্রতিটি নিয়ম খাটিয়ে বাড়ায়, যতক্ষণ না আর কিছু বদলায়। তারপর stepper-এর ছেদ হিসাব করে, আর অংশ ২-এর তিনটি নির্মাণ (union, reversal, homomorphism) চালিয়ে সংজ্ঞার সঙ্গে মেলায়। এই ব্লকের function অংশ ৬-এর ব্লকও ব্যবহার করবে (data-shared), তাই আগে এটি চালান।

from itertools import product
def lang(G, n, S="S"):   # all strings of length <= n derivable from S (fixpoint)
    L = {A: set() for A in G}        # one char = one symbol; uppercase = variable
    while True:
        new = {A: set() for A in G}
        for A, rules in G.items():
            for r in rules:                          # "" is the rule A -> ε
                for parts in product(*[L[s] if s in G else [s] for s in r]):
                    if len(w := "".join(parts)) <= n: new[A].add(w)
        if new == L: return L[S]
        L = new
show = lambda ws: [w or "ε" for w in sorted(ws, key=lambda w: (len(w), w))]
G1 = {"S": ["XC"], "X": ["aXb", ""], "C": ["cC", ""]}   # a^n b^n c^m
G2 = {"S": ["AY"], "A": ["aA", ""], "Y": ["bYc", ""]}   # a^m b^n c^n
L1, L2 = lang(G1, 12), lang(G2, 12)
print("L1 ∩ L2 (length <= 12):", show(L1 & L2))
print("only a^n b^n c^n:", all(w == "a" * k + "b" * k + "c" * k
                                for w in L1 & L2 for k in [len(w) // 3]))
# closure by grammar surgery, checked against the definition
U = {"U": ["S", "T"], **G1, "T": ["AY"], "A": G2["A"], "Y": G2["Y"]}
print("union    :", lang(U, 12, "U") == L1 | L2)
R = {A: [r[::-1] for r in rules] for A, rules in G1.items()}
print("reversal :", lang(R, 12) == {w[::-1] for w in L1})
h = {"a": "0", "b": "01", "c": "1"}
H = {A: ["".join(h.get(s, s) for s in r) for r in rules] for A, rules in G1.items()}
print("h(L1)    :", lang(H, 12) == {"".join(h[c] for c in w) for w in L1
                                    if len("".join(h[c] for c in w)) <= 12})
print("h(L1) sample:", show(lang(H, 5)))

আসল আউটপুট (ব্রাউজারের Python):

L1 ∩ L2 (length <= 12): ['ε', 'abc', 'aabbcc', 'aaabbbccc', 'aaaabbbbcccc']
only a^n b^n c^n: True
union    : True
reversal : True
h(L1)    : True
h(L1) sample: ['ε', '1', '11', '001', '111', '0011', '1111', '00111', '11111']

প্রথম দুই লাইন stepper-এর ধাপ ৫: দৈর্ঘ্য ১২ পর্যন্ত ছেদে ঠিক n = 0 থেকে 4-এর anbncn. Union-grammar U-তে G2-এর start S-এর নাম বদলে T রাখা হয়েছে, কারণ দুই grammar-এই S ছিল; বাকি variable (X, C বনাম A, Y) আগে থেকেই আলাদা। Reversal-এ প্রতিটি নিয়মের ডান দিক উল্টানো (r[::-1]), আর homomorphism-এ প্রতিটি terminal-এর জায়গায় h-এর মান; দুটিই সংজ্ঞার সঙ্গে হুবহু মেলে। শেষ লাইনে h(L1)-এর ছোট সদস্য: যেমন h(ab) = 001, h(c) = 1. h এখানে কোনো চিহ্নকে ε-তে পাঠায় না, তাই |h(w)| ≥ |w|, আর দৈর্ঘ্য ১২ পর্যন্ত তুলনা সম্পূর্ণ।

Complement নিয়ে দুটি সূক্ষ্ম কথা। (১) “Complement-এ বদ্ধ নয়” মানে কিছু CFL-এর complement CFL নয়, সবগুলোর নয়, এমন নয়। Regular language-এর complement তো CFL-ই। এমনকি {anbncn}-এর complement একটি CFL: এটি কয়েকটি CFL-এর union (a∗b∗c∗-এর বাইরের string, যা regular; আর aibjck-এর মধ্যে i ≠ j বা j ≠ k). একইভাবে {ww}-এর complement একটি CFL বলে পরিচিত, যদিও {ww} নিজে CFL নয়। অর্থাৎ CFL-শ্রেণি complement-এ অসমমিত। (২) Deterministic PDA-র language (DCFL) complement-এ বদ্ধ, কারণ deterministic যন্ত্রে accepting আর non-accepting অদলবদল করা যায় (ε-চক্র সামলানোর পর); এর বিস্তারিত পর্ব ৩৫-এ। কিন্তু DCFL union-এ বদ্ধ নয়: উপরের L1 আর L2 দুটিই DCFL, অথচ L1 ∪ L2 একটি inherently ambiguous CFL (পর্ব ২৭), আর প্রতিটি DCFL-এর unambiguous grammar থাকে।

৫ · Closure দিয়ে non-CFL প্রমাণ

পর্ব ১৬-এর কৌশল এখানেও চলে, শুধু একটি শর্ত বেশি কঠোর: ছাঁকনিটি অবশ্যই regular হতে হবে, কারণ CFL-এর সঙ্গে CFL-এর ছেদে closure নেই। কাঠামো:

  1. ধরুন L একটি CFL. — contradiction-এর জন্য
  2. একটি regular language R বেছে নিন (যেমন a∗b∗c∗), যাতে L ∩ R হিসাব করা সহজ। — উপপাদ্য ৩.১ অনুযায়ী L ∩ R তখন CFL
  3. দরকার হলে homomorphism বা inverse homomorphism চালান। — অংশ ২ ও ৩
  4. দেখান যে ফলটি একটি জানা non-CFL, যেমন {anbncn}. বিরোধ, তাই L CFL নয়। ∎ — পর্ব ৩৬-এর pumping lemma

উদাহরণ ১. বাজারঘরের গুদামে প্রতিটি চালানের লগ একটি string: a মানে আলুর বস্তা, b মানে বেগুনের ঝুড়ি, c মানে চালের বস্তা। নিয়ম: তিন রকম জিনিস সমান সংখ্যায়, যেকোনো ক্রমে। L3 = {w ∈ {a, b, c}∗ : #a = #b = #c}. L3 ∩ a∗b∗c∗ = {anbncn}, তাই L3 CFL নয়। সরাসরি pumping lemma দিয়ে L3-এর প্রমাণ লিখতে গেলে বহু ক্ষেত্র ভাবতে হতো, কারণ L3-এর string-এ অক্ষর যেকোনো ক্রমে আসে; ছাঁকনি সেই ঝামেলা এক লাইনে মেটায়।

উদাহরণ ২. L4 = {ww : w ∈ {a, b}∗}. L4 ∩ a∗b∗a∗b∗ = {aibjaibj : i, j ≥ 0}, যা CFL নয়: s = apbpapbp নিয়ে পর্ব ৩৬-এর ww-প্রমাণের মতোই pumping চলে। ছাঁকনির পর string-এর আকার নির্দিষ্ট হয়ে যায়, আর pumping-এর ক্ষেত্রভাগ ছোট হয়।

উদাহরণ ৩, homomorphism-এর contrapositive. L5 = {anb2nc3n}. এখানে সরাসরি ছাঁকনি যথেষ্ট নয়, কারণ গুনতিগুলো সমান নয়। পথ হলো inverse homomorphism: h : {0, 1, 2} → {a, b, c}∗, h(0) = a, h(1) = bb, h(2) = ccc নিন। তাহলে h−1(L5) ∩ 0∗1∗2∗ = {0n1n2n}, কারণ h(0i1j2k) = aib2jc3k, যা L5-এ ঠিক তখন, যখন i = j = k. L5 CFL হলে বাঁ দিকও CFL হতো; কিন্তু ডান দিক {anbncn}-এর মতোই, শুধু চিহ্নের নাম আলাদা। তাই L5 CFL নয়।

চারটি সাধারণ ভুল। (১) CFL-এর সঙ্গে ছেদ: “L ∩ {anbn} …” লিখে কিছু প্রমাণ হয় না; ছাঁকনি regular না হলে closure খাটে না। (২) Complement নিয়ে যুক্তি: “L CFL, তাই L̄ CFL” ভুল; উপপাদ্য ৪.১. (৩) উল্টো দিক: L ∩ R CFL হলে L CFL, এমন নয়; R = ∅ নিলে যেকোনো L-এর ছেদ ∅. (৪) Subset: {anbncn} ⊆ Σ∗, আর Σ∗ CFL, কিন্তু subset নিলে closure নেই।

৬ · Decidable প্রশ্ন — membership, emptiness আর finiteness

এবার decision property: grammar হাতে দিলে কোন প্রশ্ন decidable, অর্থাৎ কোন প্রশ্নের উত্তর সবসময় থামে এমন একটি algorithm দিতে পারে? Input হিসেবে একটি CFG G (বা PDA; পর্ব ৩৪-এর রূপান্তরে একটি থেকে অন্যটি algorithm দিয়েই পাওয়া যায়)।

উপপাদ্য ৬.১ (membership)

ACFG = {⟨G, w⟩ : w ∈ L(G)} decidable. G-কে CNF-এ এনে (পর্ব ২৯) CYK চালালে (পর্ব ৩১) O(n3 · |G|) সময়ে উত্তর আসে, n = |w|.

এখানে নতুন কিছু নেই, শুধু একটি সাবধানতা: PDA-কে সরাসরি “চালিয়ে দেখা” decider নয়, কারণ nondeterministic PDA ε-move দিয়ে অসীম ধরে push করে যেতে পারে। পর্ব ৩২-এর simulator তাই stack-এ সীমা রাখত। Grammar-এ গিয়ে CYK চালানোই নিশ্চিত পথ।

উপপাদ্য ৬.২ (emptiness)

ECFG = {⟨G⟩ : L(G) = ∅} decidable. Algorithm: পর্ব ২৮-এর মতো generating variable-এর সেট বের করুন: শুরুতে সব terminal চিহ্নিত; যে নিয়ম A → X1⋯Xk-এর ডান দিকের সব চিহ্ন চিহ্নিত, তার A-কেও চিহ্নিত করুন; নতুন কিছু চিহ্নিত না হওয়া পর্যন্ত চালান। L(G) = ∅ ঠিক তখন, যখন S চিহ্নিত হয়নি।

প্রমাণের রূপরেখা. “X চিহ্নিত ⇔ X ⇒∗ কোনো terminal string”. (⇒) কততম দফায় চিহ্নিত হলো, তার ওপর induction: ডান দিকের প্রতিটি চিহ্ন থেকে একটি string আসে, সেগুলো পাশাপাশি বসালেই X-এর string. (⇐) X ⇒∗ w-এর parse tree-র উচ্চতার ওপর induction: মূলের নিয়মের প্রতিটি সন্তান ছোট উচ্চতায় string দেয়, তাই চিহ্নিত, তাই X-ও চিহ্নিত হবে। প্রতি দফায় অন্তত একটি নতুন variable চিহ্নিত না হলে algorithm থামে, তাই বড়জোর |V| দফা; সাবধানী গণনা-কাঠামো দিয়ে grammar-এর আকারের রৈখিক সময়েও করা যায়। ∎ একটু বাড়তি হিসাব রাখলে algorithm প্রতিটি variable-এর একটি ছোট witness string-ও দেয়, যা নিচের কোডে দেখবেন।

উপপাদ্য ৬.৩ (finiteness)

G CNF-এ আছে আর কোনো useless symbol নেই ধরে নিন (আগে non-generating, তারপর unreachable variable মুছে)। Variable graph-এ প্রতিটি নিয়ম A → BC-এর জন্য A → B আর A → C তীর দিন। তাহলে L(G) অসীম ⇔ এই graph-এ একটি cycle আছে। তাই INFINITECFG আর তার complement দুটিই decidable.

  1. (⇐) cycle থাকলে অসীম: cycle-এ একটি variable A, তাই A ⇒+ uAv. CNF-এ প্রতিটি A → BC-র B আর C দুটিই অন্তত একটি অক্ষর দেয়, তাই |uv| ≥ 1. — CNF-এ ε-নিয়ম নেই (S0 → ε ছাড়া)
  2. A reachable, তাই S ⇒∗ xAy; A generating, তাই A ⇒∗ z. — useless symbol নেই
  3. তাহলে প্রতিটি i ≥ 0-এ S ⇒∗ xuizviy, আর এদের দৈর্ঘ্য সব আলাদা। তাই L(G) অসীম। — cycle-টি i বার ঘোরানো
  4. (⇒) cycle না থাকলে সসীম: parse tree-র মূল থেকে পাতার প্রতিটি পথে variable-গুলো graph-এর একটি পথ ধরে চলে; cycle নেই বলে কোনো variable দুবার আসে না, তাই পথে বড়জোর k = |V|টি variable. — graph-এর পথ = parse tree-র পথ
  5. CNF-এর parse tree binary, তাই এমন tree-তে পাতা বড়জোর 2k−1. প্রতিটি string-এর দৈর্ঘ্য তাই ≤ 2k−1, আর এমন string সসীম সংখ্যক। ∎ — পর্ব ২৯-এর উচ্চতার সীমা

আগে ছাঁটাই, তারপর cycle খোঁজা। Useless variable রেখে দিলে ভুল উত্তর আসতে পারে। S → AB ∣ SD আর D → DD থাকলে graph-এ S → S আর D → D দুটি cycle, কিন্তু D থেকে কোনো terminal string আসে না, তাই S → SD নিয়মটি কোনো derivation-এ কাজে লাগে না। আর CNF-এর শর্তও জরুরি: A → B, B → A ধরনের unit নিয়মের cycle কোনো অক্ষর যোগ করে না, তাই CNF ছাড়া “cycle ⇒ অসীম” খাটে না।

Variable graph — একটি নতুন নিয়ম, দুটি cycle

কঠিন তীর Gfin-এর নিয়ম থেকে: S → AB, A → BC, B → CC. ভাঙা লাল তীর নতুন নিয়ম C → AB থেকে।

Variable graph of a CNF grammar, with the new rule C to AB creating cycles SABC লাল ছাড়া: cycle নেই, সসীম লালসহ: A ⇄ C, B ⇄ C, অসীম
ছবি ৩৭.১ — Gfin: S → AB, A → BC ∣ a, B → CC ∣ b, C → a. কঠিন তীরগুলো একটি DAG (cycle-হীন directed graph), তাই language সসীম। C → AB যোগ করলে C থেকে A আর B-তে তীর, আর দুটি cycle তৈরি হয়।
1G_fin, ছাঁটাই2তীর বসানো3cycle খোঁজা4সসীম: পুরো তালিকা5নতুন নিয়ম C → AB6cycle B → C → B7pump করা8ফাঁদ: useless cycle
এই ধাপের অবস্থা
নিয়ম
তীর
সিদ্ধান্ত
  1. ছাঁটাই। Gfin CNF-এ আছে। C থেকে a, B থেকে b, A থেকে a, আর S থেকে AB ⇒ ab: চারটিই generating. S থেকে সবাই পৌঁছায়: সবাই reachable. তাই কিছু মোছার নেই, k = 4.
  2. তীর। শুধু দুই-variable নিয়ম তীর দেয়: S → AB থেকে S→A, S→B; A → BC থেকে A→B, A→C; B → CC থেকে B→C. A → a-এর মতো terminal-নিয়ম কোনো তীর দেয় না।
  3. Cycle খোঁজা। S, A, B, C ক্রমে সাজালে প্রতিটি তীর বাঁ থেকে ডানে যায় (topological ক্রম)। এমন ক্রম থাকা মানেই cycle নেই। তাই উপপাদ্য ৬.৩ অনুযায়ী L(Gfin) সসীম।
  4. তালিকা। দৈর্ঘ্যের সীমা 2k−1 = 8, তাই দৈর্ঘ্য ≤ 8-এর সব string বের করলেই পুরো language: ab, aaa, bab, aaab, baaa, aaaaa. ছয়টি string, সবচেয়ে লম্বাটির দৈর্ঘ্য ৫, সীমার নিচে।
  5. নতুন নিয়ম। C → AB যোগ করুন (Ginf). এখন C থেকেও A আর B-তে তীর, মোট ৭টি তীর। এবার আর এমন ক্রম নেই, যেখানে সব তীর সামনে যায়।
  6. Cycle. B → C (B → CC থেকে) আর C → B (C → AB থেকে): B → C → B একটি cycle. একইভাবে A → C → A. উপপাদ্য অনুযায়ী language অসীম।
  7. Pump. Cycle থেকে আসল derivation: B ⇒ CC ⇒ ABC ⇒ aBC ⇒ aBa, অর্থাৎ B ⇒∗ aBa. তাই S ⇒ AB ⇒ aB ⇒∗ a·akBak ⇒ ak+1bak, প্রতিটি k ≥ 0-এ: ab, aaba, aaabaa, …. দৈর্ঘ্য ১ থেকে ৯-এ string-এর সংখ্যা 0, 1, 2, 4, 9, 18, 40, 83, 175: বাড়তেই থাকে।
  8. ফাঁদ। Gfin-এ S → SD আর D → DD যোগ করলে ছাঁটাইয়ের আগের graph-এ S → S আর D → D cycle. কিন্তু D generating নয়, তাই আগে D আর S → SD মুছতে হয়; তারপর graph আবার Gfin-এর, cycle নেই, language সসীম ও একই।

নিচের ব্লক তিনটি algorithm একসঙ্গে লেখে, আর অংশ ৪-এর ব্লকের lang আর show ব্যবহার করে। generating প্রতিটি generating variable-এর সবচেয়ে ছোট witness রাখে; trim পর্ব ২৮-এর স্থির ক্রমে আগে non-generating, তারপর unreachable মোছে; on_cycle সেই variable-গুলো দেয়, যারা নিজের কাছে ফিরতে পারে। সসীম হলে 2k−1 পর্যন্ত সব string ছাপা হয়।

def generating(G):       # fixpoint: a shortest string for every generating variable
    wit, changed = {}, True
    while changed:
        changed = False
        for A, rules in G.items():
            for r in rules:
                if all(s in wit or s not in G for s in r):
                    w = "".join(wit.get(s, s) for s in r)
                    if A not in wit or len(w) < len(wit[A]): wit[A] = w; changed = True
    return wit
def reach(G, A):         # variables reachable from A in one or more steps
    seen, todo = set(), [A]
    while todo:
        for B in {s for r in G[todo.pop()] for s in r if s in G} - seen:
            seen.add(B); todo.append(B)
    return seen
def trim(G):             # drop non-generating first, then unreachable (পর্ব ২৮)
    gen = generating(G)
    G = {A: [r for r in R if all(s in gen or s not in G for s in r)]
         for A, R in G.items() if A in gen}
    return {A: G[A] for A in reach(G, "S") | {"S"}}
on_cycle = lambda G: sorted(A for A in G if A in reach(G, A))
def decide(name, G):
    if "S" not in (wit := generating(G)): return print(f"{name}: EMPTY")
    T = trim(G); cyc = on_cycle(T)
    print(f"{name}: witness {wit['S']}, raw cycle {on_cycle(G)}, trimmed cycle {cyc}")
    print("   INFINITE" if cyc else f"   FINITE {show(lang(T, 2 ** (len(T) - 1)))}")
G_fin = {"S": ["AB"], "A": ["BC", "a"], "B": ["CC", "b"], "C": ["a"]}
G_inf = {**G_fin, "C": ["AB", "a"]}
G_trap = {**G_fin, "S": ["AB", "SD"], "D": ["DD"]}
G_none = {"S": ["AB"], "A": ["a"], "B": ["BC", "AB"], "C": ["b"]}
for name in ["G_fin", "G_inf", "G_trap", "G_none"]: decide(name, globals()[name])
L9 = lang(G_inf, 9)
print("G_inf, strings of length 1..9:", [sum(len(w) == n for w in L9) for n in range(1, 10)])
print("a^(k+1) b a^k in L(G_inf) for k = 0..3:", all("a" * (k + 1) + "b" + "a" * k in L9 for k in range(4)))

আসল আউটপুট (ব্রাউজারের Python):

G_fin: witness ab, raw cycle [], trimmed cycle []
   FINITE ['ab', 'aaa', 'bab', 'aaab', 'baaa', 'aaaaa']
G_inf: witness ab, raw cycle ['A', 'B', 'C'], trimmed cycle ['A', 'B', 'C']
   INFINITE
G_trap: witness ab, raw cycle ['D', 'S'], trimmed cycle []
   FINITE ['ab', 'aaa', 'bab', 'aaab', 'baaa', 'aaaaa']
G_none: EMPTY
G_inf, strings of length 1..9: [0, 1, 2, 4, 9, 18, 40, 83, 175]
a^(k+1) b a^k in L(G_inf) for k = 0..3: True

প্রথম দুই লাইন stepper-এর ধাপ ১–৪: witness ab (S ⇒ AB ⇒ aB ⇒ ab), cycle নেই, আর পুরো language ছয়টি string. Ginf-এ A, B, C তিনটিই কোনো cycle-এ আছে, S নেই (S-এ কোনো তীর ঢোকে না)। Gtrap-এর লাইনটি এই পর্বের সবচেয়ে কাজের শিক্ষা: ছাঁটাইয়ের আগে D আর S দুটিই cycle-এ, তাই অসাবধান algorithm “অসীম” বলত; ছাঁটাইয়ের পরে cycle নেই, আর language Gfin-এর সমান। Gnone-এ B → BC আর B → AB দুটি নিয়মেই ডান দিকে B, তাই B কখনো চিহ্নিত হয় না, S-ও না: language ফাঁকা। শেষ দুই লাইন stepper-এর ধাপ ৭.

৭ · Undecidable প্রশ্ন — যেখানে কোনো algorithm নেই

Regular language-এ পর্ব ২০-এর প্রায় সব প্রশ্ন decidable ছিল, কারণ DFA-র complement আর product দুটিই হাতে ছিল: equivalence মানে symmetric difference ফাঁকা কি না। CFL-এ complement আর ছেদ দুটিই হারিয়েছি, আর সেই ফাঁক দিয়ে undecidability ঢোকে।

প্রশ্ন (input: CFG G, G1, G2; regular R)Decidable?পদ্ধতি বা প্রমাণ কোথায়
w ∈ L(G)? (membership)হ্যাঁCNF + CYK, পর্ব ৩১
L(G) = ∅?হ্যাঁgenerating symbol, অংশ ৬
L(G) অসীম?হ্যাঁছাঁটা CNF-এর variable graph-এ cycle
L(G) ∩ R = ∅? L(G) ⊆ R?হ্যাঁPDA × DFA, তারপর emptiness; দ্বিতীয়টিতে R̄ নিয়ে
L(G) = Σ∗? (universality)নাcomputation history, পর্ব ৫২
L(G1) = L(G2)? (equivalence)নাuniversality থেকে reduction
L(G1) ⊆ L(G2)? R ⊆ L(G)?নাR = Σ∗ নিলে universality
L(G1) ∩ L(G2) = ∅?নাPCP, পর্ব ৫৪
G ambiguous?নাPCP, পর্ব ৫৪
L(G) regular? L(G)-এর complement CFL?নাপর্ব ৫৪–৫৫-এর কৌশল
দুটি DPDA-র language সমান?হ্যাঁ (কঠিন উপপাদ্য)Sénizergues, “আরও গভীরে” দেখুন

লক্ষ করুন, সারণিতে কয়েকটি জোড়া প্রায় একই দেখায়, কিন্তু উত্তর উল্টো। L(G) ⊆ R decidable, কারণ এটি L(G) ∩ R̄ = ∅, আর R̄ regular. কিন্তু R ⊆ L(G) undecidable, কারণ এর জন্য L(G)-এর complement লাগত। আর L(G) ∩ R ফাঁকা কি না decidable, অথচ L(G1) ∩ L(G2) ফাঁকা কি না undecidable: ছেদের closure যেখানে আছে, সেখানে emptiness-এর algorithm বয়ে আসে।

কেন universality undecidable, তার ভাবনা. প্রমাণটি পর্ব ৫২-এর বিষয়; মূল কৌশলটি এখানে এক অনুচ্ছেদে। একটি Turing machine M আর input w-এর একটি গ্রহণকারী computation history হলো configuration-এর একটি ক্রম C1#C2#⋯#Ct, যেখানে প্রতিটি পরেরটি আগেরটি থেকে এক ধাপে আসে। এমন সঠিক history-র সেট CFL নয়, কিন্তু “এটি সঠিক history নয়” বলার জন্য শুধু একটি ভুল খুঁজলেই চলে: শুরু ভুল, বা শেষ গ্রহণ নয়, বা কোথাও Ci থেকে Ci+1 ঠিকভাবে আসেনি। শেষ ভুলটি একটি PDA অনুমান করে যাচাই করতে পারে (একটি configuration উল্টো করে লিখলে stack দিয়ে মেলানো যায়)। তাই “সঠিক history নয়”-এর একটি CFG GM,w algorithm দিয়ে বানানো যায়, আর L(GM,w) = Σ∗ ঠিক তখন, যখন M, w গ্রহণ করে না। Universality decidable হলে ATM-ও decidable হতো, যা পর্ব ৫১-এ অসম্ভব প্রমাণিত। Equivalence-এর undecidability তারপর এক লাইনে: G2 হিসেবে Σ∗-এর grammar নিলে universality পাওয়া যায়।

বাস্তবে এর মানে — দুটি parser-এর grammar একই কি না

বাজারঘরের query-ভাষার grammar একজন প্রকৌশলী নতুন করে লিখলেন, যাতে parser দ্রুত চলে। “নতুন grammar ঠিক পুরোনো ভাষাটিই চেনে” কথাটি কোনো টুল সাধারণভাবে প্রমাণ করে দিতে পারবে না। তাহলে বাস্তবে কী করা হয়? উত্তর: পার্থক্য খোঁজা। দুটি grammar ভিন্ন হলে কোনো একটি নির্দিষ্ট string-এ তারা ভিন্নমত, আর সেটি দৈর্ঘ্যের ক্রমে খুঁজতে থাকলে একদিন পাওয়া যাবেই (প্রতিটি string-এ membership তো decidable). অর্থাৎ “ভিন্ন” প্রশ্নটি recognizable: হ্যাঁ-উত্তর থাকলে খোঁজা একসময় থামে। কিন্তু grammar দুটি সমান হলে খোঁজা কখনো থামে না, আর কতদূর খুঁজলে যথেষ্ট, তার কোনো সাধারণ সীমা নেই। নিচের JavaScript ব্লক এই খোঁজাটিই করে, EQ (a আর b সমান সংখ্যক)-এর একটি পাঠ্যবই-grammar আর একটি AI assistant-এর দুটি চেষ্টা নিয়ে।

// Two grammars, same language? Compare all strings up to length n.
// A grammar maps a variable (uppercase) to rules; "" is the rule S -> ε.
function lang(G, n, S = "S") {        // strings of length <= n from S (fixpoint)
  const empty = () => Object.fromEntries(Object.keys(G).map(A => [A, new Set()]));
  let L = empty();
  for (;;) {
    const N = empty();
    for (const A in G) for (const r of G[A]) {
      let parts = [""];
      for (const s of r) {
        const opts = s in G ? [...L[s]] : [s];
        parts = parts.flatMap(p => opts.map(o => p + o)).filter(w => w.length <= n);
      }
      parts.forEach(w => N[A].add(w));
    }
    if (Object.keys(G).every(A => N[A].size === L[A].size)) return L[S];
    L = N;                              // sets only grow, so equal sizes = fixpoint
  }
}
const EQ  = { S: ["aSbS", "bSaS", ""] };        // a textbook grammar for EQ
const AI1 = { S: ["aSb", "bSa", ""] };          // an assistant's first try
const AI2 = { S: ["aSb", "bSa", "SS", ""] };    // its second try
const shortlex = (x, y) => x.length - y.length || (x < y ? -1 : 1);
const t0 = performance.now();
for (const [name, H] of [["AI1", AI1], ["AI2", AI2]]) {
  for (const n of [4, 8, 12]) {
    const a = lang(EQ, n), b = lang(H, n);
    const diff = [...a].filter(w => !b.has(w)).concat([...b].filter(w => !a.has(w)));
    diff.sort(shortlex);
    console.log(`${name}, n=${n}: ${a.size} vs ${b.size} strings; ` +
      (diff.length ? `first difference "${diff[0]}" (${diff.length} in all)` : "no difference found"));
  }
}
console.log("under 1 s:", performance.now() - t0 < 1000);

আসল আউটপুট (ব্রাউজারের JavaScript):

AI1, n=4: 9 vs 7 strings; first difference "abba" (2 in all)
AI1, n=8: 99 vs 31 strings; first difference "abba" (68 in all)
AI1, n=12: 1275 vs 127 strings; first difference "abba" (1148 in all)
AI2, n=4: 9 vs 9 strings; no difference found
AI2, n=8: 99 vs 99 strings; no difference found
AI2, n=12: 1275 vs 1275 strings; no difference found
under 1 s: true

AI1-এর grammar শুধু “বাইরে একটি a আর একটি b মোড়ানো” string দেয়; abba-কে এভাবে মোড়ানো যায় না (শুরু আর শেষ দুটিই a), তাই প্রথম পার্থক্য দৈর্ঘ্য ৪-এ, আর দৈর্ঘ্য ১২-এ AI1 ১২৭৫টির মধ্যে মাত্র ১২৭টি পায়। ১২৭৫ সংখ্যাটি নিজেও একটি যাচাই: দৈর্ঘ্য 2k-এর EQ-string C(2k, k)টি, আর k = 0 থেকে 6-এর যোগফল 1 + 2 + 6 + 20 + 70 + 252 + 924 = 1275. AI2 দৈর্ঘ্য ১২ পর্যন্ত একমত, আর এই grammar আসলেই EQ-এর সঠিক grammar (S → SS যোগ করায় বাকি string আসে; প্রমাণ অনুশীলনের মতো করে নিজে করে দেখুন)। কিন্তু “১২ পর্যন্ত একমত” কোনো প্রমাণ নয়: সারণির undecidability বলে, এমন কোনো n-এর সূত্র নেই যার পরে খোঁজা বন্ধ করা নিরাপদ। lang হলো Python ব্লকের function-এর JavaScript রূপ; set শুধু বাড়ে, তাই আকার না বদলালেই fixpoint.

এই কারণেই বাস্তবের parser-কাজে grammar-সমতা “প্রমাণ” না করে পরীক্ষা করা হয়: পুরোনো আর নতুন parser-কে একই বিশাল input-সংগ্রহে চালিয়ে ফল মেলানো (differential testing), এলোমেলো বা grammar-চালিত input বানানো (Software Testing & QA কোর্সের পর্ব ৬০-এর fuzz testing), আর ছোট দৈর্ঘ্য পর্যন্ত সম্পূর্ণ তুলনা, ঠিক উপরের ব্লকের মতো। Ambiguity-র ক্ষেত্রেও একই চিত্র: সাধারণ algorithm নেই, তাই parser generator একটি যথেষ্ট শর্ত পরীক্ষা করে। Grammar LR(1) হলে (পর্ব ৩৯) সেটি unambiguous, আর conflict-এর রিপোর্ট আসলে “আমি নিশ্চিত হতে পারছি না” বার্তা। Compiler বানানোর গভীর কৌশল পরে Programming Languages & Compilers কোর্সে আসবে।

আরও গভীরে: CFL ∩ regular-এর নির্মাণ, CFL-এর pumping lemma আর CFG-এর বেশ কয়েকটি undecidability ফল Bar-Hillel, Perles আর Shamir-এর ১৯৬১ সালের একটি প্রবন্ধের সঙ্গে যুক্ত বলে পরিচিত; grammar দিয়ে ছেদের নির্মাণকে তাই অনেক বইয়ে “Bar-Hillel construction” বলা হয়। Ambiguity-র undecidability ১৯৬২–৬৩ সালের কাছাকাছি কয়েকজন গবেষক (Cantor, Floyd, Chomsky ও Schützenberger) আলাদাভাবে দেখান বলে উল্লেখ পাওয়া যায়। Greibach ১৯৬০-এর দশকের শেষে একটি সাধারণ উপপাদ্য দেন, যা থেকে “L(G) regular কি না” ধরনের অনেক প্রশ্নের undecidability একসঙ্গে আসে। আর deterministic PDA-র equivalence decidable, এই দীর্ঘদিনের প্রশ্নের উত্তর Géraud Sénizergues ১৯৯৭ সালের দিকে দেন, যার জন্য তিনি ২০০২ সালে Gödel Prize পান; algorithm-টি অত্যন্ত জটিল, আর তার কার্যকর সময়-সীমা নিয়ে গবেষণা চলছে।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • CFL কোন operation-এ বদ্ধ নয়? ∩ আর complement; উদাহরণ {anbncm} ∩ {ambncn} = {anbncn}.
  • CFL ∩ regular CFL কেন? PDA × DFA: state জোড়া, stack একটিই, ε-move-এ DFA দাঁড়িয়ে থাকে।
  • Closure দিয়ে {w : #a = #b = #c} non-CFL দেখান। a∗b∗c∗-এর সঙ্গে ছেদ নিলে {anbncn}.
  • CFG-এর language সসীম কি না কীভাবে ঠিক করবেন? CNF, useless symbol মুছে variable graph-এ cycle খোঁজা।
  • দুটি CFG-এর equivalence decidable? না; universality undecidable, আর Σ∗-এর grammar-এর সঙ্গে equivalence সেটিই।

৮ · AI-এর যুগে CFL-এর closure আর decision

AI assistant এই বিষয়ে আত্মবিশ্বাসের সঙ্গে তালিকা দেয়, কিন্তু তালিকার সীমানায় ভুল করে, আর প্রমাণে শর্ত বাদ দেয়। বারবার দেখা যায় এমন ভুল:

AI-এর ভুলকীভাবে ধরবেন
“CFL intersection-এ বদ্ধ” বা “regular-এর মতো CFL-ও complement-এ বদ্ধ”{anbncm} ∩ {ambncn} মনে রাখা
দুটি PDA-র “product” এক stack-এ বানিয়ে ছেদের প্রমাণপ্রশ্ন করা: দুই PDA-র stack-এর ওপরের চিহ্ন কোথায় থাকে?
Non-CFL প্রমাণে CFL ছাঁকনি ব্যবহারপ্রতিটি ছাঁকনি প্রমাণিতভাবে regular কি না দেখা
ছাঁটাই ছাড়া, বা CNF ছাড়া “cycle ⇒ অসীম”S → SD, D → DD বা A → B, B → A দিয়ে পাল্টা-উদাহরণ
“দুটি grammar ১০ পর্যন্ত মিলেছে, তাই সমান”Equivalence undecidable; brute force শুধু পার্থক্য খুঁজে পেলে প্রমাণ
“L(G) ⊆ R” আর “R ⊆ L(G)” গুলিয়ে ফেলাকোনটিতে complement লাগে, কার complement, লিখে দেখা
বানানো সাল, নাম বা রেফারেন্সSipser বা Hopcroft–Motwani–Ullman-এ নিজে খোঁজা

AI-কে কাজে লাগানোর ভালো উপায়: নির্মাণের প্রতিটি অংশ আর একটি স্বাধীন যাচাইয়ের কোড চাওয়া, তারপর নিজে চালানো আর প্রতিটি দাবি “প্রমাণিত” না “পরীক্ষিত” তা আলাদা করা।

আমি গণনার তত্ত্ব শিখছি। Σ = {a, b}-এর ওপর PDA P (a^n b^n): q1 থেকে q2: ε, ε → $ q2-তে: a, ε → a q2 থেকে q3: b, a → ε q3-তে: b, a → ε q3 থেকে q4: ε, $ → ε শুরু q1, accepting {q1, q4}. DFA D: a-এর সংখ্যা জোড় (e শুরু ও accepting, o বিজোড়; b-তে state বদলায় না)। ১. P × D-এর শুধু reachable state আর move-গুলোর তালিকা দাও। ২. L(P × D) কোন language, এক বাক্যে বলো, আর তার একটি CFG দাও। ৩. শুধু standard library দিয়ে একটি ছোট Python কোড দাও, যা দৈর্ঘ্য ≤ 10-এর সব string-এ তোমার product-কে সংজ্ঞার সঙ্গে মেলায়। ৪. বলো: দুটি PDA-র ক্ষেত্রে একই product কেন কাজ করে না? ৫. প্রতিটি দাবির পাশে লেখো, সেটি প্রমাণিত নাকি শুধু পরীক্ষিত।

(নিজে যাচাই করুন: reachable state সাতটি, move নয়টি; language {a2kb2k : k ≥ 0}, grammar S → aaSbb ∣ ε. পুরো উত্তর অনুশীলন ১-এ।)

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১PDA × DFA চলে, কিন্তু PDA × PDA চলে না। একটি stack আর দুটি stack-এর মধ্যে পার্থক্য এত বড় কেন?

Stack একটি খুব নির্দিষ্ট স্মৃতি: শুধু ওপরের চিহ্ন দেখা যায়, আর নিচে যেতে হলে ওপরেরটি মুছে ফেলতে হয়। একটি PDA যখন anbn চেনে, তখন a-গুলো জমা রাখে আর b পড়ার সময় একে একে মুছে মেলায়। এই কাজের সময় stack পুরোপুরি এই একটি তুলনায় ব্যস্ত। DFA-র সঙ্গে product-এ DFA-র অবস্থা state-এর ভেতরে বসে যায়, stack-এ কোনো জায়গা নেয় না; তাই কিছুই হারায় না।

দুটি PDA-র ক্ষেত্রে দুজনেরই নিজের stack লাগে। {anbncn}-এর জন্য একটি PDA a আর b মেলায়, অন্যটি b আর c. একটি stack-এ দুটি মেলাতে গেলে b পড়ার সময় a-গুলো মুছতে হয়, অথচ একই সময় b-গুলো জমিয়ে রাখতে হয়, যাতে পরে c-এর সঙ্গে মেলানো যায়। একটি stack একসঙ্গে দুই দিকে চলতে পারে না। Pumping lemma এই অসুবিধাকে প্রমাণে রূপ দেয়: parse tree-র একটি ছোট অংশ (|vxy| ≤ p) বড়জোর দুই রকম অক্ষর ছোঁয়।

অন্য দিকে দুটি stack দিলে শক্তি লাফিয়ে Turing machine-এর সমান হয়ে যায়। একটি stack ধরে রাখে tape-এর head-এর বাঁয়ের অংশ, অন্যটি ডানের অংশ; head বাঁয়ে সরানো মানে এক stack থেকে pop করে অন্যটিতে push. তাই PDA × PDA-র মতো একটি “দুই-stack” যন্ত্র সব recognizable language চিনতে পারে, আর তার জন্য emptiness-এর মতো প্রশ্নও undecidable হয়ে যায়। এক stack আর দুই stack-এর মাঝে কোনো আরামদায়ক মধ্যবর্তী ধাপ নেই; এটি গণনার তত্ত্বের সবচেয়ে নাটকীয় সীমানাগুলোর একটি।

বাস্তবে এর প্রভাব হলো, parser-এর ভেতরে একটি stack থাকে, আর “একই সময়ে দুটি স্বাধীন গুনতি মেলানো” ধরনের শর্ত (যেমন একটি ঘোষণার প্রতিটি নাম পরে ঠিক একবার ব্যবহৃত হয়েছে কি না) grammar-এর বাইরে, আলাদা কোডে (semantic analysis-এ) পরীক্ষা করা হয়।

মূল উপলব্ধি: DFA-র সসীম স্মৃতি state-এ মিশে যায়, তাই PDA × DFA নিরাপদ। দুটি সীমাহীন stack এক stack-এ মেশে না, আর দুটি stack একসঙ্গে পেলে যন্ত্রটি Turing machine-এর মতো শক্তিশালী।

প্র ০২{ww} CFL নয়, অথচ তার complement CFL. একটি শ্রেণি complement-এ এমন অসমমিত হয় কীভাবে, আর nondeterminism-এর সঙ্গে এর সম্পর্ক কী?

Nondeterministic যন্ত্র “অন্তত একটি পথ গ্রহণ করে” শর্তে চলে। তাই সে “আছে” ধরনের দাবি সহজে যাচাই করে: অনুমান করুন, তারপর মিলিয়ে দেখুন। “সব জায়গায় মেলে” ধরনের দাবি তার জন্য কঠিন, কারণ প্রতিটি অনুমান আলাদা পথে চলে, কেউ অন্যদের ফল জানে না।

{ww}-এর সদস্য হতে হলে দুই অর্ধের প্রতিটি অবস্থান মিলতে হবে: একটি “সব” ধরনের শর্ত, আর তার ওপর মেলানোর ক্রমটি stack-এর উল্টো (প্রথম অর্ধের প্রথম অক্ষর মেলাতে হয় দ্বিতীয় অর্ধের প্রথম অক্ষরের সঙ্গে, অথচ stack শেষে রাখা অক্ষর আগে দেয়)। Complement-এর সদস্য হতে হলে দুটির একটি যথেষ্ট: দৈর্ঘ্য বিজোড়, অথবা এমন একটি অবস্থান আছে যেখানে দুই অর্ধ আলাদা। দ্বিতীয় শর্তটি nondeterminism দিয়ে অনুমান করা যায়। একটু কৌশল লাগে: string-টিকে ভিন্নভাবে দুই টুকরোয় ভাগ করে দেখা যায় যে এটি দুটি বিজোড় দৈর্ঘ্যের string-এর জোড়া, যাদের মাঝের অক্ষর আলাদা, আর এমন জোড়া একটি CFG সহজে তৈরি করে। এই যুক্তি অনেক পাঠ্যবইয়ে অনুশীলনী হিসেবে থাকে।

একই অসমতা {anbncn}-এ: সদস্য হতে তিনটি গুনতি সমান হতে হবে (“সব”), complement-এ একটি অসমতা যথেষ্ট (“আছে”), তাই complement কয়েকটি CFL-এর union. এটি NP আর coNP-এর সম্পর্কের ছোট রূপ মনে করিয়ে দেয় (পর্ব ৬২): nondeterminism “আছে” প্রশ্নে শক্তিশালী, “সব” প্রশ্নে নয়, আর এই অসমতা দূর করা যায় কি না, complexity-তে অনেক জায়গায় একটি খোলা প্রশ্ন। CFL-এর ক্ষেত্রে অবশ্য উত্তর জানা: অসমতা সত্যিই আছে, কারণ complement-এ closure নেই প্রমাণিত।

Deterministic যন্ত্রে এই অসমতা নেই। একটি পথ, তাই accept আর reject অদলবদল করলেই complement, শুধু খেয়াল রাখতে হয় যন্ত্র যেন সবসময় থামে। এই কারণেই DCFL complement-এ বদ্ধ, যদিও union-এ নয়।

মূল উপলব্ধি: Nondeterminism “একটি সাক্ষী আছে” ধরনের দাবিতে দক্ষ, “কোনো সাক্ষী নেই” দাবিতে নয়। CFL-এর complement-এ closure না থাকা এই অসমতার একটি প্রমাণিত, স্পষ্ট উদাহরণ।

প্র ০৩Emptiness decidable, কিন্তু universality undecidable. দুটিই “language কত বড়” প্রশ্ন, তবু একটি সহজ আর একটি অসম্ভব কেন?

Emptiness প্রশ্নটি হলো “কোনো string আছে কি?” এর উত্তর “হ্যাঁ” হলে একটি সাক্ষী আছে, আর সাক্ষী খুঁজতে grammar নিজেই পথ দেখায়: নিচ থেকে ওপরে generating variable চিহ্নিত করা। চিহ্নিত করার কাজটি একটি monotone প্রক্রিয়া, সেট শুধু বাড়ে, আর variable সসীম; তাই এটি থামবেই। এমনকি ছোট witness-ও বের হয়ে আসে, যেমন অংশ ৬-এর কোডে ab.

Universality প্রশ্নটি হলো “প্রতিটি string আছে কি?” এর “না” উত্তরের সাক্ষী একটি অনুপস্থিত string, আর সেটি খুঁজে পেলে CYK দিয়ে যাচাই করা যায়; তাই “না” উত্তর একসময় পাওয়া যায় (প্রশ্নটির complement recognizable). কিন্তু “হ্যাঁ” উত্তরের কোনো সসীম সাক্ষী নেই: অসীম সংখ্যক string-এর প্রত্যেকটি আছে, এটি কোনো সসীম পরীক্ষায় দেখানো যায় না, যদি না complement নিয়ে emptiness-এ ফেরা যায়। Regular language-এ ঠিক সেটিই করা হয় (পর্ব ২০): complement DFA, তারপর emptiness. CFL-এ complement নেই, আর অংশ ৭-এর computation-history যুক্তি দেখায় যে এই ফাঁক কোনো চতুর algorithm দিয়েও ভরানো যায় না।

Computation-history কৌশলটি বিশেষভাবে সুন্দর। একটি Turing machine-এর পুরো গণনার “ভুল” রূপগুলো CFG দিয়ে বর্ণনা করা যায়, কারণ ভুল খুঁজতে একটিই জায়গায় দুটি পরপর configuration মেলাতে হয়, আর সেটি stack পারে। সঠিক রূপ বর্ণনা করতে প্রতিটি জোড়া মেলাতে হয়, যা পারে না। তাই “সব string-ই ভুল history” মানে “কোনো সঠিক গ্রহণকারী history নেই”, অর্থাৎ যন্ত্রটি গ্রহণ করে না। Universality-র algorithm থাকলে ATM-এর algorithm থাকত।

বাজারঘরের ভাষায়: “আমাদের query-ভাষায় অন্তত একটি বৈধ query আছে কি?” program দিয়ে নিশ্চিত বলা যায়। “প্রতিটি সম্ভাব্য অক্ষর-ক্রম কি বৈধ query?” সাধারণভাবে বলা যায় না, যদিও কোনো নির্দিষ্ট ক্ষেত্রে মানুষ প্রমাণ লিখতে পারে।

মূল উপলব্ধি: “আছে” প্রশ্নে একটি সসীম সাক্ষী যথেষ্ট, “সব” প্রশ্নে লাগে complement. CFL-এর complement-এ closure না থাকাই emptiness আর universality-কে দুই আলাদা জগতে রাখে।

প্র ০৪Grammar ambiguous কি না undecidable, অথচ parser generator প্রতিদিন grammar নিয়ে কাজ করে। বাস্তবের টুল এই সীমা কীভাবে সামলায়?

পর্ব ২৭-এ দেখেছেন, ambiguous grammar একই string-কে দুই অর্থে পড়ে, যেমন 2 + 3 ∗ 4-এর দুটি মান। একটি সাধারণ algorithm থাকলে সেটি প্রতিটি grammar-এ বলত, এমন দ্ব্যর্থতা আছে কি না। পর্ব ৫৪-এ Post correspondence problem থেকে reduction দিয়ে দেখবেন, এমন algorithm থাকতে পারে না: প্রতিটি PCP-instance থেকে একটি grammar বানানো যায়, যা ambiguous ঠিক তখন, যখন instance-টির সমাধান আছে।

টুলগুলো তাই উল্টো দিক থেকে কাজ করে: “ambiguous কি না” না জিজ্ঞেস করে একটি কঠোর, সহজে যাচাইযোগ্য শর্ত পরীক্ষা করে। LR(1) বা LALR(1) parser-টেবিল বানাতে গিয়ে কোনো conflict না এলে grammar নিশ্চিতভাবে unambiguous (পর্ব ৩৯)। Conflict এলে grammar ambiguous হতেও পারে, না-ও হতে পারে; টুল শুধু বলে “এই শর্তে আমি নিশ্চিত হতে পারছি না”, আর প্রকৌশলী precedence নিয়ম বা grammar নতুন করে লিখে সমাধান করেন। অর্থাৎ undecidable প্রশ্নের জায়গায় একটি decidable কিন্তু অসম্পূর্ণ প্রশ্ন বসানো হয়।

দ্বিতীয় পথ হলো সীমিত খোঁজ: দৈর্ঘ্য n পর্যন্ত সব string-এর parse গুনে দেখা, দুটি parse পাওয়া যায় কি না। গবেষণায় এমন ambiguity detector আছে, যারা ছোট দৈর্ঘ্যে দ্ব্যর্থতা খুঁজে বের করে। খুঁজে পেলে সেটি নিশ্চিত প্রমাণ (একটি string, দুটি tree); না পেলে কিছুই প্রমাণ হয় না, ঠিক অংশ ৭-এর equivalence-খোঁজার মতো।

তৃতীয় পথ হলো ambiguity মেনে নেওয়া: Earley বা GLR parser (পর্ব ৪১) সব parse একসঙ্গে রাখে, আর পরে অন্য নিয়মে একটি বেছে নেয়। প্রাকৃতিক ভাষার parsing-এ এটিই স্বাভাবিক, কারণ মানুষের ভাষা নিজেই ambiguous.

মূল উপলব্ধি: Undecidability মানে সব grammar-এর জন্য একটি সর্বজনীন algorithm নেই, কাজ বন্ধ নয়। বাস্তবের টুল যথেষ্ট শর্ত, সীমিত খোঁজ আর ambiguity-সহিষ্ণু parsing দিয়ে কাজ চালায়, আর জানে কোন উত্তর প্রমাণ আর কোনটি শুধু ইঙ্গিত।

প্র ০৫Regular language-এ equivalence decidable, deterministic CFL-এও decidable (Sénizergues), কিন্তু সাধারণ CFL-এ নয়। এই সীমারেখা কোথায় আর কেন?

Regular language-এ equivalence-এর algorithm সরল: দুটি DFA-র symmetric difference-এর product বানিয়ে emptiness দেখা (পর্ব ২০), অথবা দুটিকে minimise করে isomorphic কি না দেখা। দুটি কাজই complement আর ছেদের closure-এর ওপর দাঁড়িয়ে, যা DFA-তে সস্তা।

সাধারণ CFL-এ দুটি closure-ই নেই, আর অংশ ৭ দেখায় যে এটি শুধু একটি পদ্ধতির ব্যর্থতা নয়: কোনো পদ্ধতিই কাজ করবে না, কারণ universality নিজেই undecidable. Deterministic CFL মাঝখানে বসে। DCFL complement-এ বদ্ধ, তাই universality সহজ: complement-এর DPDA বানিয়ে emptiness দেখা। কিন্তু ছেদে বদ্ধ নয়, তাই symmetric difference-এর পথ বন্ধ। তবু দুটি DPDA-র equivalence decidable কি না, এই প্রশ্নটি প্রায় তিন দশক খোলা ছিল বলে পরিচিত, আর ১৯৯৭ সালের দিকে Géraud Sénizergues এর ইতিবাচক উত্তর দেন। প্রমাণটি দীর্ঘ আর কৌশলী; পরে Colin Stirling-সহ কয়েকজন এর সরল রূপ আর সময়ের সীমা নিয়ে কাজ করেন বলে উল্লেখ পাওয়া যায়। এই কাজের জন্য Sénizergues ২০০২ সালে Gödel Prize পান।

সীমারেখাটি তাই nondeterminism-এর ওপর। একটি DPDA প্রতিটি input-এ একটিই পথে চলে, তাই দুটি DPDA-কে পাশাপাশি “একই ছন্দে” তুলনা করার একটি কাঠামো আছে, যদিও stack দুটি আলাদা। NPDA-তে এক string-এর অসংখ্য পথ, আর computation-history কৌশল দেখায় যে এই স্বাধীনতা দিয়ে Turing machine-এর গণনাকেই অনুকরণ করা যায়। মাঝের আরও কিছু শ্রেণি নিয়ে গবেষণা চলছে, যেমন কিছু সীমিত ধরনের counter বা visibly pushdown automaton, যেখানে push আর pop input চিহ্ন দেখেই ঠিক হয়; শেষেরটির ক্ষেত্রে ছেদ, complement আর equivalence সবই decidable বলে পরিচিত, আর XML-এর মতো নেস্টেড ডেটা যাচাইয়ে এটি কাজে লাগে।

বাস্তবের জন্য শিক্ষা: কোনো grammar-কে deterministic আকারে রাখতে পারলে (যেমন LR(1)) তত্ত্বের দিক থেকেও অনেক প্রশ্ন সহজ হয়, আর parser-ও দ্রুত চলে।

মূল উপলব্ধি: Equivalence-এর decidability-র সীমা closure property আর nondeterminism-এর ওপর নির্ভর করে। Regular-এ সহজ, DCFL-এ কঠিন কিন্তু সম্ভব, আর সাধারণ CFL-এ অসম্ভব প্রমাণিত।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। অংশ ৩ আর ৬-এর Python ব্লকের function দিয়ে নিজের উত্তরও যাচাই করতে পারেন।

  1. নকশা: P হলো anbn-এর PDA: q1 থেকে q2-তে ε, ε → $; q2-তে a, ε → a; q2 থেকে q3-তে b, a → ε; q3-তে b, a → ε; q3 থেকে q4-এ ε, $ → ε; শুরু q1, accepting {q1, q4}. D হলো “a-এর সংখ্যা জোড়”-এর DFA (state e আর o, শুরু ও accepting e; a-তে অদলবদল, b-তে একই)। (ক) P × D-এর reachable state আর move-এর তালিকা দিন। (খ) L(P × D) কী? তার একটি CFG দিন।

    (ক) শুরু q1·e থেকে reachable state সাতটি: q1·e, q2·e, q2·o, q3·e, q3·o, q4·e, q4·o. Move নয়টি: q1·e →[ε, ε → $] q2·e; q2·e →[a, ε → a] q2·o; q2·o →[a, ε → a] q2·e; q2·e →[b, a → ε] q3·e; q2·o →[b, a → ε] q3·o; q3·e →[b, a → ε] q3·e; q3·o →[b, a → ε] q3·o; q3·e →[ε, $ → ε] q4·e; q3·o →[ε, $ → ε] q4·o. b পড়লে D-এর state বদলায় না, তাই q3-এর move-গুলো e বা o-তেই থাকে। Accepting: {q1, q4} × {e} = {q1·e, q4·e}.

    (খ) L(P) ∩ L(D) = {anbn : n জোড়} = {a2kb2k : k ≥ 0}. CFG: S → aaSbb ∣ ε. Scratch-এ অংশ ৩-এর product_pda আর run দিয়ে বানানো product দৈর্ঘ্য ≤ 10-এর সব 2047টি string-এ এই language-এর সঙ্গে মিলেছে, আর reachable state ৭টি ও move ৯টি এসেছে।

  2. প্রমাণ: Σ = {a, b, c}-এর ওপর L3 = {w : w-এ a, b আর c সমান সংখ্যক}. Closure property আর {anbncn}-এর non-CFL হওয়া ব্যবহার করে প্রমাণ করুন যে L3 CFL নয়। তারপর বলুন, L3-এর complement CFL কি না, এই যুক্তি থেকে কিছু বলা যায় কি না।
    1. ধরুন L3 CFL. — contradiction-এর জন্য
    2. a∗b∗c∗ একটি regex-এর language, তাই regular. — পর্ব ১৩
    3. উপপাদ্য ৩.১ অনুযায়ী L3 ∩ a∗b∗c∗ একটি CFL. — CFL ∩ regular
    4. a∗b∗c∗-এর string aibjck; এটি L3-এ থাকে ঠিক তখন, যখন i = j = k. তাই ছেদ = {anbncn}. — L3-এর সংজ্ঞা
    5. কিন্তু {anbncn} CFL নয় (পর্ব ৩৬)। বিরোধ, তাই L3 CFL নয়। ∎

    Complement সম্পর্কে এই যুক্তি কিছুই বলে না: CFL-এর শ্রেণি complement-এ বদ্ধ নয়, তাই “L3 CFL নয়” থেকে L̄3 নিয়ে কোনো সিদ্ধান্ত আসে না। (আসলে L̄3 একটি CFL: #a ≠ #b, বা #b ≠ #c, এই দুটি CFL-এর union. কিন্তু সেটি আলাদা প্রমাণ।) Scratch-এ দৈর্ঘ্য ≤ 9 পর্যন্ত L3 ∩ a∗b∗c∗-এ ঠিক ε, abc, aabbcc, aaabbbccc এসেছে।

  3. প্রমাণের ভুল ধরুন: দাবি: “CFL intersection-এ বদ্ধ।” প্রমাণ: “P1 আর P2 দুটি PDA. নতুন PDA-র state (q1, q2), শুরু (শুরু1, শুরু2), accepting F1 × F2. একটি চিহ্ন a পড়লে P1-এর move a, x → y আর P2-এর move a, x′ → y′ একসঙ্গে খাটে: x আর x′ দুটিই একই stack থেকে তুলি, y আর y′ দুটিই রাখি। PDA × DFA-র মতোই, তাই ∎” ভুলটি কোথায়? একটি পাল্টা-উদাহরণ দিন।

    ভুল ধাপ: “x আর x′ দুটিই একই stack থেকে তুলি”। দুই PDA-র stack-এর বিষয়বস্তু আলাদা, আর একটি stack-এ মেশালে কোনো PDA-ই তার নিজের ওপরের চিহ্ন দেখে না: P1-এর চিহ্নের ওপর P2-এর চিহ্ন বসে থাকে। আর একটি move-এ দুটি চিহ্ন তোলা বা রাখা Sipser-এর সংজ্ঞায় সম্ভবও নয় (Γε-এর একটি উপাদান)। PDA × DFA-তে এই সমস্যা ছিল না, কারণ DFA-র কোনো stack নেই।

    পাল্টা-উদাহরণ: P1 চেনে {anbncm}, P2 চেনে {ambncn}. দাবি সত্য হলে ছেদ {anbncn} CFL হতো, যা পর্ব ৩৬ অনুযায়ী মিথ্যা। তাই দাবিটি নিজেই মিথ্যা, শুধু প্রমাণ নয়। অংশ ৪-এর Python ব্লক দৈর্ঘ্য ≤ 12 পর্যন্ত এই ছেদ হিসাব করেছে।

  4. Trace আর আউটপুট অনুমান: G: S → AB ∣ CA, A → a, B → BC ∣ AB, C → aB ∣ b. হাতে হিসাব করুন: (ক) generating variable কোনগুলো, আর প্রতিটির সবচেয়ে ছোট witness; (খ) ছাঁটাইয়ের পর grammar; (গ) ছাঁটাইয়ের আগে আর পরে কোন variable cycle-এ; (ঘ) L(G) সসীম কি না, আর পুরো language.

    (ক) প্রথম দফায় A (A → a) আর C (C → b) চিহ্নিত। দ্বিতীয় দফায় S → CA-র দুটি চিহ্নই চিহ্নিত, তাই S, witness ba. B-এর দুটি নিয়মেই (BC, AB) ডান দিকে B নিজে, তাই B কখনো চিহ্নিত হয় না। Generating: A (a), C (b), S (ba).

    (খ) B আর B-যুক্ত সব নিয়ম (S → AB, C → aB) মুছে: S → CA, A → a, C → b. সবাই S থেকে reachable.

    (গ) আগে: B → BC থেকে B → B, আর C → aB ও B → BC থেকে C → B → C; তাই B আর C cycle-এ। পরে: তীর শুধু S → C, S → A; কোনো cycle নেই।

    (ঘ) সসীম, L(G) = {ba}. অংশ ৬-এর কোডে generating, trim, on_cycle চালিয়ে scratch-এ ঠিক এগুলোই এসেছে: witness {A: a, C: b, S: ba}, raw cycle [B, C], ছাঁটা grammar-এ cycle নেই, আর language {ba}. (G পুরোপুরি CNF-এ নয়, C → aB-র জন্য; কিন্তু ছাঁটাইয়ের পর যা থাকে তা CNF-এর রূপেই, তাই সিদ্ধান্ত নিরাপদ।)

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমএকটি CFG-এর language সসীম কি না ঠিক করার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Grammar-কে Chomsky normal form-এ আনা
  2. Non-generating variable আর তাদের নিয়ম মুছে ফেলা
  3. Start symbol থেকে unreachable variable মুছে ফেলা
  4. প্রতিটি নিয়ম A → BC থেকে A → B আর A → C তীর দিয়ে variable graph বানানো
  5. Graph-এ cycle থাকলে অসীম, না থাকলে সসীম বলা

Context-free language-এর শ্রেণি নিচের কোন operation-এ বদ্ধ নয়?

  • Reversal
  • একটি regular language-এর সঙ্গে ছেদ
  • Complement
  • Inverse homomorphism

L একটি context-free language আর R একটি regular language. নিচের কোনটি সবসময় context-free?

  • R ∖ L
  • L ∖ R
  • L ∩ L′, যেখানে L′ আরেকটি CFL
  • L̄, L-এর complement

Input একটি context-free grammar G (বা দুটি, G1 আর G2). নিচের কোন প্রশ্নটি decidable?

  • L(G) = Σ∗ কি না
  • L(G) = ∅ কি না
  • G ambiguous কি না
  • L(G1) = L(G2) কি না

Grammar: S → AB ∣ SD, A → a, B → b, D → DD. ছাঁটাইয়ের আগের variable graph-এ S → S আর D → D cycle আছে। L(G) কী?

  • অসীম, কারণ graph-এ cycle আছে
  • সসীম, ঠিক {ab}
  • ফাঁকা
  • সিদ্ধান্ত নেওয়া সম্ভব নয়, কারণ প্রশ্নটি undecidable

একটি PDA আর একটি DFA-র product দিয়ে L(P) ∩ L(D)-এর PDA বানানো যায়, কিন্তু দুটি PDA-র product দিয়ে L(P1) ∩ L(P2)-এর PDA সাধারণভাবে বানানো যায় না। মূল কারণ কী?

  • দুটি PDA-র state-জোড়া অসীম সংখ্যক হয়ে যায়
  • PDA-তে ε-move থাকে, DFA-তে থাকে না
  • PDA nondeterministic, DFA deterministic
  • প্রতিটি PDA-র নিজের stack লাগে, আর দুটি stack এক stack-এ ধরে রাখা যায় না

Σ = {a, b, c}-এর ওপর L = {w : w-এ a, b আর c সমান সংখ্যক}. Closure দিয়ে L CFL নয় প্রমাণ করতে L-এর সঙ্গে কোন language-এর ছেদ নেওয়া সঠিক কৌশল?

  • a∗b∗c∗
  • {anbncm : n, m ≥ 0}
  • Σ∗
  • (abc)∗

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. CFL union, concatenation, star, reversal, homomorphism, substitution, inverse homomorphism আর regular-এর সঙ্গে ছেদে বদ্ধ; প্রথমগুলো grammar-নির্মাণ, শেষ দুটি PDA-নির্মাণ।
  2. PDA × DFA: state (q, s), accepting F × F′; চিহ্ন পড়লে দুজনেই এগোয়, ε-move-এ DFA দাঁড়িয়ে থাকে, stack একটিই।
  3. দুটি CFL-এর ছেদ আর complement-এ closure নেই: {anbncm} ∩ {ambncn} = {anbncn}; non-CFL প্রমাণে ছাঁকনি সবসময় regular.
  4. Decidable: membership (CYK), emptiness (S generating কি না), finiteness (CNF, ছাঁটাই, তারপর variable graph-এ cycle).
  5. Undecidable: universality, equivalence, inclusion, দুটি CFL-এর ছেদ ফাঁকা কি না, ambiguity, regularity; বাস্তবে তাই পার্থক্য খোঁজা আর পরীক্ষা, “মিলেছে” মানে প্রমাণ নয়।

পরের পর্বে: মডিউল ৭ শুরু: বাস্তবে parsing. প্রথমে top-down parsing: LL(1) grammar, FIRST আর FOLLOW সেট, parse টেবিল, আর বাজারঘরের query-ভাষার জন্য একটি recursive-descent parser.

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান