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

Deterministic PDA আর deterministic CFL

Deterministic Pushdown Automata — Definition, DCFLs, Why wwᴿ Needs Nondeterminism, Closure, Unambiguity, LR(k) and Equivalence

Taught in Bangla, this lesson defines deterministic pushdown automata, where at most one move applies in every configuration, and shows how to spot and fix conflicting moves. It builds DPDAs for wcwᴿ, aⁿbⁿ and balanced brackets, proves with the two-copy argument that wwᴿ is not deterministic context-free, and shows DCFLs are closed under complement but not union or intersection. It links DCFLs to unambiguous grammars and LR(k) parsing, with in-page Python (Pyodide) checks and a real automata-lib DPDA run.

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

  • DPDA-র সঠিক সংজ্ঞা, move-এর সংঘাত চেনা, আর একটি nondeterministic নকশাকে deterministic বানানো
  • wcwR, anbn আর সুষম বন্ধনীর DPDA, আর Python-এ deterministic run ও সংঘাত-পরীক্ষা
  • দুই কপির কৌশলে প্রমাণ যে wwR আর {anbn} ∪ {anb2n} DCFL নয়
  • DCFL-এর complement নির্মাণ ধাপে ধাপে, আর কেন union ও intersection-এ বদ্ধতা নেই
  • DCFL, unambiguous grammar, LR(k) parsing আর DPDA-র সমতার ইতিহাস

১ · অনুমান ছাড়া চলা — কেন deterministic PDA

পর্ব ৩২-এ দেখেছেন, PDA সংজ্ঞাতেই nondeterministic: একই অবস্থায় একাধিক move থাকতে পারে, আর অন্তত একটি পথ গ্রহণে শেষ হলেই string গৃহীত। wwR-এর PDA প্রতিটি অবস্থানে “মাঝখান কি এখানে?” অনুমান করত। গাণিতিক যন্ত্র হিসেবে এটি চমৎকার, কিন্তু একটি বাস্তব program-কে সব পথ একসঙ্গে চালাতে হলে সময় আর স্মৃতি দুটিই বাড়ে।

ধরুন একজন রিকশাচালক অচেনা এলাকায় যাত্রী নিয়ে যাচ্ছেন, কোনো মোড়ে কোনো সাইনবোর্ড নেই। প্রতিটি মোড়ে তাঁকে অনুমান করতে হয়, ভুল হলে ফিরে আসতে হয়। এখন ভাবুন প্রতিটি মোড়ে একটি স্পষ্ট সাইনবোর্ড আছে: “বাজার বাঁয়ে”. তখন তিনি কখনো থামেন না, পেছনেও ফেরেন না, রাস্তার দৈর্ঘ্যের সমান সময়েই পৌঁছে যান। Deterministic PDA এমন রাস্তার চালক: প্রতিটি মুহূর্তে ঠিক কী করতে হবে, তা বর্তমান state, পরের input চিহ্ন আর stack-এর ওপরের চিহ্ন থেকেই নিশ্চিতভাবে জানা যায়।

wcwR-এ মাঝের c হলো সেই সাইনবোর্ড: c দেখলেই যন্ত্র জানে push শেষ, এবার মেলানো। wwR-এ কোনো সাইনবোর্ড নেই। প্রশ্নটি তাই গভীর: সাইনবোর্ড ছাড়া, একবার বাঁ থেকে ডানে পড়ে, শুধু একটি stack দিয়ে, কোনো চতুর deterministic যন্ত্র কি wwR চিনতে পারে? উত্তর “না”, আর তা প্রমাণ করা এই পর্বের একটি প্রধান কাজ। এর ফল হলো পর্ব ১০-এর পরিস্থিতির ঠিক উল্টো: সেখানে প্রতিটি NFA-র সমান একটি DFA ছিল, এখানে nondeterminism সত্যিই ক্ষমতা বাড়ায়।

ব্যবহারিক দিকটিও গুরুত্বপূর্ণ। বাজারঘরের order-query ভাষা, যেমন FIND order WHERE ( amount >= 1000 AND district = "Dhaka" ), প্রতিদিন হাজারবার parse হয়। এমন parser input-এর দৈর্ঘ্যের রৈখিক সময়ে চলুক, এটিই কাম্য, আর তার জন্য ভাষাটিকে deterministic রাখতে হয়। প্রায় সব compiler-এর parser, LL আর LR পরিবার (পর্ব ৩৮–৩৯), আসলে একটি deterministic PDA-রই রূপ।

২ · DPDA-র সংজ্ঞা — প্রতিটি অবস্থায় বড়জোর একটি move

পর্ব ৩২-এর রীতি থাকছে: P = (Q, Σ, Γ, δ, q0, F), δ: Q × Σε × Γε → P(Q × Γε), transition “a, x → y” মানে a পড়ে, ওপরের x তুলে, y রাখা; প্রথম move-এ তলার চিহ্ন $ push করা হয়। Configuration (q, w, γ), stack-এর ওপর বাঁয়ে। Deterministic হওয়ার শর্ত হলো: কোনো configuration-এ দুটি আলাদা move একসঙ্গে খাটতে পারবে না।

সংজ্ঞা ২.১ (Deterministic PDA)

PDA P deterministic, যদি
১. প্রতিটি q, a, x-এর জন্য δ(q, a, x)-এ বড়জোর একটি উপাদান থাকে; আর
২. একই state q-এর দুটি আলাদা move (q, a, x) আর (q, b, y)-এর ক্ষেত্রে কখনো একসঙ্গে “a = b বা a = ε বা b = ε” এবং “x = y বা x = ε বা y = ε” সত্য না হয়।

যে language কোনো DPDA final state দিয়ে গ্রহণ করে, তাকে বলে deterministic context-free language (DCFL).

শর্ত ২-এর অর্থ কথায়: দুটি move-এর input অংশ “মিলতে পারে” যদি দুটি একই চিহ্ন পড়ে বা অন্তত একটি কিছুই না পড়ে (ε); stack অংশ মিলতে পারে যদি দুটি একই চিহ্ন তোলে বা অন্তত একটি কিছুই তোলে না। দুটিই মিলতে পারলে এমন configuration আছে, যেখানে দুটি move একসঙ্গে খাটে। সবচেয়ে সাধারণ সংঘাত হলো একটি ε-move আর একটি পড়ার move একই stack-অবস্থায়: যন্ত্র বুঝতে পারে না, এখন পড়বে নাকি না পড়ে এগোবে। লক্ষ করুন, ε-move নিষিদ্ধ নয়; শুধু এমন জায়গায় নিষিদ্ধ, যেখানে অন্য move-ও খাটে।

বইভেদে রূপ: Sipser (তৃতীয় সংস্করণ, অংশ ২.৪) শর্তটি আরও কঠোরভাবে লেখেন: প্রতিটি q ∈ Q, a ∈ Σ, x ∈ Γ-এর জন্য δ(q, a, x), δ(q, a, ε), δ(q, ε, x) আর δ(q, ε, ε)-এর ঠিক একটি ফাঁকা নয়। “ঠিক একটি” মানে যন্ত্র কখনো আটকায় না। Hopcroft–Motwani–Ullman (HMU) “বড়জোর একটি” রাখেন, অর্থাৎ যন্ত্র আটকে যেতে পারে, আর আটকানো মানে বাতিল। দুই রূপের ক্ষমতা সমান: অনুপস্থিত move-গুলো একটি dead state-এ পাঠালেই “বড়জোর একটি” থেকে “ঠিক একটি” হয় (অংশ ৫-এ এটি লাগবে)। এই পর্বের Python কোড “বড়জোর একটি” রূপ মানে।

গ্রহণের নিয়ম সাধারণ PDA-র মতোই: (q0, w, ε) ⊢∗ (f, ε, γ) কোনো f ∈ F-এর জন্য। পার্থক্য হলো, এখন computation একটিই। তাই নিয়মটি দাঁড়ায়: input পুরো পড়ার পরে যন্ত্র ε-move দিয়ে আরও কিছু ধাপ চলতে পারে, আর এই শেষ অংশে কোনো এক মুহূর্তে F-এর state-এ থাকলেই w গৃহীত। এই সূক্ষ্মতাটি অংশ ৫-এ complement বানানোর সময় বড় ভূমিকা নেবে।

প্রথম উদাহরণ wcwR = {wcwR : w ∈ {a, b}∗}, অর্থাৎ c, aca, bcb, abcba, …. পর্ব ৩২-এর wwR-এর যন্ত্র থেকে শুধু অনুমানের তীরটি বদলান: “ε, ε → ε”-এর জায়গায় “c, ε → ε”.

D1: wcwR-এর DPDA

q2-তে push, c পড়লে q3-তে, q3-তে মিলিয়ে pop, $ দেখে q4. কোনো তীর অনুমান করে না।

DPDA D1 for w c w^R q1q2q3q4 ε, ε → $ a, ε → a b, ε → b ε, $ → ε a, a → ε b, b → ε c, ε → ε সাইনবোর্ড c
ছবি ৩৫.১ — সবুজ তীরটি পর্ব ৩২-এর অনুমানের তীরের জায়গা নিয়েছে। q2-তে তিনটি move-ই আলাদা চিহ্ন পড়ে (a, b, c), q3-এর ε-move শুধু $ ওপরে থাকলে খাটে আর অন্য দুটি move a বা b ওপরে চায়: কোথাও সংঘাত নেই।

সংজ্ঞা ২.১ দিয়ে মিলিয়ে দেখুন। q1-এ একটিই move. q2-এর তিনটি move-এর input অংশ a, b, c: জোড়ায় জোড়ায় আলাদা, কোনোটি ε নয়, তাই শর্ত ২-এর প্রথম অংশই ভাঙে। q3-এ (a, a), (b, b) আর (ε, $): শেষটির input ε, কিন্তু stack অংশ $ বনাম a বা b, মেলে না। অতএব D1 একটি DPDA. নিচের stepper D1-কে abcba দেয়; প্রতিটি ধাপে ঠিক একটি move খাটে।

1q1 → q2 : ε, ε → $2q2 → q2 : a, ε → a3q2 → q2 : b, ε → b4q2 → q3 : c, ε → ε5q3 : a, a → ε ; b, b → ε6q3 → q4 : ε, $ → ε
এই ধাপের configuration
(state, বাকি, stack)
এখন খাটে এমন move
  1. শুরু। (q1, abcba, ε). q1-এ একটিই move, কিছু না পড়ে $ বসানো। এখানে পছন্দের কোনো সুযোগ নেই।
  2. $ বসল। (q2, abcba, $). পরের চিহ্ন a, তাই q2-এর তিনটি move-এর মধ্যে শুধু “a, ε → a” খাটে।
  3. a জমা। Stack a$. পরের চিহ্ন b: শুধু “b, ε → b”.
  4. b জমা। Stack ba$, ওপরে b. পরের চিহ্ন c: শুধু “c, ε → ε”. পর্ব ৩২-এর wwR-যন্ত্রে এই জায়গায় দুটি পথ ছিল (push চালানো, নাকি অনুমান); এখানে c নিজেই বলে দেয়।
  5. মেলানো শুরু। (q3, ba, ba$). ওপরে b, পরের চিহ্ন b: শুধু “b, b → ε”. “ε, $ → ε” খাটে না, কারণ ওপরে $ নেই।
  6. আবার মিল। (q3, a, a$) থেকে “a, a → ε” দিয়ে (q3, ε, $).
  7. $ ওপরে। Input শেষ, ওপরে $: একমাত্র move “ε, $ → ε”, যা q4-এ নেয়।
  8. গ্রহণ। (q4, ε, ε): input শেষ আর q4 ∈ F, তাই abcba ∈ L(D1). মোট ৭টি move, সাধারণভাবে |w| + 2টি: প্রতিটি চিহ্নে একটি, আর $ বসানো ও তোলায় দুটি। Computation-টি রৈখিক, কোনো শাখা নেই।

৩ · আরও DPDA — anbn, সুষম বন্ধনী আর সংঘাত সারানো

anbn. পর্ব ৩২-এর P1 (q1 → q2: ε, ε → $; q2: a, ε → a; q2 → q3: b, a → ε; q3: b, a → ε; q3 → q4: ε, $ → ε; F = {q1, q4}) আসলে আগে থেকেই deterministic. q2-তে input অংশ a আর b, আলাদা; q3-তে (b, a) আর (ε, $), stack অংশ আলাদা। তাই anbn একটি DCFL.

সুষম বন্ধনী (BAL). পর্ব ৩২-এর BAL-যন্ত্রে q2-এর move ছিল “(, ε → (”, “), ( → ε” আর “ε, $ → ε”. প্রথম আর তৃতীয়টি মিলিয়ে দেখুন: input অংশ “(” বনাম ε, মিলতে পারে; stack অংশ ε বনাম $, মিলতে পারে। অর্থাৎ (q2, (), $)-এর মতো configuration-এ দুটিই খাটে: “(” push করা, অথবা $ তুলে q3-তে যাওয়া। দ্বিতীয় পথটি input বাকি রেখে মরে যায়, তাই language-এ ক্ষতি হয়নি, কিন্তু যন্ত্রটি সংজ্ঞা অনুযায়ী deterministic নয়।

সারানোর কৌশল: যে তথ্য ε-move “অনুমান” করছিল, তা state-এ রাখুন। দুটি state: z মানে “এখন কোনো বন্ধনী খোলা নেই” (accept state), n মানে “ভেতরে আছি”। আর push-এর move-এ stack-এর ওপরের চিহ্ন স্পষ্ট লিখুন, যাতে ε-move-এর সঙ্গে মিল না হয়:

stateপড়া, তোলা → রাখাপরের stateঅর্থ
s (start)ε, ε → $zতলার চিহ্ন
z (accept)(, $ → ($nপ্রথম খোলা বন্ধনী
n(, ( → ((nআরও গভীরে
n), ( → εnএকটি বন্ধ হলো
nε, $ → $zসব বন্ধ, z-এ ফেরা

“(, $ → ($” মানে $ তুলে “($” রাখা, অর্থাৎ $-এর ওপরে একটি “(”; পর্ব ৩২-এর মতো এটি দুটি চিহ্ন রাখার সংক্ষিপ্ত লেখা, আসল রূপে একটি বাড়তি state লাগে। এবার n-এর তিনটি move: (“(”, “(”), (“)”, “(”) আর (ε, $). ε-move-টি $ চায়, অন্য দুটি “(”, তাই সংঘাত নেই। z-এ “)” পড়ার কোনো move নেই: খোলা বন্ধনী নেই অথচ “)” এলে যন্ত্র আটকে যায়, যা ঠিক যা চাই। নিচের ব্লক সংজ্ঞা ২.১-এর শর্ত ২ সরাসরি পরীক্ষা করে, deterministic run চালায়, আর ফল সংজ্ঞার সঙ্গে brute force-এ মেলায়।

from itertools import product, accumulate
def conflicts(P):           # pairs of moves that can fire in one configuration
    ms = list(P["d"])
    return [(m, n) for i, m in enumerate(ms) for n in ms[i + 1:] if m[0] == n[0]
            and (m[1] == n[1] or "" in (m[1], n[1]))
            and (m[2] == n[2] or "" in (m[2], n[2]))]
def run(P, w, limit=1000):  # the ONE computation; key (state, read, pop)
    q, i, st, acc, steps = P["q0"], 0, "", False, 0
    for steps in range(limit):
        acc = acc or (i == len(w) and q in P["F"])
        m = [k for k in P["d"] if k[0] == q and w.startswith(k[1], i)
             and st.startswith(k[2])]
        if not m: break                         # stuck: the run ends here
        (r, y), (_, a, x) = P["d"][m[0]], m[0]
        q, i, st = r, i + len(a), y + st[len(x):]
    return acc, steps
WCW = {"q0": "q1", "F": {"q4"}, "d": {("q1", "", ""): ("q2", "$"),
    ("q2", "a", ""): ("q2", "a"), ("q2", "b", ""): ("q2", "b"),
    ("q2", "c", ""): ("q3", ""), ("q3", "a", "a"): ("q3", ""),   # c = middle
    ("q3", "b", "b"): ("q3", ""), ("q3", "", "$"): ("q4", "")}}
BAL32 = {"q0": "q1", "F": {"q3"}, "d": {("q1", "", ""): ("q2", "$"),
    ("q2", "(", ""): ("q2", "("), ("q2", ")", "("): ("q2", ""),
    ("q2", "", "$"): ("q3", "")}}
BALD = {"q0": "s", "F": {"z"}, "d": {("s", "", ""): ("z", "$"),
    ("z", "(", "$"): ("n", "($"), ("n", "(", "("): ("n", "(("),
    ("n", ")", "("): ("n", ""), ("n", "", "$"): ("z", "$")}}
for name, P in [("WCW", WCW), ("BAL32", BAL32), ("BALD", BALD)]: print(f"{name:5} conflicts: {conflicts(P) or 'none'}")
bal = lambda w: min(accumulate(1 if c == "(" else -1 for c in "(" + w)) >= 1 \
                and w.count("(") == w.count(")")
wcw = lambda w: w.count("c") == 1 and w.split("c")[0] == w.split("c")[1][::-1]
for name, P, sig, inL in [("WCW", WCW, "abc", wcw), ("BALD", BALD, "()", bal)]:
    words = ["".join(t) for k in range(9) for t in product(sig, repeat=k)]
    bad = [w for w in words if run(P, w)[0] != inL(w)]
    print(f"{name}: {len(words)} strings, {sum(run(P, w)[0] for w in words)}"
          f" accepted, disagreements {len(bad)}")

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

WCW   conflicts: none
BAL32 conflicts: [(('q2', '(', ''), ('q2', '', '$'))]
BALD  conflicts: none
WCW: 9841 strings, 15 accepted, disagreements 0
BALD: 511 strings, 23 accepted, disagreements 0

conflicts হুবহু সংজ্ঞা ২.১-এর শর্ত ২: একই state, input অংশ সমান বা একটি "" (ε), stack অংশ সমান বা একটি "". পর্ব ৩২-এর BAL-যন্ত্রে ঠিক একটি সংঘাত পাওয়া গেছে, (q2, “(”, ε) বনাম (q2, ε, $), যা ওপরে হাতে দেখেছেন; সারানো BALD-এ কোনো সংঘাত নেই। run কোনো BFS করে না: প্রতিটি ধাপে খাটে এমন move-এর তালিকা বড়জোর এক উপাদানের, তাই সরাসরি এগোয়। তিন চিহ্নের alphabet-এ দৈর্ঘ্য ৮ পর্যন্ত (39 − 1)/2 = 9841টি string-এ wcwR-এর যন্ত্র সংজ্ঞার সঙ্গে একমত; গৃহীত ১৫টি হলো |w| ≤ 3-এর 1 + 2 + 4 + 8টি w. BALD-এর ২৩টি সেই Catalan-সংখ্যার যোগফল, যা পর্ব ৩২-এ দেখেছেন। run-এর দ্বিতীয় ফল move-এর সংখ্যা: run(WCW, "abcba") চালালে (True, 7) আসে, stepper-এর মতোই, আর সংখ্যাটি input-এর দৈর্ঘ্যের রৈখিক।

একটি স্বাধীন library দিয়ে যাচাই। নিজের লেখা পরীক্ষকের ভুল ধরতে একই যন্ত্র automata-lib-এর DPDA class-এ চালানো হলো (MIT licence; কোনো network বা usage-reporting কোড নেই, source-এ খুঁজে দেখা হয়েছে)। পর্ব ৩২-এর মতো এই library HMU রীতি মানে: stack শুরুতে Z নিয়ে থাকে, প্রতিটি move ঠিক একটি চিহ্ন তোলে, আর তৈরি করার সময়ই class-টি পরীক্ষা করে যে একই state আর একই ওপরের চিহ্নে একটি ε-move আর একটি পড়ার move একসঙ্গে নেই। ডেস্কটপে uv দিয়ে বানানো একটি ছোট প্রকল্পে script-টির মূল অংশ:

from automata.pda.dpda import DPDA
from automata.pda.exceptions import NondeterminismError
push = {X: {"a": ("q0", ("a", X)), "b": ("q0", ("b", X)), "c": ("q1", X)}
        for X in "Zab"}
wcw = DPDA(states={"q0", "q1", "q2"}, input_symbols={"a", "b", "c"},
    stack_symbols={"Z", "a", "b"}, initial_state="q0",
    initial_stack_symbol="Z", final_states={"q2"}, acceptance_mode="final_state",
    transitions={"q0": {s: {X: push[X][s] for X in "Zab"} for s in "abc"},
                 "q1": {"a": {"a": ("q1", "")}, "b": {"b": ("q1", "")},
                        "": {"Z": ("q2", ("Z",))}}})
# ... brute force over all strings up to length 8, then a stepwise run
try:   # BAL the lesson-32 way: in q, "(" on top $ AND an ε-move on top $
    DPDA(..., transitions={"p": {"": {"$": ("q", ("$",))}},
         "q": {"(": {"$": ("q", ("(", "$")), "(": ("q", ("(", "("))},
               ")": {"(": ("q", "")}, "": {"$": ("f", ("$",))}}})
except NondeterminismError as e:
    print("BAL as in lesson 32 ->", type(e).__name__ + ":", e)

সত্যিকারের run (ডেস্কটপ, automata-lib 9.2.0, Python 3.12.13):

~/bazarghar-toc$ uv run python run_dpda.py
automata-lib 9.2.0
wcwR {'c': True, 'abcba': True, 'abcab': False, 'aacaa': True, 'ab': False}
wcwR: 9841 strings checked, 15 accepted, agree: True
   q0 abcba Z
   q0 bcba aZ
   q0 cba baZ
   q1 ba baZ
   q1 a aZ
   q1 ε Z
   q2 ε Z
BAL as in lesson 32 -> NondeterminismError: A symbol transition is adjacent to a lambda transition for this DPDA.

Library-ও ৯৮৪১টি string-এ সংজ্ঞার সঙ্গে একমত, গৃহীত ১৫টি, আমাদের ব্লকের মতোই। ধাপে ধাপে run-টি stepper-এর আটটি configuration-এর সঙ্গে মেলে, শুধু $-এর জায়গায় Z, আর শুরুতে Z আগে থেকেই থাকায় $ বসানোর ধাপটি নেই (stack এখানে ওপর বাঁয়ে সাজিয়ে ছাপা)। শেষ লাইনটি সবচেয়ে শিক্ষণীয়: পর্ব ৩২-এর BAL-যন্ত্রকে library DPDA হিসেবে মানতেই রাজি হয়নি। Error-বার্তার “lambda transition” মানে ε-move (কিছু বই ε-এর জায়গায় λ লেখে); একই state-এ, একই ওপরের চিহ্ন $-এ, একটি পড়ার move-এর “পাশে” একটি ε-move. এটি ঠিক আমাদের conflicts-এর পাওয়া সংঘাত।

৪ · wwR কেন DCFL নয় — দুই কপির কৌশল

প্রথমে স্বজ্ঞা। ধরুন একটি DPDA wwR চেনে আর input-এর শুরু anbban. এটি নিজেই একটি জোড় palindrome, তাই এটুকু পড়ার পরে যন্ত্রকে accept state-এ যেতে হবে, অর্থাৎ দ্বিতীয় an-কে প্রথমটির সঙ্গে মিলিয়ে দেখতে হবে। Stack-এ গোনা থাকলে মেলাতে সেটি তুলে ফেলতে হয়। কিন্তু input যদি চলতে থাকে, যেমন anbbanbban, তখন আবার n জানা দরকার। Nondeterministic যন্ত্র দুটি পথে দুটি কাজ করে; deterministic যন্ত্রের পথ একটিই, আর তুলে ফেলা stack ফেরে না। এই অনুভূতিকে কঠোর করতে একটি সুন্দর কৌশল আছে।

উপপাদ্য ৪.১

L = {wwR : w ∈ {a, b}∗} context-free, কিন্তু কোনো DPDA L গ্রহণ করে না। অর্থাৎ DCFL ⊊ CFL.

প্রমাণের রূপরেখা (দুই কপির কৌশল; একই ধাঁচ HMU আর Sipser-এর অনুশীলনীতে {anbn} ∪ {anb2n}-এর জন্য দেখা যায়):

  1. ধরুন একটি DPDA M-এর জন্য L(M) = L. — বিরোধের জন্য অনুমান
  2. যেকোনো u আর v-এর জন্য, M-এর uv-এর ওপর computation হলো u-এর ওপর computation-এর একটি সম্প্রসারণ। কারণ: পথ একটিই, আর u শেষ হওয়ার পরে যতক্ষণ ε-move খাটে ততক্ষণ পড়ার move খাটে না (সংজ্ঞা ২.১), তাই uv-এর run-ও u-এর run-এর সব ε-ধাপ হুবহু পেরোয়। ফলে u ∈ L(M) হলে uv-এর run u পড়ার পরে কোনো এক মুহূর্তে F-এর state-এ থাকে। — determinism
  3. একটি PDA M′ বানান: M-এর দুটি কপি। কপি ১ সাধারণ চিহ্ন a, b পড়ে, কপি ২ একই নিয়মে “চিহ্নিত” চিহ্ন â, b̂ পড়ে। কপি ১-এর কোনো accept state থেকে একটি ε-move কপি ২-এর একই state-এ যায়, stack অপরিবর্তিত। কপি ২-এর accept state-ই M′-এর accept state. — নির্মাণ
  4. ধাপ ২ অনুযায়ী L(M′) = {u v̂ : u ∈ L, uv ∈ L}, যেখানে v̂ হলো v-এর চিহ্নিত রূপ। M′ nondeterministic হতে পারে, কিন্তু PDA, তাই L(M′) context-free. — ধাপ ২, ৩
  5. Regular set R = a∗bba∗b̂b̂â∗ নিন। L(M′) ∩ R-এর string aibbajb̂b̂âk, যেখানে aibbaj ∈ L (মানে i = j) আর aibbaibbak ∈ L. দ্বিতীয়টির উল্টো akbbaibbai, সমান হতে k = i; দৈর্ঘ্য 3i + 4 জোড় হতে i জোড়। তাই L(M′) ∩ R = {anbbanb̂b̂ân : n জোড়}. — হিসাব
  6. CFL আর regular language-এর intersection CFL (পর্ব ৩৭-এ PDA × DFA নির্মাণ)। কিন্তু {anbbanb̂b̂ân : n জোড়}-এ তিনটি ব্লক সমান হতে হয়, anbncn-এর মতো; পর্ব ৩৬-এর CFL pumping lemma দিয়ে এটি context-free নয় (|vxy| ≤ p বলে pumping বড়জোর দুটি পাশাপাশি ব্লক ছোঁয়, তৃতীয়টি বদলায় না)। — বিরোধ
  7. অতএব এমন M নেই। আর L-এর একটি CFG S → aSa ∣ bSb ∣ ε, তাই L ∈ CFL ∖ DCFL. ∎
1অনুমান: DPDA M, L(M) = wwᴿ2একই run: u, তারপর uv3M′ = কপি ১ + কপি ২ (চিহ্নিত)4L(M′) = {u v̂ : u ∈ L, uv ∈ L}5∩ a∗bba∗b̂b̂â∗6তিনটি সমান ব্লক: CFL নয়
উদাহরণ string আর তথ্য
string
জানা গেল
  1. অনুমান। ধরি M একটি DPDA আর L(M) = wwR. লক্ষ্য একটি বিরোধ।
  2. প্রথম palindrome. u = aabbaa = a2bba2 ∈ L. M-এর একমাত্র run u পড়ে কোনো এক মুহূর্তে F-এর state-এ পৌঁছায়।
  3. চালিয়ে যাওয়া। v = bbaa হলে uv = aabbaabbaa, যার উল্টোও একই আর দৈর্ঘ্য ১০, তাই uv ∈ L. Determinism-এর কারণে uv-এর run u-এর run-এর হুবহু সম্প্রসারণ: u-এর পরের accept মুহূর্তটি এই পথেও আছে।
  4. দুই কপি। M′ কপি ১-এ u পড়ে, কোনো accept state থেকে ε-move দিয়ে কপি ২-এ যায়, তারপর চিহ্নিত চিহ্নে v̂ = b̂b̂ââ পড়ে। Stack একটিই, অপরিবর্তিত, তাই কপি ২ ঠিক সেখান থেকে চলে যেখানে M uv পড়ার মাঝপথে থাকত।
  5. M′-এর language. M′ গ্রহণ করে ঠিক u v̂, যেখানে u ∈ L আর uv ∈ L. M′ একটি PDA, তাই এই language context-free হওয়ার কথা।
  6. Regular দিয়ে ছাঁকা। a∗bba∗b̂b̂â∗-এর সঙ্গে intersection-এ থাকে ঠিক anbbanb̂b̂ân, n জোড়। n = 0-তে bbb̂b̂, n = 2-তে aabbaab̂b̂ââ. CFL ∩ regular আবার CFL হওয়ার কথা।
  7. বিরোধ। n = 3-এ aaabbaaab̂b̂âââ নেই, কারণ aaabbaaabbaaa-র দৈর্ঘ্য ১৩, বিজোড়। আর তিন সমান ব্লকের এই language CFL নয় (পর্ব ৩৬-এর pumping lemma). তাই M থাকতে পারে না। ∎

ধাপ ৫-এর হিসাব হাতে না করে নিচের ব্লকে language-এর সংজ্ঞা থেকেই যাচাই করা যায়: সব i, j, k ≤ 12 নিয়ে দেখা হয়েছে কোন ত্রয়ীতে u ∈ L আর uv ∈ L দুটিই সত্য। একই কৌশল {anbn} ∪ {anb2n}-এও চালানো হয়েছে (অনুশীলন ২)। এখানে কোনো যন্ত্র চলছে না; ব্লকটি শুধু প্রমাণের সেট-হিসাবটি পরীক্ষা করে।

# Two-copy trick, checked on the languages themselves (no machine needed):
# M' accepts u + hat(v) exactly when u is in L and uv is in L.
def twocopy(L, shapes):
    return [s for s, (u, v) in shapes if L(u) and L(u + v)]

wwr = lambda w: len(w) % 2 == 0 and w == w[::-1]       # even palindromes
# shape a^i bb a^j | bb a^k  (the part after "|" is the hatted copy)
shapes = [((i, j, k), ("a" * i + "bb" + "a" * j, "bb" + "a" * k))
          for i in range(13) for j in range(13) for k in range(13)]
print("wwR       :", twocopy(wwr, shapes))

two = lambda w: (w == "a" * (n := w.count("a")) + "b" * w.count("b")
                 and w.count("b") in (n, 2 * n))     # a^n b^n  or  a^n b^2n
shapes = [((i, j, k), ("a" * i + "b" * j, "b" * k))
          for i in range(9) for j in range(17) for k in range(1, 17)]
print("anbn+anb2n:", twocopy(two, shapes))

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

wwR       : [(0, 0, 0), (2, 2, 2), (4, 4, 4), (6, 6, 6), (8, 8, 8), (10, 10, 10), (12, 12, 12)]
anbn+anb2n: [(1, 1, 1), (2, 2, 2), (3, 3, 3), (4, 4, 4), (5, 5, 5), (6, 6, 6), (7, 7, 7), (8, 8, 8)]

প্রথম লাইনে 133 = 2197টি (i, j, k)-এর মধ্যে টিকে আছে শুধু i = j = k আর i জোড়: ঠিক ধাপ ৫-এর হিসাব। দ্বিতীয় লাইনে u = aibj, v̂ = b̂k (k ≥ 1). টিকে থাকে শুধু i = j = k: u = anbn আর uv = anb2n. অর্থাৎ ছাঁকা language {anbnb̂n : n ≥ 1}, b̂-কে c নাম দিলে anbncn. দুই ক্ষেত্রেই “তিনটি সমান ব্লক” বেরিয়ে আসে, আর সেটিই বিরোধের উৎস।

একটি সতর্কতা: এই ব্লক ছোট সংখ্যায় হিসাবটি যাচাই করে, প্রমাণ করে না; প্রমাণ উপরের সাত ধাপ। আর প্রমাণটি কোথায় determinism ব্যবহার করেছে, তা খেয়াল করুন: শুধু ধাপ ২-এ। Nondeterministic PDA-তে u-এর গ্রহণযোগ্য পথ আর uv-এর গ্রহণযোগ্য পথ আলাদা হতে পারে, তাই একই নির্মাণ সাধারণ PDA-র বিরুদ্ধে কিছু বলে না, যেমনটি হওয়া উচিত।

৫ · DCFL complement-এ বদ্ধ — তিনটি বাধা আর তাদের সমাধান

পর্ব ০৮-এ DFA-র complement ছিল এক লাইনের কাজ: accept আর non-accept state অদলবদল। সাধারণ PDA-তে এটি অসম্ভব (CFL complement-এ বদ্ধ নয়, পর্ব ৩৭), কারণ “কোনো একটি পথ গ্রহণ করে” কথাটির উল্টো “সব পথ বাতিল করে”, যা একটি পথ দিয়ে যাচাই করা যায় না। DPDA-তে পথ একটিই, তাই আশা জাগে। কিন্তু সরল অদলবদল এখানেও ভুল, তিনটি কারণে।

১. আটকে যাওয়া

“বড়জোর একটি” রূপের DPDA মাঝপথে আটকে যেতে পারে, যেমন anbn-যন্ত্রে ba. Input পুরো পড়া হয়নি, তাই F অদলবদলের পরেও বাতিল, অথচ ba complement-এ আছে।

২. শেষের ε-move

Input শেষে ε-move দিয়ে যন্ত্র একটি non-accept আর তারপর একটি accept state ছুঁতে পারে। অদলবদলের পরে non-accept-টি accept হয়ে যায়, ফলে একই string দুই যন্ত্রেই গৃহীত।

৩. অসীম ε-loop

যন্ত্র কোনো চিহ্ন না পড়ে চিরকাল ε-move চালাতে পারে। তখন input-এর বাকিটা কখনো পড়া হয় না; এই অবস্থা আগে থেকে চিনে বাতিলের একটি state-এ পাঠাতে হয়।

উপপাদ্য ৫.১ (Ginsburg–Greibach, ১৯৬৬ বলে পরিচিত)

L একটি DCFL হলে L̄ = Σ∗ ∖ L-ও একটি DCFL.

নির্মাণের সুবিধার জন্য HMU-র মতো একটি রূপ নিন: প্রতিটি move ঠিক একটি ওপরের চিহ্ন X তোলে (আবার রাখতে পারে), তলার Z কখনো তোলা হয় না, তাই stack কখনো ফাঁকা হয় না; আর প্রতিটি (q, X)-এ হয় একটি ε-move, নয়তো শুধু পড়ার move. যেকোনো DPDA-কে language না বদলে এই রূপে আনা যায় (Sipser অংশ ২.৪ আর HMU অংশ ৬.৪-এ বিস্তারিত)।

প্রমাণের রূপরেখা:

  1. ε-loop দূর করা। যে (q, X) থেকে শুধু ε-move-এ অনন্তকাল চলা যায়, তা চেনা যায় (সসীম অবস্থায় ε-move-এর ধারায় stack একটি সীমার বেশি উঁচু হলে বা একই (state, ওপরের চিহ্ন) ফিরে এলে পুনরাবৃত্তি নিশ্চিত — বিশদ যুক্তি Sipser Lemma ২.৪১-এ)। এমন জায়গায় ε-move-এর বদলে একটি non-accept ফাঁদ-state বসানো হয়, তবে loop-এর মধ্যে কোনো accept state ছুঁলে সেই তথ্য রাখতে হয়। এখন যন্ত্র সবসময় পুরো input পড়ে।
  2. Dead state D. যে (q, X)-এ ε-move নেই আর কোনো চিহ্ন a-এর move নেই, সেখানে a, X → X দিয়ে D-তে পাঠান; D প্রতিটি চিহ্ন পড়ে নিজের কাছে ফেরে। এখন যন্ত্র কখনো আটকায় না।
  3. পতাকা k. প্রতিটি state q-কে তিনটি কপিতে ভাঙুন: (q, 1) মানে “শেষ চিহ্ন পড়ার পরে কোনো accept state দেখা হয়নি”, (q, 2) মানে “দেখা হয়েছে”, (q, 3) মানে “পরের চিহ্ন পড়তে যাচ্ছি আর কোনো accept দেখা হয়নি”। ε-move পতাকা রক্ষা করে (accept state-এ ঢুকলে 2); পড়ার move পতাকা নতুন করে শুরু করে।
  4. পড়ার ঠিক আগে। (q, 1) থেকে, যেখানে q-এর পরের move একটি পড়া, একটি ε-move দিয়ে (q, 3)-এ যান, তারপর পড়ুন। (q, 2) থেকে সরাসরি পড়ুন।
  5. F′ = {(q, 3)}. w ∉ L মানে শেষ চিহ্নের পরের ε-ধারায় কোনো accept নেই, আর ধারাটি একটি পড়ার-state-এ থামে (ধাপ ১ আর ২-এর কারণে); তখন যন্ত্র (q, 3)-এ যায় আর গ্রহণ করে। w ∈ L হলে পতাকা 2 হয়ে যায়, আর ৩-এ যাওয়ার পথ বন্ধ। নতুন যন্ত্রও deterministic, কারণ প্রতিটি (q, k, X)-এ আগের মতোই বড়জোর একটি পথ। ∎
1q0 : a, Z → aZ ⇒ q12q1 : a, a → aa ; b, a → ε ⇒ q23q2 : b, a → ε ; ε, Z → Z ⇒ q34D : যেকোনো চিহ্ন, X → X5(q, k): k = 1, 2, 3 ; F′ = {(q, 3)}
run আর সিদ্ধান্ত
input
state-ক্রম
  1. মূল যন্ত্র। HMU রূপে anbn: q0-এ প্রথম a, q1-এ বাকি a আর প্রথম b, q2-তে বাকি b, তারপর Z দেখে ε-move-এ q3. F = {q0, q3}; q0 থাকায় ε গৃহীত। ab-এর run q0 → q1 → q2 → q3, গৃহীত।
  2. সরল অদলবদল, বাধা ২। F′ = {q1, q2} নিন। ab পড়া শেষে যন্ত্র (q2, ε, Z)-এ, যা F′-এ, তারপর ε-move-এ q3-তে। শেষের ε-ধারা q2 ছুঁয়েছে, তাই “complement” যন্ত্রও ab গ্রহণ করে, অথচ ab ∈ L.
  3. সরল অদলবদল, বাধা ১। ba-তে q0-এ b পড়ার move নেই: যন্ত্র আটকে যায়, input বাকি। F যা-ই হোক, গ্রহণ হয় না। অথচ ba ∉ L, তাই complement-এ থাকার কথা।
  4. সমাধান ১: dead state. অনুপস্থিত move-গুলো D-তে যায়, D সব চিহ্ন পড়ে। ba এখন q0 → D → D, পুরো input পড়া হলো।
  5. সমাধান ২: পতাকা। প্রতিটি state-এর তিন কপি। (q, 3)-এ শুধু তখনই যাওয়া যায়, যখন যন্ত্র পরের চিহ্ন পড়তে যাচ্ছে আর শেষ পড়ার পরে কোনো accept দেখা হয়নি। F′ শুধু এই কপিগুলো।
  6. ab নতুন যন্ত্রে। শুরু (q0, 2), কারণ q0 ∈ F. a পড়ে (q1, 1); পড়ার আগে (q1, 3); b পড়ে (q2, 1); ε-move-এ q3 ∈ F, তাই (q3, 2). Input শেষ, আর k = 2 থেকে ৩-এ যাওয়ার নিয়ম নেই: বাতিল, ঠিক যা চাই।
  7. ba নতুন যন্ত্রে। (q0, 2) থেকে b পড়ে (D, 1); পড়ার আগে (D, 3); a পড়ে (D, 1); input শেষে ε-move-এ (D, 3) ∈ F′: গৃহীত। বাধা ৩ (ε-loop) এই যন্ত্রে নেই, কারণ একমাত্র ε-move q2 → q3, আর q3 থেকে কোনো ε-move নেই; সাধারণ ক্ষেত্রে নির্মাণের ধাপ ১ সেটি সামলায়।

নিচের ব্লক নির্মাণটি সত্যি সত্যি বানায় (ধাপ ২ থেকে ৫; এই যন্ত্রে ε-loop নেই বলে ধাপ ১ লাগে না) আর দৈর্ঘ্য ৮ পর্যন্ত প্রতিটি string-এ সরল অদলবদল ও নির্মাণ দুটিকে মূল যন্ত্রের সঙ্গে মেলায়। একটি সঠিক complement-যন্ত্র L-এর কোনো string গ্রহণ করবে না, আর L̄-এর কোনোটি বাদ দেবে না।

from itertools import product
def run(P, w, limit=500):   # one computation; each move pops ONE symbol X
    q, i, st, d, acc = P["q0"], 0, "Z", P["d"], False    # Z: never popped
    for _ in range(limit):
        acc = acc or (i == len(w) and q in P["F"])
        if (q, "", st[0]) in d: a = ""                       # ε-move, or
        elif i < len(w) and (q, w[i], st[0]) in d: a = w[i]  # read: never both
        else: break
        q, push = d[(q, a, st[0])]
        i, st = i + len(a), push + st[1:]
    return acc
ANBN = {"q0": "q0", "F": {"q0", "q3"}, "S": "ab", "G": "Za", "d": {
    ("q0", "a", "Z"): ("q1", "aZ"), ("q1", "a", "a"): ("q1", "aa"),
    ("q1", "b", "a"): ("q2", ""), ("q2", "b", "a"): ("q2", ""),
    ("q2", "", "Z"): ("q3", "Z")}}
def complement(P):
    d, F, nd = dict(P["d"]), P["F"], {}
    Q = {P["q0"], "D"} | {k[0] for k in d} | {v[0] for v in d.values()}
    for q, X, a in product(Q, P["G"], P["S"]):       # fix 1: dead state D
        if (q, "", X) not in d: d.setdefault((q, a, X), ("D", X))
    for (q, a, X), (r, y) in d.items():              # fix 2: flag k = 1, 2, 3
        if a == "":
            for k in (1, 2): nd[((q, k), "", X)] = ((r, 2 if k == 2 or r in F else 1), y)
        else:
            nd[((q, 1), "", X)] = ((q, 3), X)        # about to read, no F seen
            for k in (2, 3): nd[((q, k), a, X)] = ((r, 2 if r in F else 1), y)
    return {"q0": (P["q0"], 2 if P["q0"] in F else 1), "d": nd,
            "F": {(q, 3) for q in Q}}
naive = dict(ANBN, F={"q1", "q2"})                   # just swap F
words = ["".join(t) for n in range(9) for t in product("ab", repeat=n)]
for name, M in [("naive swap", naive), ("construction", complement(ANBN))]:
    extra = [w for w in words if run(M, w) and run(ANBN, w)]
    miss = [w for w in words if not run(M, w) and not run(ANBN, w)]
    print(f"{name:12}: accepts {len(extra)} of L {extra[:3]}, "
          f"misses {len(miss)} of L-bar {miss[:3]}")

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

naive swap  : accepts 4 of L ['ab', 'aabb', 'aaabbb'], misses 486 of L-bar ['b', 'ba', 'bb']
construction: accepts 0 of L [], misses 0 of L-bar []

সরল অদলবদল দুই দিকেই ভুল। L-এর ৫টি string-এর মধ্যে n ≥ 1-এর চারটি (ab, aabb, …) সে গ্রহণ করে: বাধা ২, শেষের ε-ধারায় q2 ছোঁয়া। আর L̄-এর ৫০৬টির মধ্যে ৪৮৬টি সে বাদ দেয়: প্রায় সবই আটকে যাওয়া run (বাধা ১), যেমন b, ba. যে ২০টি সে ঠিকঠাক গ্রহণ করে, সেগুলো শুধু a-এর string (a, aa, …) আর aab-এর মতো “b কম” string, যেখানে input পুরো পড়া শেষে যন্ত্র q1 বা q2-তে থেমে থাকে। নির্মাণ দুই দিকেই নিখুঁত, ৫১১টি string-এর সবগুলোতে। run-এর limit শুধু নিরাপত্তার জন্য; এই যন্ত্রে ε-ধারা বড়জোর এক ধাপের।

ফাঁদ: “DPDA-তে complement সহজ, F অদলবদল করলেই হয়” কথাটি AI আর পাঠ্যনোট দুই জায়গায়ই দেখা যায়। উপরের আউটপুট দেখাচ্ছে, ছোট একটি anbn-যন্ত্রেই এটি ৪৯০টি string-এ ভুল করে। DFA-তে অদলবদল কাজ করে কারণ DFA কখনো আটকায় না আর ε-move নেই; DPDA-তে দুটি শর্তই আগে নিশ্চিত করতে হয়।

৬ · কোথায় বদ্ধ, কোথায় নয় — DCFL-এর closure

Complement-এ বদ্ধতা থেকে একটি চমৎকার ফল আসে, যা দেখায় DCFL শ্রেণি closure-এর দিক থেকে CFL-এর চেয়ে একেবারে আলাদা আচরণ করে।

উপপাদ্য ৬.১

DCFL intersection-এ বদ্ধ নয়, union-এও বদ্ধ নয়।

প্রমাণ:

  1. L1 = {aibjck : i = j} আর L2 = {aibjck : j = k}, i, j, k ≥ 0. দুটিই DCFL: L1-এর DPDA a push করে, b-তে pop করে, $ দেখে c-এর state-এ যায় আর stack না ছুঁয়ে c পড়ে; L2-এর DPDA a উপেক্ষা করে, b push করে, c-তে pop করে। কোনো ধাপে অনুমান লাগে না, কারণ a, b, c-এর ক্রম নিজেই পর্যায় বলে দেয়। — নির্মাণ (scratch-এ L1-এর যন্ত্র দৈর্ঘ্য ৮ পর্যন্ত সংজ্ঞার সঙ্গে মিলেছে)
  2. L1 ∩ L2 = {anbncn : n ≥ 0}, যা context-free-ই নয় (পর্ব ৩৬), তাই DCFL-ও নয়। অতএব DCFL ∩-এ বদ্ধ নয়। — সংজ্ঞা
  3. ধরুন DCFL ∪-এ বদ্ধ। L1 ∩ L2 = Σ∗ ∖ (L̄1 ∪ L̄2) (De Morgan). উপপাদ্য ৫.১-এ L̄1, L̄2 DCFL, ধরে নেওয়া অনুযায়ী তাদের union DCFL, আবার উপপাদ্য ৫.১-এ তার complement DCFL. তাহলে L1 ∩ L2 DCFL হতো, যা ধাপ ২-এর বিরোধী। ∎ — De Morgan আর complement-বদ্ধতা

লক্ষ করুন, L1 ∪ L2 = {aibjck : i = j অথবা j = k} হলো পর্ব ২৭-এর সেই inherently ambiguous language: context-free, কিন্তু DCFL নয়। দুটি DPDA “পাশাপাশি” চালিয়ে union বানানো যায় না, কারণ দুটি যন্ত্রের দুটি stack লাগে, আর পর্ব ৩২-এ দেখেছেন দুই stack মানে Turing machine-এর ক্ষমতা। একটি DPDA আর একটি DFA হলে সমস্যা নেই: DFA-র state সসীম, তাই product construction-এ একটি stack-ই যথেষ্ট, আর ফলটি deterministic থাকে।

OperationRegularDCFLCFL
Complementহ্যাঁহ্যাঁ (উপপাদ্য ৫.১)না (পর্ব ৩৭)
Unionহ্যাঁনা (উপপাদ্য ৬.১)হ্যাঁ
Intersectionহ্যাঁনানা
Regular-এর সঙ্গে ∩ আর ∪হ্যাঁহ্যাঁ (DPDA × DFA)হ্যাঁ
Inverse homomorphismহ্যাঁহ্যাঁহ্যাঁ
Concatenation, star, reversal, homomorphismহ্যাঁনা (পরিচিত ফল)হ্যাঁ

শেষ সারির ফলগুলো এখানে প্রমাণ করা হলো না; HMU-র অধ্যায় ৬-এর অনুশীলনী আর M. A. Harrison-এর Introduction to Formal Language Theory বইয়ে এগুলোর উদাহরণ পাওয়া যায়। নিচের ছবিতে তিনটি শ্রেণির অবস্থান আর এই পর্বের উদাহরণগুলো।

Regular ⊊ DCFL ⊊ CFL

প্রতিটি অন্তর্ভুক্তি কঠোর; প্রতিটি স্তরে একটি করে উদাহরণ।

Regular inside DCFL inside CFL CFL DCFL Regular wwR aⁿbⁿ ∪ aⁿb²ⁿ aⁿbⁿ wcwR সুষম বন্ধনী (ab)∗ a∗b∗ বাইরে: aⁿbⁿcⁿ, ww
ছবি ৩৫.২ — DCFL-এর ভেতরে regular, কারণ প্রতিটি DFA stack না ছুঁয়ে একটি DPDA. aⁿbⁿ দুই স্তরকে আলাদা করে, wwᴿ পরের দুটিকে, আর aⁿbⁿcⁿ CFL-এর বাইরে।

৭ · DCFL, unambiguous grammar আর LR(k) parsing

পর্ব ২৭-এ ambiguous grammar দেখেছেন: একই string-এর দুটি parse tree. Determinism আর ambiguity-র মধ্যে একটি একমুখী সম্পর্ক আছে।

উপপাদ্য ৭.১ (HMU অংশ ৬.৪-এ প্রমাণিত)

প্রতিটি DCFL-এর একটি unambiguous grammar আছে। উল্টোটি সত্য নয়: wwR-এর grammar S → aSa ∣ bSb ∣ ε unambiguous, অথচ wwR DCFL নয়।

প্রমাণের রূপরেখা: পর্ব ৩৪-এর PDA → CFG নির্মাণে grammar-এর প্রতিটি leftmost derivation যন্ত্রের একটি computation-এর সঙ্গে মেলে। যন্ত্র deterministic হলে প্রতিটি string-এর computation একটিই, তাই leftmost derivation-ও একটিই। একটি কারিগরি বাধা: সেই নির্মাণ empty stack-এ গ্রহণ চায়, আর empty-stack DPDA শুধু prefix-free language চেনে (কোনো string অন্যটির প্রকৃত prefix নয়; পর্ব ৩৩-এর বিষয়)। HMU এর সমাধান করেন একটি endmarker দিয়ে: L-এর জায়গায় L⊣ নিন, যা prefix-free; তার unambiguous grammar বানিয়ে ⊣-কে ε দিয়ে বদলান। ∎ wwR-এর grammar unambiguous, কারণ প্রতিটি ধাপে বাইরের দুটি চিহ্ন দেখেই নিয়ম ঠিক হয়ে যায়; তবু যন্ত্রের দিক থেকে মাঝখানটা বাঁ থেকে পড়ে জানা যায় না। Ambiguity grammar-এর ধর্ম, determinism বাঁ থেকে ডানে পড়ার ধর্ম: দুটি আলাদা জিনিস।

LR(k) আর DCFL. Donald Knuth ১৯৬৫ সালের প্রবন্ধ “On the translation of languages from left to right”-এ LR(k) grammar-এর ধারণা দেন: এমন grammar, যার জন্য একটি bottom-up parser input বাঁ থেকে ডানে একবার পড়ে, সামনের সর্বোচ্চ k-টি চিহ্ন দেখে, কোনো অনুমান ছাড়াই rightmost derivation উল্টো ক্রমে খুঁজে পায়। প্রচলিত বর্ণনায় একই প্রবন্ধে দেখানো হয়েছে: একটি language-এর LR(k) grammar আছে ঠিক তখন, যখন সেটি DCFL, আর তখন একটি LR(1) grammar-ও আছে। অর্থাৎ আরও বেশি lookahead নতুন language আনে না (যদিও grammar ছোট বা সহজ হতে পারে)। Prefix-free DCFL-গুলো ঠিক LR(0) grammar-এর language বলে পরিচিত। LR parser আসলে একটি DPDA: stack-এ grammar-চিহ্ন আর state, প্রতিটি ধাপে “shift” না “reduce” তা নিশ্চিতভাবে ঠিক হয়। বিস্তারিত পর্ব ৩৯-এ।

Membership কত দ্রুত? সাধারণ CFL-এ পর্ব ৩১-এর CYK O(n3) সময় নেয়। DCFL-এ একটি DPDA-কে এমন রূপে আনা যায় যে এটি সবসময় পুরো input পড়ে থামে (উপপাদ্য ৫.১-এর ধাপ ১), আর তখন move-এর সংখ্যা input-এর দৈর্ঘ্যের রৈখিক হয় বলে জানা। তাই DCFL-এর membership রৈখিক সময়ে, আর এটিই কারণ যে programming language-এর syntax DCFL-এর মধ্যে রাখার চেষ্টা করা হয়।

সমতা: একটি দীর্ঘ খোলা প্রশ্নের সমাধান। দুটি সাধারণ PDA একই language গ্রহণ করে কি না, তা undecidable (প্রমাণ পর্ব ৫৪-এর Post correspondence problem দিয়ে, তালিকা পর্ব ৩৭-এ)। DPDA-র ক্ষেত্রে প্রশ্নটি Ginsburg আর Greibach ১৯৬৬ সালেই তোলেন বলে পরিচিত, আর প্রায় তিন দশক খোলা ছিল। Géraud Sénizergues ১৯৯৭ সালের ICALP সম্মেলনে দেখান যে এটি decidable; পূর্ণ প্রমাণ ২০০১ সালে Theoretical Computer Science-এ প্রায় ১৬০ পৃষ্ঠার একটি প্রবন্ধে আসে, আর এর জন্য তিনি ২০০২ সালের Gödel Prize পান। পরে Colin Stirling একটি সরল প্রমাণ দেন, যা সময়ের একটি primitive recursive সীমাও দেয় বলে উল্লেখ পাওয়া যায়। লক্ষ করুন বিপরীতটি: DPDA-র universality (L = Σ∗?) সহজ, কারণ complement নিয়ে emptiness পরীক্ষা করলেই হয়; কিন্তু সমতা নয়, কারণ দুটি DCFL-এর symmetric difference DCFL না-ও হতে পারে।

আরও গভীরে: Sénizergues-এর প্রমাণ decidable বলে, কিন্তু কত দ্রুত তা বলে না; Petr Jančar পরে দেখান যে সমস্যাটি TOWER নামের non-elementary শ্রেণিতে আছে বলে উল্লেখ পাওয়া যায়, আর আসল জটিলতা আজও অজানা: এটি polynomial সময়ে হয় কি না, কেউ জানে না। আরেকটি খোলা দিক হলো DCFL-এর জন্য একটি ভালো pumping lemma; Sheng Yu ১৯৮৯ সালে এমন একটি lemma দেন, কিন্তু wwR-এর মতো উদাহরণে closure-ভিত্তিক যুক্তি (অংশ ৪) প্রায়ই সহজ। Visibly pushdown language (পর্ব ৩২-এর আরও গভীরে) DCFL-এরও একটি অংশ, যেখানে union, intersection আর complement তিনটিতেই বদ্ধতা আছে।

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

  • DPDA-র সংজ্ঞা দিন। প্রতিটি configuration-এ বড়জোর একটি move: δ-এর প্রতিটি মান বড়জোর এক উপাদানের, আর ε-move ও পড়ার move একই stack-অবস্থায় একসঙ্গে নয়।
  • DPDA আর NPDA-র ক্ষমতা কি সমান? না: DCFL ⊊ CFL, উদাহরণ wwR; wcwR DCFL.
  • DCFL কোন operation-এ বদ্ধ? Complement আর regular-এর সঙ্গে ∩; union আর ∩-এ নয় (L1 = anbnc∗, L2 = a∗bncn).
  • প্রতিটি DCFL কি unambiguous? হ্যাঁ, প্রতিটির একটি unambiguous grammar আছে; উল্টোটি নয় (wwR).
  • DCFL আর LR parsing-এর সম্পর্ক? LR(k) grammar-এর language ঠিক DCFL (Knuth ১৯৬৫); LR(1)-ই যথেষ্ট।

৮ · AI-এর যুগে DPDA

AI assistant-কে “wwR-এর একটি deterministic PDA দাও” বললে অনেক সময় সে আপত্তি না তুলে একটি চতুর-দেখতে নিয়ম দেয়, যেমন “পরের চিহ্ন stack-এর ওপরের চিহ্নের সমান হলেই মেলানো শুরু”। যন্ত্রটি সত্যিই deterministic, আর abba বা ε-এ ঠিক কাজ করে, তাই প্রথম দেখায় বিশ্বাসযোগ্য। নিচের ব্লকে এমন একটি খসড়া (AI-এর উত্তরের ধাঁচে বানানো উদাহরণ) সংঘাত-পরীক্ষা আর দৈর্ঘ্য ১০ পর্যন্ত brute force দিয়ে যাচাই করা হয়েছে; ব্লকটি স্বয়ংসম্পূর্ণ।

from itertools import product
def conflicts(P):           # pairs of moves that can fire in one configuration
    ms = list(P["d"])
    return [(m, n) for i, m in enumerate(ms) for n in ms[i + 1:] if m[0] == n[0]
            and (m[1] == n[1] or "" in (m[1], n[1]))
            and (m[2] == n[2] or "" in (m[2], n[2]))]
def run(P, w, limit=1000):  # the ONE computation of a deterministic PDA
    q, i, st, acc = P["q0"], 0, "", False
    for _ in range(limit):
        acc = acc or (i == len(w) and q in P["F"])
        m = [k for k in P["d"] if k[0] == q and w.startswith(k[1], i)
             and st.startswith(k[2])]
        if not m: break
        (r, y), (_, a, x) = P["d"][m[0]], m[0]
        q, i, st = r, i + len(a), y + st[len(x):]
    return acc
# "AI draft": a DPDA for ww^R. Rule: switch to matching at the first
# symbol that equals the top of the stack (no guessing needed!?)
AI = {"q0": "q1", "F": {"q1", "q4"}, "d": {
    ("q1", "", ""): ("q2", "$"),
    ("q2", "a", "$"): ("q2", "a$"), ("q2", "b", "$"): ("q2", "b$"),
    ("q2", "a", "b"): ("q2", "ab"), ("q2", "b", "a"): ("q2", "ba"),
    ("q2", "a", "a"): ("q3", ""), ("q2", "b", "b"): ("q3", ""),  # switch
    ("q3", "a", "a"): ("q3", ""), ("q3", "b", "b"): ("q3", ""),
    ("q3", "", "$"): ("q4", "")}}
print("conflicts:", conflicts(AI) or "none, so it IS deterministic")
inL = lambda w: len(w) % 2 == 0 and w == w[::-1]
words = ["".join(t) for k in range(11) for t in product("ab", repeat=k)]
extra = [w for w in words if run(AI, w) and not inL(w)]
miss = [w for w in words if inL(w) and not run(AI, w)]
print(f"{len(words)} strings: extra {len(extra)}, missing {len(miss)} of "
      f"{sum(map(inL, words))}; shortest missing: {miss[:4]}")

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

conflicts: none, so it IS deterministic
2047 strings: extra 0, missing 52 of 63; shortest missing: ['aaaa', 'bbbb', 'aaaaaa', 'aabbaa']

যন্ত্রটি সত্যিই deterministic, আর কোনো বাড়তি string নেয় না, কারণ q3-এর মেলানো ধাপ সৎ। কিন্তু দৈর্ঘ্য ১০ পর্যন্ত ৬৩টি জোড় palindrome-এর মধ্যে ৫২টি বাদ দেয়। সবচেয়ে ছোট উদাহরণ aaaa: দ্বিতীয় a ওপরের a-এর সমান, তাই যন্ত্র “মাঝখান এসে গেছে” ধরে মেলাতে শুরু করে, অথচ আসল মাঝখান দুটি চিহ্ন পরে। aabbaa-তেও একই ভুল, প্রথম জোড়া aa-তেই। কয়েকটি পরীক্ষায় (abba, ε, aa) পাস করলেও যন্ত্রটি ভুল; আর অংশ ৪-এর উপপাদ্য বলে, কোনো deterministic নিয়মই সব ক্ষেত্রে পারবে না। তাই “wwR-এর DPDA” দাবি শুনলেই brute force চালানোর আগেই সন্দেহ করুন।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
wwR বা {anbn} ∪ {anb2n}-এর জন্য “DPDA” দেওয়াউপপাদ্য ৪.১ মনে রাখুন; brute force-এ missing তালিকা দেখুন (aaaa)
“Deterministic” বলা যন্ত্রে ε-move আর পড়ার move একই stack-অবস্থায় (পর্ব ৩২-এর BAL)প্রতিটি state-এর move জোড়ায় জোড়ায় সংঘাত-শর্তে মিলিয়ে দেখুন, বা conflicts চালান
“DPDA-র complement মানে শুধু F অদলবদল”আটকে যাওয়া run আর শেষের ε-ধারা পরীক্ষা করুন; L আর নতুন যন্ত্র দুটিই একটি string নেয় কি না দেখুন
“DCFL union-এ বদ্ধ” বা “দুটি DPDA পাশাপাশি চালানো যায়”দুটি stack লাগবে; L1 ∩ L2 = anbncn উদাহরণ দিয়ে খণ্ডন করুন
“Unambiguous grammar আছে, তাই DCFL” বা “DPDA-র সমতা undecidable”প্রথমটি ভুল (wwR); দ্বিতীয়টি NPDA-র জন্য সত্য, DPDA-র জন্য নয় (Sénizergues)
সাল আর নাম বানানো (যেমন ভুল বছরে Knuth বা ভুল পুরস্কার)Sipser অংশ ২.৪, HMU অংশ ৬.৪ আর মূল প্রবন্ধের তথ্য নিজে খুঁজুন

AI-কে কাজে লাগানোর ভালো উপায়: যন্ত্রের সঙ্গে প্রতিটি state-এর move-জোড়ার সংঘাত-বিশ্লেষণ, ছোট input-এর trace আর একটি brute-force কোড চাওয়া, আর language আদৌ DCFL কি না, সেই প্রশ্ন আগে তোলা।

আমি গণনার তত্ত্ব শিখছি। Σ = {a, b}-এর ওপর L = {w : w-এ a আর b সমান সংখ্যক}-এর জন্য একটি deterministic pushdown automaton (DPDA) দাও। ১. প্রথমে বলো L আদৌ DCFL কি না, আর কেন; নিশ্চিত না হলে স্পষ্ট করে বলো। ২. Sipser রীতিতে P = (Q, Σ, Γ, δ, q0, F) লেখো; প্রথম move-এ $ push করো, প্রতিটি transition "a, x → y" রূপে একটি সারণিতে দাও। ৩. প্রতিটি state-এর প্রতিটি move-জোড়া নিয়ে দেখাও কেন দুটি একসঙ্গে খাটে না (input অংশ বা stack অংশ মেলে না)। ৪. ε, ab, ba আর aabbba-র configuration-ক্রম দাও। ৫. শুধু standard library দিয়ে একটি Python কোড দাও, যা সংঘাত খোঁজে আর দৈর্ঘ্য 10 পর্যন্ত প্রতিটি string-এ যন্ত্র ও L-এর সংজ্ঞা মিলিয়ে extra আর missing তালিকা ছাপে। ৬. বানানো রেফারেন্স দিও না।

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

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

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

প্র ০১Deterministic CFL-এর ধারণা কীভাবে এল, আর compiler-নির্মাতারা কেন এর ওপর এত নির্ভর করেন?

১৯৫০-এর দশকের শেষে FORTRAN আর ALGOL-এর মতো ভাষার compiler বানানো শুরু হলে একটি ব্যবহারিক প্রশ্ন দেখা দেয়: grammar থেকে কীভাবে এমন parser বানানো যায়, যা দ্রুত চলে আর পেছনে ফিরে চেষ্টা করে না? সাধারণ CFG-এর parsing তখনকার যন্ত্রে খুব ব্যয়বহুল ছিল, আর backtracking-এর সময় অনিশ্চিত। ১৯৬০-এর দশকের শুরুতে বহু গবেষক “precedence” আর অন্যান্য সীমিত grammar-শ্রেণি নিয়ে কাজ করেন, যেগুলো এক পাসে parse করা যায়।

Donald Knuth ১৯৬৫ সালে Information and Control-এ প্রকাশিত প্রবন্ধে এই সব প্রচেষ্টাকে একটি সাধারণ ধারণায় আনেন: LR(k) grammar, যেখানে বাঁ থেকে ডানে পড়ে, সামনের k-টি চিহ্ন দেখে, rightmost derivation উল্টো ক্রমে নিশ্চিতভাবে খুঁজে পাওয়া যায়। প্রচলিত বর্ণনায় তিনি দেখান যে এই grammar-গুলোর language ঠিক deterministic PDA-র language. প্রায় একই সময়ে Seymour Ginsburg আর Sheila Greibach-এর ১৯৬৬ সালের প্রবন্ধ “Deterministic context free languages” DPDA-র শ্রেণিটি নিয়ে বিস্তারিত গবেষণা করে, complement-বদ্ধতাসহ, আর DPDA-র সমতার প্রশ্নটি তোলে বলে পরিচিত।

প্রথমদিকে LR parser-এর table বিশাল হতো বলে এটি তাত্ত্বিক মনে হতো। পরে Frank DeRemer-এর SLR আর LALR (১৯৬৯–৭১ সালের দিকে) table ছোট করে, আর Unix-এর yacc-এর মতো parser generator LALR(1) ব্যবহার করে ব্যাপক জনপ্রিয় হয়; আজকের Bison-ও এই ধারার। এর মূল প্রতিশ্রুতি DPDA-রই প্রতিশ্রুতি: input-এর দৈর্ঘ্যের রৈখিক সময়, কোনো অনুমান নেই, আর grammar-এ সমস্যা থাকলে (shift-reduce বা reduce-reduce conflict) parser বানানোর সময়েই সতর্কবার্তা। লক্ষ করুন, এই “conflict” আর আমাদের DPDA-র move-সংঘাত একই ধারণার দুই রূপ।

মূল উপলব্ধি: DCFL কোনো বিমূর্ত কৌতূহল নয়; compiler-এর রৈখিক-সময়ের parser-এর গাণিতিক সীমানা এটি, আর grammar-নকশাকারীর কাজ হলো ভাষাটিকে এই সীমানার ভেতরে রাখা।

প্র ০২দুটি DFA-র সমতা সহজে যাচাই করা যায়, দুটি PDA-র সমতা undecidable. দুটি DPDA-র সমতার প্রশ্ন কেন এত কঠিন ছিল?

DFA-র ক্ষেত্রে (পর্ব ২০) সমতা মানে symmetric difference ফাঁকা কি না, আর product construction-এ symmetric difference আবার একটি DFA, যার emptiness একটি reachability প্রশ্ন। সাধারণ PDA-তে এই পথ বন্ধ: CFL complement বা intersection-এ বদ্ধ নয়, আর সমতা undecidable বলে প্রমাণিত (পর্ব ৫৪-এর Post correspondence problem থেকে)। DPDA মাঝখানে বসে। Complement-এ বদ্ধতা আছে, তাই L(A) ⊆ L(B) মানে L(A) ∩ L̄(B) = ∅; কিন্তু দুটি DCFL-এর intersection DCFL না-ও হতে পারে, এমনকি CFL না-ও হতে পারে, তাই সরল product-কৌশল কাজ করে না। আসলে DCFL-এর inclusion (⊆) undecidable বলে জানা, সমতা নয়, আর এই সূক্ষ্ম পার্থক্যই প্রশ্নটিকে কঠিন করেছিল।

১৯৬৬ সালে প্রশ্নটি ওঠার পর কয়েক দশক ধরে বিশেষ ক্ষেত্রগুলো একটি একটি করে decidable প্রমাণিত হয়: simple DPDA, real-time DPDA, finite-turn DPDA ইত্যাদি। প্রতিটি প্রমাণ নতুন কৌশল চাইত, আর সাধারণ ক্ষেত্রটি খোলা থাকে। শেষে Géraud Sénizergues ১৯৯৭ সালে একটি পূর্ণ সমাধান ঘোষণা করেন; মোটা দাগে মূল ধারণা হলো দুটি DPDA-র configuration-জোড়ার সমতা নিয়ে একটি সম্পূর্ণ “proof system” বানানো, যেখানে সমান হলে একটি সসীম প্রমাণ অবশ্যই পাওয়া যায়, আর অসমান হলে একটি পার্থক্যকারী string খুঁজে পাওয়া যায়। দুটি পদ্ধতি পাশাপাশি চালালে একটি অবশ্যই থামে। এই কাজের জন্য তিনি ২০০২ সালের Gödel Prize পান। Colin Stirling পরে আরও সরল একটি প্রমাণ দেন।

ব্যবহারিক দিক থেকে মজার কথা: algorithm-টি আছে, কিন্তু এর চলার সময় অত্যন্ত বেশি হতে পারে, আর বাস্তব কোনো compiler-টুলে এটি নিয়মিত ব্যবহার হয় বলে জানা নেই। দুটি LR grammar একই ভাষা বর্ণনা করে কি না, তা যাচাই এখনো প্রধানত পরীক্ষা আর হাতে প্রমাণের কাজ।

মূল উপলব্ধি: Decidable আর undecidable-এর সীমারেখা কখনো কখনো অপ্রত্যাশিত জায়গা দিয়ে যায়: DPDA-র সমতা decidable, অথচ inclusion নয়; আর “decidable” মানেই “ব্যবহারযোগ্য দ্রুত” নয়।

প্র ০৩Complement নেওয়া DPDA-তে সম্ভব কিন্তু সাধারণ PDA-তে নয়। এই অসমতার পেছনে “অন্তত একটি পথ” বনাম “সব পথ”-এর কী ভূমিকা?

Nondeterministic যন্ত্রের গ্রহণের সংজ্ঞায় একটি অস্তিত্ব-প্রশ্ন লুকিয়ে আছে: “এমন একটি পথ আছে কি, যা গ্রহণে শেষ হয়?” এর complement হলো একটি সার্বজনীন প্রশ্ন: “প্রতিটি পথ কি বাতিলে শেষ হয়?” একটি nondeterministic যন্ত্র অস্তিত্ব-প্রশ্নে দক্ষ, কারণ সে একটি সঠিক পথ অনুমান করে দেখিয়ে দেয়। কিন্তু “সব পথ ব্যর্থ” দেখাতে একটি পথ যথেষ্ট নয়; সব পথ একসঙ্গে দেখতে হয়।

NFA-র ক্ষেত্রে সমস্যা ছিল না, কারণ subset construction সব পথ একসঙ্গে একটি deterministic যন্ত্রে ধরে, আর তারপর অদলবদল চলে। PDA-তে সব পথ একসঙ্গে ধরতে প্রতিটি পথের নিজস্ব stack লাগে, যা একটি stack-এ রাখা যায় না। তাই CFL complement-এ বদ্ধ নয়: পর্ব ৩৭-এ দেখবেন, anbncn-এর complement একটি CFL, অথচ anbncn নিজে নয়। DPDA-তে পথ একটিই, তাই “সব পথ” আর “একটি পথ” এক জিনিস; বাকি থাকে শুধু অংশ ৫-এর তিনটি কারিগরি বাধা।

এই ছক complexity theory-তেও বারবার ফিরে আসে। NP-এর সংজ্ঞাও অস্তিত্বের: একটি সার্টিফিকেট আছে কি না (পর্ব ৫৮)। এর complement-শ্রেণি coNP সার্বজনীন প্রশ্নের। P-তে যন্ত্র deterministic, তাই P complement-এ বদ্ধ, ঠিক DCFL-এর মতো। NP = coNP কি না, তা একটি খোলা প্রশ্ন (পর্ব ৬২), যদিও বেশিরভাগ গবেষক মনে করেন সমান নয়। অন্যদিকে NL = coNL প্রমাণিত (Immerman–Szelepcsényi, পর্ব ৬৬), যা দেখায় যে nondeterminism থাকলেও কখনো কখনো complement নেওয়ার চতুর উপায় থাকে। এখানে উপমাটি শুধু ধারণার মিল; PDA-র ফল থেকে এসব প্রশ্নের কোনো উত্তর আসে না।

মূল উপলব্ধি: Nondeterminism অস্তিত্বের প্রশ্ন সহজ করে, কিন্তু তার complement কঠিন করে; deterministic শ্রেণিগুলো তাই প্রায় সবসময় complement-এ বদ্ধ, আর nondeterministic শ্রেণির ক্ষেত্রে এটি একটি আলাদা, প্রায়ই গভীর, প্রশ্ন।

প্র ০৪Final state আর empty stack দুই রীতি PDA-তে সমান শক্তিশালী, কিন্তু DPDA-তে নয়। Endmarker এই পার্থক্য কীভাবে মুছে দেয়, আর বাস্তবে EOF token কেন থাকে?

Empty stack দিয়ে গ্রহণে একটি string গৃহীত হয় যখন input শেষ আর stack ফাঁকা। HMU-র রীতিতে প্রতিটি move ওপরের একটি চিহ্ন তোলে, তাই stack ফাঁকা হলে DPDA আর কোনো move করতে পারে না। তাই w গৃহীত হলে w-এর পরে যেকোনো চিহ্ন এলে run আর এগোয় না: w-কে প্রকৃত prefix হিসেবে রাখে এমন কোনো string গৃহীত হতে পারে না। ফলে empty-stack DPDA শুধু prefix-free language চেনে, যেমন wcwR; কিন্তু anbn-এর মতো সহজ DCFL-ও নয় (ε আর ab দুটিই আছে, আর ε সব কিছুর prefix). Final-state DPDA-র এমন সীমা নেই। পর্ব ৩৩-এ এই পার্থক্যের বিস্তারিত।

সমাধানটি সরল: প্রতিটি input-এর শেষে একটি বিশেষ চিহ্ন ⊣ বসান, যা Σ-এ নেই। L⊣ সবসময় prefix-free, কারণ ⊣ শুধু শেষে আসে। আর L একটি DCFL হয় ঠিক তখন, যখন L⊣ একটি DCFL (Sipser অংশ ২.৪-এ এই “endmarked” রূপ নিয়ে আলোচনা আছে)। ⊣ দেখলেই যন্ত্র জানে input শেষ, তাই সে stack পরিষ্কার করে empty stack-এ গ্রহণ করতে পারে। অংশ ৭-এর unambiguous-grammar প্রমাণেও ঠিক এই কৌশল লেগেছে।

বাস্তবের parser-এ এই ধারণা খুব পরিচিত। প্রায় প্রতিটি lexer (পর্ব ২২) শেষে একটি EOF token দেয়, আর LR parser-এর augmented grammar-এ একটি নতুন start নিয়ম S′ → S ⊣ যোগ হয়। কারণ একই: parser-কে নিশ্চিতভাবে জানতে হয় কখন “এখানেই শেষ” বলে গ্রহণ করবে, না হলে “x = 1” পড়ে সে বুঝতে পারত না এটি পুরো statement, নাকি “x = 1 + 2”-এর শুরু। বাজারঘরের order-query parser-ও query-র শেষে একটি সমাপ্তি-চিহ্ন পেলে সবচেয়ে সরল থাকে।

মূল উপলব্ধি: Deterministic যন্ত্রের জন্য “input শেষ” নিজেই একটি তথ্য, যা স্পষ্ট করে দিলে গ্রহণের রীতিগুলোর পার্থক্য মুছে যায়; EOF token সেই তত্ত্বেরই প্রকৌশল-রূপ।

প্র ০৫বাস্তবের programming language-গুলো কি সত্যিই DCFL? না হলে compiler কীভাবে সামলায়?

উত্তর সূক্ষ্ম। প্রথমত, কোনো programming language-ই পুরোপুরি context-free নয়: “প্রতিটি variable ব্যবহারের আগে ঘোষিত”, “function-এর argument-সংখ্যা মেলে” ধরনের নিয়ম context-free নয়, আর compiler এগুলো parsing-এর পরে আলাদা ধাপে (semantic analysis) যাচাই করে। তাই প্রশ্নটি আসলে syntax-অংশ নিয়ে: grammar-টি কি একটি DPDA বা LR(1) parser দিয়ে সামলানো যায়?

অনেক ভাষার মূল syntax মোটামুটি এর কাছাকাছি, বা সামান্য পরিবর্তনে এর ভেতরে আনা যায়, আর সেজন্য LALR বা LL parser generator এত জনপ্রিয়। JSON-এর grammar একটি পরিষ্কার উদাহরণ: খোলা আর বন্ধ চিহ্ন আলাদা, প্রতিটি মান তার প্রথম চিহ্ন দেখেই চেনা যায়, তাই এক পাসে deterministic parsing সহজ। কিন্তু ব্যতিক্রমও আছে। C-তে “T * x;” লাইনটি T একটি type-এর নাম হলে একটি ঘোষণা, আর variable হলে একটি গুণ। Grammar একা এটি ঠিক করতে পারে না; প্রচলিত সমাধান হলো “lexer hack”, যেখানে parser type-এর নামের তালিকা lexer-কে জানায় (পর্ব ২২)। C++-এর কিছু গঠন আরও জটিল বলে পরিচিত।

যেখানে grammar স্বাভাবিকভাবে deterministic নয়, সেখানে দুটি পথ। এক, grammar বা ভাষার নকশা বদলানো: keyword দিয়ে অংশ চিহ্নিত করা, বন্ধনী বাধ্যতামূলক করা, যেমন বাজারঘরের query-তে “FIND … WHERE …” keyword. দুই, সাধারণ CFG-এর parser ব্যবহার: GLR বা Earley (পর্ব ৪১), যা সব সম্ভাব্য পথ একসঙ্গে চালায়; deterministic অংশে প্রায় রৈখিক সময়ে চলে, কিন্তু সবচেয়ে খারাপ ক্ষেত্রে ঘন সময় নেয়। আধুনিক অনেক টুল এই দ্বিতীয় পথ নেয়, কারণ যন্ত্র দ্রুত হয়েছে আর grammar লেখা সহজ হয়।

মূল উপলব্ধি: DCFL একটি নকশার লক্ষ্য, প্রকৃতির নিয়ম নয়; ভাষা-নকশাকারীরা syntax-কে এর কাছাকাছি রাখেন দ্রুত, নিশ্চিত parsing-এর জন্য, আর বাকিটা semantic ধাপ বা সাধারণ parser সামলায়।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। dpda.py ব্লকে নিজের যন্ত্র লিখে conflicts আর run দিয়ে উত্তর যাচাইও করতে পারেন।

  1. নকশা: EQ = {w ∈ {a, b}∗ : w-এ a আর b সমান সংখ্যক}-এর জন্য একটি DPDA নকশা করুন। প্রতিটি state-এ কেন move-সংঘাত নেই, বলুন।

    সুষম বন্ধনীর DPDA-র মতো “এখন কেউ বাড়তি নয়” তথ্যটি state-এ রাখুন। s → z: ε, ε → $. z (accept): a, $ → a$ ⇒ A; b, $ → b$ ⇒ B. A (বাড়তি a): a, a → aa; b, a → ε; ε, $ → $ ⇒ z. B (বাড়তি b): b, b → bb; a, b → ε; ε, $ → $ ⇒ z. F = {z}.

    সংঘাত নেই: z-এর দুটি move আলাদা চিহ্ন পড়ে। A-তে দুটি পড়ার move a চায় ওপরে, ε-move $ চায়; stack অংশ মেলে না। B-তেও একইভাবে। Stack-এ সবসময় শুধু বাড়তি চিহ্নগুলো (পর্ব ৩২-এর invariant), আর ওপরে $ এলে যন্ত্র z-এ ফেরে। Scratch-এ conflicts ফাঁকা আর দৈর্ঘ্য ৮ পর্যন্ত ৯৯টি গৃহীত string সংজ্ঞার সঙ্গে হুবহু মিলেছে; abba-তে ৭টি move.

  2. প্রমাণ: L = {anbn : n ≥ 0} ∪ {anb2n : n ≥ 0} context-free, কিন্তু DCFL নয়, প্রমাণ করুন।

    CFL: S → S1 ∣ S2, S1 → aS1b ∣ ε, S2 → aS2bb ∣ ε. DCFL নয়: ধরুন DPDA M, L(M) = L. দুই কপির কৌশলে M′ বানান, L(M′) = {u v̂ : u ∈ L, uv ∈ L}, যা CFL. R = a∗b∗b̂+-এর সঙ্গে intersection নিন: u = aibj, j ∈ {i, 2i}; uv = aibj+k, j + k ∈ {i, 2i}, k ≥ 1. একমাত্র সম্ভাবনা j = i, j + k = 2i, অর্থাৎ k = i ≥ 1. তাই L(M′) ∩ R = {anbnb̂n : n ≥ 1}.

    Homomorphism h (a ↦ a, b ↦ b, b̂ ↦ c) CFL-কে CFL-এ নেয় (পর্ব ৩৭), তাই {anbncn : n ≥ 1} CFL হতো, যা পর্ব ৩৬-এর pumping lemma-র বিরোধী। ∎ two_copy.py-র দ্বিতীয় লাইন ঠিক এই হিসাব দেখায়: শুধু (n, n, n). স্বজ্ঞা: anbn পড়ে গ্রহণ করতে stack-এর গোনা খরচ হয়, অথচ পরে আরও n-টি b এলে আবার n জানা দরকার।

  3. সংঘাত খোঁজা (হিসাব): একটি PDA-র transition: q1 → q2 “ε, ε → $”; q2-তে “a, $ → a$”, “a, a → aa”, “a, b → ε”, “b, $ → b$”, “b, b → bb”, “b, a → ε”; q2 → q3 “ε, $ → ε”; F = {q3}. যন্ত্রটি কি deterministic? সব সংঘাতপূর্ণ move-জোড়া লিখুন, আর এমন একটি configuration দিন যেখানে দুটি move খাটে।

    এটি পর্ব ৩২-এর EQ-যন্ত্র। q2-এর ছয়টি পড়ার move-এর (চিহ্ন, ওপর) জোড়া সব আলাদা, তাই এদের মধ্যে সংঘাত নেই। সংঘাত শুধু ε-move-এর সঙ্গে: (q2, a, $) বনাম (q2, ε, $), আর (q2, b, $) বনাম (q2, ε, $). দুটি ক্ষেত্রেই stack অংশ সমান ($), আর input অংশের একটি ε. উদাহরণ configuration: (q2, ab, $), যা ab-এর শুরুতে আসে; এখানে a পড়ে a$ রাখা যায়, আবার $ তুলে q3-তে যাওয়াও যায়।

    dpda.py-এর conflicts ঠিক এই দুটি জোড়া ছাপে (scratch-এ যাচাই করা)। সমাধান অনুশীলন ১-এর যন্ত্র: “কেউ বাড়তি নয়” তথ্যটি $-এর বদলে state z-এ রাখা, যাতে ε-move আর পড়ার move আলাদা state-এ থাকে।

  4. ভুল খুঁজুন: একজন লিখেছেন, “DCFL union-এ বদ্ধ। প্রমাণ: L1, L2-এর DPDA M1, M2 নিন। একটি নতুন যন্ত্র দুটিকে পাশাপাশি চালায়, state হলো (q1, q2), আর যেকোনো একটি accept করলে গ্রহণ করে। প্রতিটি ধাপে দুটি যন্ত্রই deterministic, তাই নতুন যন্ত্রও deterministic.” ভুলটি কোথায়, আর দাবিটি যে মিথ্যা তা কীভাবে দেখাবেন?

    ভুল: product construction DFA-তে কাজ করে কারণ দুটি যন্ত্রের পুরো অবস্থা (state) সসীম, তাই জোড়াও একটি সসীম state. DPDA-র অবস্থায় stack আছে; M1 আর M2-এর দুটি আলাদা stack একটি stack-এ রাখা যায় না, কারণ দুটির ওপরের চিহ্ন একসঙ্গে দেখা আর আলাদাভাবে push/pop করা দরকার। দুই stack-এর যন্ত্র আর PDA-ই নয় (পর্ব ৩২: তা Turing machine-এর সমান)। এ ছাড়া দুটি যন্ত্রের ε-move আলাদা সময়ে আসে, তাই “পাশাপাশি” কথাটিও অস্পষ্ট।

    দাবি মিথ্যা: L1 = {aibjck : i = j}, L2 = {aibjck : j = k} DCFL. ∪-বদ্ধতা থাকলে complement-বদ্ধতা আর De Morgan দিয়ে L1 ∩ L2 = anbncn DCFL হতো, যা CFL-ও নয় (উপপাদ্য ৬.১)। লক্ষ করুন, একটি DPDA আর একটি DFA-র product ঠিকই কাজ করে, কারণ সেখানে stack একটিই।

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

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

ক্রমএকটি DPDA থেকে তার language-এর complement চেনে এমন DPDA বানানোর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. প্রতিটি move ঠিক একটি চিহ্ন তোলে আর তলার চিহ্ন থাকে, এমন রূপে আনা
  2. অসীম ε-loop চিনে সেগুলো একটি বাতিলের state-এ পাঠানো
  3. অনুপস্থিত move-গুলো একটি dead state-এ পাঠানো, যাতে পুরো input পড়া হয়
  4. প্রতিটি state-এ পতাকা যোগ করা: শেষ পড়ার পরে accept state দেখা হয়েছে কি না
  5. পড়ার ঠিক আগে, কোনো accept দেখা না হলে, (q, 3)-এ যাওয়া আর এগুলোকেই accept state করা
  6. ছোট দৈর্ঘ্যের সব string-এ মূল আর নতুন যন্ত্র মিলিয়ে দেখা যে ঠিক একটি গ্রহণ করে

একটি PDA-র state q-তে দুটি move আছে: “a, ε → x” (a পড়ে x push) আর “ε, $ → ε” (কিছু না পড়ে $ তোলা)। অন্য কোনো move নেই। যন্ত্রটি কি deterministic?

  • হ্যাঁ, কারণ একটি move a পড়ে আর অন্যটি কিছু পড়ে না
  • না, কারণ ওপরে $ আর পরের চিহ্ন a হলে দুটি move-ই খাটে
  • না, কারণ DPDA-তে কোনো ε-move থাকতে পারে না
  • শুধু তখনই deterministic, যখন input শেষ

নিচের কোন language একটি deterministic context-free language (DCFL)?

  • {wwR : w ∈ {a, b}∗}
  • {anbn : n ≥ 0} ∪ {anb2n : n ≥ 0}
  • {wcwR : w ∈ {a, b}∗}
  • {anbncn : n ≥ 0}

Deterministic context-free language-এর শ্রেণি নিচের কোন operation-এ বদ্ধ?

  • Complement
  • Union
  • Intersection
  • Union আর intersection দুটিই

Deterministic context-free language আর grammar-এর ambiguity নিয়ে কোন বক্তব্যটি সত্য?

  • যে language-এর unambiguous grammar আছে, তা অবশ্যই DCFL
  • প্রতিটি DCFL-এর একটি unambiguous grammar আছে
  • কিছু DCFL inherently ambiguous
  • একটি DCFL-এর প্রতিটি grammar unambiguous

“দুটি deterministic pushdown automaton একই language গ্রহণ করে কি না” — এই সমস্যার বর্তমান অবস্থা কী?

  • Undecidable, Post correspondence problem দিয়ে প্রমাণিত
  • এখনো একটি খোলা প্রশ্ন
  • Decidable, DFA-র মতো product construction দিয়ে সহজেই
  • Decidable, Sénizergues-এর প্রমাণ অনুযায়ী

একটি “বড়জোর একটি move” রূপের DPDA-র accept আর non-accept state শুধু অদলবদল করলে সাধারণত complement পাওয়া যায় না। মূল কারণ কোনটি?

  • একাধিক computation পথ থাকে
  • Stack alphabet সসীম নয়
  • মাঝপথে আটকে যাওয়া run, আর input শেষের ε-move-এ accept ও non-accept দুই রকম state ছোঁয়া
  • DPDA-তে ε-move নিষিদ্ধ বলে নতুন যন্ত্র বানানো যায় না

শব্দকোষ

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

মনে রাখুন

  1. DPDA: প্রতিটি configuration-এ বড়জোর একটি move; (q, a, x) আর (q, b, y) সংঘাতে যায় যদি input অংশ সমান বা একটি ε, আর stack অংশ সমান বা একটি ε.
  2. DCFL = DPDA-র final-state language; regular ⊊ DCFL ⊊ CFL; wcwR, anbn, BAL ভেতরে, wwR বাইরে।
  3. wwR DCFL নয়: দুই কপির কৌশল, regular দিয়ে ছাঁকা, তিন সমান ব্লকের non-CFL.
  4. DCFL complement-এ বদ্ধ (dead state, ε-loop, পতাকা k), কিন্তু union আর intersection-এ নয়।
  5. প্রতিটি DCFL unambiguous (উল্টোটি নয়); LR(k) = DCFL (Knuth); DPDA-র সমতা decidable (Sénizergues), NPDA-র নয়।

পরের পর্বে: Context-free language-এর pumping lemma: CNF parse tree-র উচ্চতা থেকে প্রমাণ, adversary খেলা, anbncn আর ww-এর মতো language যে CFL নয় তার প্রমাণ, আর Ogden-এর lemma.

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

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