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

PDA-র গ্রহণ — final state বনাম empty stack

PDA Acceptance — Final State versus Empty Stack, Conversions Both Ways, the Bottom Marker and the DPDA Prefix Property

Taught in Bangla, this lesson compares the two ways a pushdown automaton can say yes: acceptance by final state L(P) and by empty stack N(P). It builds and proves both conversions using a fresh bottom marker, then shows two classic mistakes caught by brute-force checks in in-page Python (Pyodide). A real automata-lib run tests acceptance modes, and the lesson explains why empty-stack DPDAs accept only prefix-free languages unless an endmarker is added.

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

  • L(P) আর N(P)-এর সঠিক সংজ্ঞা, configuration আর ⊢ দিয়ে, আর দুই বইয়ের দুই রীতির পার্থক্য
  • কোন language-এর নকশা কোন রীতিতে সহজ, আর কেন একটি রীতিতে নকশা করলেই চলে
  • Final state → empty stack আর empty stack → final state, দুই দিকের পূর্ণ গঠন আর সঠিকতার প্রমাণ
  • নতুন bottom marker আর শুরুর কপি কেন লাগে, Python-এ পাল্টা-উদাহরণ দিয়ে দেখা
  • DPDA-র empty stack গ্রহণ কেন শুধু prefix-free language দেয়, আর endmarker দিয়ে তার সমাধান

১ · একই যন্ত্র, দুই রকম “হ্যাঁ”

পর্ব ৩২-এ আপনি pushdown automaton (PDA) দেখেছেন: সসীম state-এর একটি যন্ত্র, সঙ্গে একটি সীমাহীন stack. Stack-এ শুধু ওপরে রাখা (push) আর ওপর থেকে তোলা (pop) যায়, ঠিক ডেটা স্ট্রাকচারের stack-এর মতো (DSA কোর্সের পর্ব ১৩)। সেই পর্বে একটি প্রশ্ন আমরা চুপচাপ একটি উত্তর ধরে নিয়েছিলাম: PDA কখন “হ্যাঁ” বলে? উত্তর ছিল, পুরো input পড়া শেষে যন্ত্রটি কোনো accept state-এ থাকলে। এটি একমাত্র যুক্তিসঙ্গত উত্তর নয়।

বাজারঘর-এর ডেলিভারি ভ্যানের কথা ভাবুন। গুদামে বাক্সগুলো একটির ওপর আরেকটি তোলা হয়, আর পথে ওপরের বাক্স আগে নামে, অর্থাৎ ভ্যানটি একটি stack. দিনের শেষে “আজকের কাজ ঠিকঠাক হয়েছে” বলার দুটি নিয়ম হতে পারে। প্রথম নিয়ম: ম্যানেজারের খাতায় শেষ ঘরটি “হিসাব মিলেছে”। ভ্যানে কয়টা বাক্স ফেরত এল, তা কেউ দেখে না। দ্বিতীয় নিয়ম: ভ্যান একদম খালি, সব বাক্স পৌঁছে গেছে। খাতার কোন ঘরে আছেন, তা কেউ দেখে না। প্রথমটি final state, দ্বিতীয়টি empty stack.

দুটি নিয়মে একই যন্ত্র ভিন্ন language দিতে পারে। যেমন পর্ব ৩২-এর anbn-এর PDA শেষে নিচের চিহ্ন $ তুলে ফেলে, তাই এর stack-ও শেষে খালি হয়; দুই নিয়মে প্রায় একই উত্তর। কিন্তু যে PDA কখনো $ তোলে না, empty stack নিয়মে সে কোনো string-ই নেয় না। এই পর্বের প্রশ্ন তিনটি:

  • সংজ্ঞা: দুই রীতির language ঠিক কী, configuration-এর ভাষায়?
  • শক্তি: একটি রীতিতে যে language চেনা যায়, অন্যটিতেও কি যায়? (nondeterministic PDA-র জন্য হ্যাঁ, দুই দিকের গঠন দিয়ে প্রমাণ।)
  • সতর্কতা: deterministic PDA-তে কী বদলায়? (অনেক কিছু: empty stack সেখানে দুর্বল।)

কেন এটি জানা দরকার? প্রথমত, পাঠ্যবইগুলো আলাদা রীতি মানে: Sipser-এর বই final state, আর Hopcroft–Motwani–Ullman (HMU)-এর বই দুটিই সংজ্ঞায়িত করে আর প্রায়ই empty stack ব্যবহার করে। দ্বিতীয়ত, পর্ব ৩৪-এর CFG → PDA গঠন empty stack-এ সবচেয়ে স্বাভাবিক: stack-এ থাকে “আর কী derive করা বাকি”, আর কিছু বাকি না থাকলেই কাজ শেষ। তৃতীয়ত, বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় দুই রীতির রূপান্তর আর DPDA-র পার্থক্য প্রায়ই প্রশ্ন হিসেবে আসে।

২ · সংজ্ঞা — L(P) আর N(P)

পর্ব ৩২-এর রীতি সংক্ষেপে মনে করি। PDA P = (Q, Σ, Γ, δ, q0, F), যেখানে Q state-এর সসীম set, Σ input alphabet, Γ stack alphabet, q0 শুরুর state, F ⊆ Q accept state-এর set, আর δ: Q × Σε × Γε → P(Q × Γε)। এখানে Σε = Σ ∪ {ε}, আর P(·) মানে power set. একটি transition লেখা হয় “a, x → y”: input থেকে a পড়া, stack-এর top থেকে x তোলা, তারপর y রাখা। তিন জায়গার যেকোনোটিতে ε চলে। Stack শুরুতে খালি; দরকার হলে PDA প্রথম move-এ নিজেই একটি নিচের চিহ্ন $ রাখে।

সংজ্ঞা ২.১ (configuration আর ⊢)

Configuration হলো (q, w, γ): বর্তমান state q, এখনো না-পড়া input w, আর stack-এর পুরো লেখা γ, যার বাঁ দিকের চিহ্নটি top. এক move-এর সম্পর্ক ⊢:
(q, aw, xβ) ⊢ (r, w, yβ), যদি (r, y) ∈ δ(q, a, x), যেখানে a ∈ Σε আর x, y ∈ Γε.
⊢∗ মানে শূন্য বা তার বেশি move, আর ⊢+ মানে অন্তত একটি move.

সংজ্ঞা ২.২ (final state-এ গ্রহণ)

L(P) = { w ∈ Σ∗ : (q0, w, ε) ⊢∗ (q, ε, γ), কোনো q ∈ F আর কোনো γ ∈ Γ∗-এর জন্য }

কথায়: শুরুর configuration থেকে এমন একটি computation আছে, যা পুরো w পড়ে কোনো accept state-এ পৌঁছায়। Stack-এ তখন কী আছে, তা গুরুত্বহীন।

সংজ্ঞা ২.৩ (empty stack-এ গ্রহণ)

N(P) = { w ∈ Σ∗ : (q0, w, ε) ⊢+ (q, ε, ε), কোনো q ∈ Q-এর জন্য }

কথায়: অন্তত একটি move-এর এমন একটি computation আছে, যা পুরো w পড়ে stack পুরো খালি করে। F এখানে একেবারেই ব্যবহার হয় না; N মানে “null stack”.

চারটি খুঁটিনাটি, যা পরীক্ষায় আর প্রমাণে কাজে লাগে:

  1. পুরো input পড়তেই হবে। দুই রীতিতেই শেষ configuration-এ বাকি input ε. মাঝপথে accept state-এ গেলে বা stack খালি হলে কিছু প্রমাণ হয় না।
  2. একটি পথই যথেষ্ট। PDA সাধারণত nondeterministic; কোনো একটি computation গ্রহণ করলেই w গৃহীত, বাকি পথ আটকে গেলেও।
  3. কেন ⊢+? এই কোর্সের মডেলে stack খালি দিয়ে শুরু হয়। ⊢∗ লিখলে শূন্য move-এই (q0, ε, ε) “সব input পড়া, stack খালি”, তাই প্রতিটি PDA-র N(P)-তে ε ঢুকে যেত। HMU-র বইয়ে stack শুরু হয় একটি start চিহ্ন Z0 নিয়ে, শুরুর configuration (q0, w, Z0), আর সেখানে ⊢∗ লিখলেই চলে। দুই রীতিতে একই শ্রেণির language আসে; শুধু এক রীতির সংজ্ঞা আর গঠন অন্য রীতিতে না মেশানো জরুরি।
  4. মাঝপথে খালি stack. এই মডেলে x = ε এমন move (কিছু না তুলে রাখা) খালি stack-এও চলে, তাই PDA মাঝপথে stack খালি করে আবার চলতে পারে। HMU-র মডেলে প্রতিটি move top থেকে ঠিক একটি চিহ্ন তোলে, তাই সেখানে খালি stack মানে যন্ত্র থেমে যাওয়া। এই পার্থক্য অংশ ৭-এ DPDA-র প্রশ্নে গুরুত্বপূর্ণ হবে।

একটি উদাহরণ। L≥ = {aibj : i ≥ j ≥ 0}, অর্থাৎ আগে a, পরে b, আর b-র সংখ্যা a-র চেয়ে বেশি নয়। এর একটি PDA P≥, F = {q1, q2}:

থেকেtransitionগন্তব্যমানে
q0ε, ε → $q1নিচের চিহ্ন রাখা
q1a, ε → Aq1প্রতিটি a-র জন্য একটি A
q1ε, ε → εq2a শেষ, এবার b (অনুমান)
q2b, A → εq2প্রতিটি b একটি A তোলে

Final state রীতিতে P≥ ঠিক L≥ চেনে: b-র জন্য A না থাকলে move নেই, তাই j > i হলে আটকে যায়; আর বাড়তি A থেকে গেলেও q2 accept state. Empty stack রীতিতে কিন্তু N(P≥) = ∅, কারণ $ কখনো তোলা হয় না। নিচের stepper একটি string-এর পুরো computation দেখায়।

1q0 → q1 : ε, ε → $2q1 → q1 : a, ε → A3q1 → q2 : ε, ε → ε4q2 → q2 : b, A → ε
Configuration
state
বাকি input
stack (top বাঁয়ে)
final state রীতি
empty stack রীতি
  1. শুরু। (q0, aab, ε)। Stack এখন খালি, কিন্তু তিনটি চিহ্ন পড়া বাকি, তাই কোনো রীতিতেই কিছু বলার নেই। এই কারণেই empty stack-এর সংজ্ঞায় শুধু শেষের configuration দেখা হয়।
  2. $ রাখা। ε, ε → $: কিছু না পড়ে, কিছু না তুলে $ রাখা। (q1, aab, $)।
  3. প্রথম a. a, ε → A: (q1, ab, A$)। Top বাঁ দিকে লেখা, তাই নতুন A বাঁয়ে বসল।
  4. দ্বিতীয় a. (q1, b, AA$)। এখানে q1-এ থেকে আরেকটি a-র অপেক্ষাও করা যেত, কিন্তু পরের চিহ্ন b, তাই সেই পথ আটকে যাবে।
  5. অনুমান। ε-move q1 → q2: “a শেষ” বলে অনুমান। Stack অপরিবর্তিত: (q2, b, AA$)।
  6. b পড়া। b, A → ε: একটি A উঠল। (q2, ε, A$)। পুরো input পড়া শেষ।
  7. রায়। Final state রীতিতে q2 ∈ F, তাই aab গৃহীত; stack-এ A$ থাকা কোনো বাধা নয়। Empty stack রীতিতে stack A$, খালি নয়, আর $ তোলার কোনো move নেই, তাই কোনো string-এর জন্যই stack খালি হয় না: N(P≥) = ∅।

এবার কোডে। নিচের simulator পর্ব ৩২-এর মতোই configuration-এর ওপর BFS চালায়, কিন্তু দুই রীতির যেকোনোটিতে। Transition একটি tuple (p, a, x, r, y), যেখানে ফাঁকা string মানে ε। Configuration-এ একটি বাড়তি flag রাখা হয়, “অন্তত একটি move হয়েছে কি না”, যাতে ⊢+ শর্তটি ঠিকভাবে খাটে। Stack-এর দৈর্ঘ্যের একটি সীমা (bound) রাখা হয়েছে, যাতে ε-move দিয়ে অসীম push হলেও খোঁজ শেষ হয়; এখানকার যন্ত্রগুলোর জন্য সীমাটি যথেষ্ট বড়। দ্বিতীয় যন্ত্র Panbn পর্ব ৩২-এর anbn (n ≥ 0)-এর PDA, F = {q1, q4}।

from collections import deque
def run(P, w, mode, bound=10):          # BFS over configurations
    start = (P["q0"], 0, "", False)     # (state, symbols read, stack, moved?)
    parent, todo = {start: None}, deque([start])
    while todo:
        c = todo.popleft(); q, i, st, moved = c
        if i == len(w) and (q in P["F"] if mode == "final" else st == "" and moved):
            path = []
            while c: path.append(c); c = parent[c]
            return path[::-1]           # one accepting computation
        for p, a, x, r, y in P["d"]:    # move "a, x -> y" from p to r
            if p == q and w.startswith(a, i) and st.startswith(x):
                n = (r, i + len(a), y + st[len(x):], True)
                if len(n[2]) <= bound and n not in parent:
                    parent[n] = c; todo.append(n)
    return None
P_ge = {"q0": "q0", "F": {"q1", "q2"},            # a^i b^j with i >= j
        "d": [("q0", "", "", "q1", "$"), ("q1", "a", "", "q1", "A"),
              ("q1", "", "", "q2", ""), ("q2", "b", "A", "q2", "")]}
P_anbn = {"q0": "q1", "F": {"q1", "q4"},          # a^n b^n, n >= 0
          "d": [("q1", "", "", "q2", "$"), ("q2", "a", "", "q2", "A"),
                ("q2", "b", "A", "q3", ""), ("q3", "b", "A", "q3", ""),
                ("q3", "", "$", "q4", "")]}
yn = lambda path: "yes" if path else "no"
print("w      P_ge: final empty   P_anbn: final empty")
for w in ["", "a", "ab", "aab", "abb", "aabb"]:
    print(f"{w or 'ε':6} {yn(run(P_ge, w, 'final')):>11} {yn(run(P_ge, w, 'empty')):>5}"
          f" {yn(run(P_anbn, w, 'final')):>13} {yn(run(P_anbn, w, 'empty')):>5}")
show = lambda c: f"({c[0]}, {'aab'[c[1]:] or 'ε'}, {c[2] or 'ε'})"
print("P_ge, final state, aab:", " ⊢ ".join(map(show, run(P_ge, "aab", "final"))))

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

w      P_ge: final empty   P_anbn: final empty
ε              yes    no           yes    no
a              yes    no            no    no
ab             yes    no           yes   yes
aab            yes    no            no    no
abb             no    no            no    no
aabb           yes    no           yes   yes
P_ge, final state, aab: (q0, aab, ε) ⊢ (q1, aab, $) ⊢ (q1, ab, A$) ⊢ (q1, b, AA$) ⊢ (q2, b, AA$) ⊢ (q2, ε, A$)

P≥-এর empty কলাম পুরোটাই no: N(P≥) = ∅, ঠিক stepper-এর মতো। শেষ লাইনের computation-ও stepper-এর ছয়টি configuration-এর সঙ্গে হুবহু মেলে। Panbn-এ দুই কলাম প্রায় এক, শুধু ε-তে আলাদা: শুরুর state q1 নিজেই accept state, তাই শূন্য move-এ ε গৃহীত, কিন্তু empty stack-এ অন্তত একটি move লাগে, আর প্রথম move-ই $ রাখে। anbn (n ≥ 1)-এর শেষে $ উঠে যায়, তাই সেখানে দুই রীতি একমত। শিক্ষা: একই transition-এর তালিকা দুই রীতিতে দুটি আলাদা যন্ত্র।

৩ · কোন নকশা কোন রীতিতে সহজ

অংশ ৪ আর ৫-এ প্রমাণ হবে যে দুই রীতির শক্তি সমান। তাই নকশার সময় যে রীতিতে কাজ সহজ, সেটিই বেছে নেওয়া যায়, পরে যান্ত্রিকভাবে রূপান্তর। দুটি উদাহরণ দুই দিকের সুবিধা দেখায়।

সুষম বন্ধনী: empty stack সহজ। BAL (পর্ব ২৫-এর Dyck language, S → (S)S ∣ ε)-এর জন্য empty stack রীতিতে একটি state q আর দুটি transition যথেষ্ট: “(, ε → X” আর “), X → ε”। প্রতিটি খোলা বন্ধনী একটি X রাখে, প্রতিটি বন্ধ বন্ধনী একটি X তোলে। Stack খালি মানে ঠিক “সব খোলা বন্ধনী বন্ধ”। N(Pbal) = BAL − {ε}, কারণ ε-তে কোনো move হয় না। ε-ও চাইলে q-তে একটি “ε, ε → ε” loop যোগ করলেই চলে: তখন একটি move-এ খালি stack-এ পৌঁছানো যায়। লক্ষ করুন, ()() পড়ার সময় মাঝখানে stack খালি হয়, তারপর আবার ভরে; এই মডেলে তা বৈধ।

একই language final state রীতিতে নিতে $ লাগে, কারণ PDA জানতে চায় “stack-এ আর X নেই”: q0 (accept) থেকে ε, ε → $ দিয়ে q1; q1-এ একই দুটি loop; আর q1 থেকে ε, $ → ε দিয়ে q2 (accept). তিনটি state, চারটি transition, F = {q0, q2}। Scratch-এ দৈর্ঘ্য ৮ পর্যন্ত দুটি যন্ত্রই BAL-এর ২৩টি string দেয় (প্রথমটি ε বাদে ২২টি, loop যোগ করলে ২৩টি)।

L≥: final state সহজ। P≥ বাড়তি A নিয়ে মাথা ঘামায় না। Empty stack রীতিতে বাড়তি A আর $ ঝেড়ে ফেলতে হয়: q2-এ দুটি নতুন loop “ε, A → ε” আর “ε, $ → ε”। এটি ঠিক কাজ করে (দৈর্ঘ্য ৮ পর্যন্ত ২৫টি string, brute force-এ মেলানো), কিন্তু একটি সূক্ষ্মতা আছে: এখন যন্ত্রটি b পড়ার আগেও A তুলে ফেলতে পারে। তাতে ক্ষতি নেই, কারণ আগে A তুললে পরে কম b পড়া যায়, বেশি নয়; i ≥ j শর্ত ভাঙে না। এমন যুক্তি প্রতিবার লাগে বলেই “বাকি stack ঝাড়ার” কাজটি সাধারণ গঠনে একবারে করে রাখা ভালো।

LanguageFinal stateEmpty stack
BAL৩ state, $ লাগে১ state, ২ transition
L≥ = {aibj : i ≥ j}৩ state, বাড়তি A উপেক্ষাবাড়তি A আর $ ঝাড়ার loop লাগে
wwR (জোড় palindrome)$ দিয়ে শেষ চেনামাঝখান অনুমান, তারপর মিলিয়ে তোলা (অনুশীলন ১)
Regular language, যেমন a∗bDFA-টিই, stack অব্যবহৃতstack খালি রাখতে হয়, শেষে খালি থাকা নিশ্চিত করতে হয়

একটি নিয়ম মনে রাখুন: “গোনা শেষে শূন্য হতে হবে” ধরনের language (বন্ধনী, সমান সংখ্যা, palindrome) empty stack-এ স্বাভাবিক। “অন্তত এতগুলো” বা “বাকিটা যা খুশি” ধরনের language final state-এ স্বাভাবিক। পরীক্ষায় রীতি বলা না থাকলে যেটি সহজ সেটিতে নকশা করে কোন রীতি মানছেন তা এক লাইনে লিখে দিন।

৪ · Final state থেকে empty stack — গঠন আর প্রমাণ

উপপাদ্য ৪.১

প্রতিটি PDA P-এর জন্য একটি PDA P′ আছে, যাতে N(P′) = L(P). P′ একটি algorithm দিয়ে P থেকে বানানো যায়।

ধারণাটি সরল: P-কে হুবহু চালানো, আর P যখনই কোনো accept state-এ থাকে, তখন ইচ্ছা করলে একটি নতুন drain state qe-তে চলে গিয়ে stack-এর সবকিছু তুলে ফেলা। কিন্তু একটি বিপদ আছে। P নিজেও কোনো non-accept state-এ পুরো input পড়ে stack খালি করে ফেলতে পারে, আর তখন P′ ভুল করে গ্রহণ করবে। তাই P′ শুরুতেই নিজের একটি নতুন চিহ্ন # stack-এর একদম নিচে রাখে। # ∉ Γ, তাই P-এর কোনো transition # তুলতে পারে না; শুধু qe পারে।

গঠন। P′ = (Q ∪ {qs, qe}, Σ, Γ ∪ {#}, δ′, qs, ∅), যেখানে qs, qe নতুন state আর δ′-এ চার রকম transition:

  1. শুরু: qs থেকে “ε, ε → #” দিয়ে q0.
  2. নকল: P-এর প্রতিটি transition অপরিবর্তিত।
  3. প্রস্থান: প্রতিটি f ∈ F থেকে “ε, ε → ε” দিয়ে qe.
  4. ঝাড়া: প্রতিটি x ∈ Γ ∪ {#}-এর জন্য qe-তে loop “ε, x → ε”।

দুই দিকের রূপান্তরের ছক

ড্যাশ দেওয়া বাক্সটি মূল PDA P, ভেতরে কিছু বদলায় না। কমলা অংশগুলো নতুন: শুরুর state, নতুন bottom marker #, আর শেষের state. দুই দাগের বৃত্ত accept state.

Final state থেকে empty stack, আর empty stack থেকে final state (ক) final state → empty stack P qsq0fqe ⋯ ε,ε→#ε,ε→ε ε, x → εx ∈ Γ∪{#} F থেকে qe, সেখানে stack ঝেড়ে খালি (খ) empty stack → final state P qss0q0qqf ⋯ ε,ε→# q0-র তীরের কপি ε,#→ε P-এর প্রতিটি q থেকে qf-এ
ছবি ৩৩.১ — (ক)-তে # নিশ্চিত করে stack শুধু qe-তে খালি হয়। (খ)-তে # top-এ আসা মানে P-এর stack খালি; s0 হলো q0-র এমন কপি, যেখানে আর কখনো ফেরা হয় না।

প্রমাণ। এটি একটি simulation argument. প্রথমে একটি সহায়ক দাবি, যা দুই দিকেই লাগবে:

দাবি: P-এ (q0, w, ε) ⊢∗ (q, v, γ) হয় ঠিক তখন, যখন P′-এ শুধু “নকল” transition দিয়ে (q0, w, #) ⊢∗ (q, v, γ#) হয়। কারণ: P-এর কোনো transition # পড়ে না বা তোলে না, আর কোনো transition-ই top-এর নিচে দেখে না; তাই নিচে একটি # থাকলে P-এর প্রতিটি move হুবহু একই থাকে, আর উল্টোটাও। (ধাপের সংখ্যার ওপর induction-এ লিখলে এক লাইনের প্রমাণ।)

  1. L(P) ⊆ N(P′): ধরুন w ∈ L(P), অর্থাৎ (q0, w, ε) ⊢∗ (f, ε, γ), f ∈ F. তাহলে P′-এ (qs, w, ε) ⊢ (q0, w, #) ⊢∗ (f, ε, γ#) ⊢ (qe, ε, γ#), তারপর |γ| + 1টি ঝাড়ার move-এ (qe, ε, ε)। অন্তত একটি move হয়েছে, তাই w ∈ N(P′)। — দাবি, তারপর প্রস্থান আর ঝাড়া
  2. N(P′) ⊆ L(P), ধাপ ক: ধরুন w ∈ N(P′)। প্রথম move-ই # রাখে, আর # কেবল qe-র loop তুলতে পারে। শেষ configuration-এ stack খালি, তাই # উঠেছে, তাই computation qe-তে পৌঁছেছে। — # ∉ Γ
  3. ধাপ খ: qe-তে ঢোকার একমাত্র পথ কোনো f ∈ F থেকে প্রস্থান-transition, আর qe থেকে বেরোনোর পথ নেই। qe-র কোনো move input পড়ে না, তাই প্রস্থানের মুহূর্তেই বাকি input ε ছিল: (q0, w, #) ⊢∗ (f, ε, γ#), শুধু নকল transition দিয়ে। — qe-র গঠন
  4. ধাপ গ: দাবি অনুযায়ী P-এ (q0, w, ε) ⊢∗ (f, ε, γ), তাই w ∈ L(P). ∎ — দাবির উল্টো দিক

আকার: P′-এ |Q| + 2টি state, আর transition বাড়ে |F| + |Γ| + 2টি। নিচের stepper গঠনটি P≥-এর ওপর চালায়, তারপর aab-এর computation-এর শেষ অংশ দেখায়।

1qs → q0 : ε, ε → #2P≥-এর ৪টি transition3q1, q2 → qe : ε, ε → ε4qe → qe : ε, A → ε5qe → qe : ε, $ → ε6qe → qe : ε, # → ε
এই ধাপে
configuration
move-সংখ্যা
  1. শুরু। নতুন qs প্রথম move-এ # রাখে: (qs, aab, ε) ⊢ (q0, aab, #). এরপর যা-ই ঘটুক, # তোলা না পর্যন্ত stack খালি হবে না।
  2. নকল। P≥-এর চারটি transition অপরিবর্তিত। আগের stepper-এর পাঁচটি move হুবহু চলে, শুধু সবার নিচে বাড়তি #: (q2, ε, A$#), মোট ৬টি move.
  3. প্রস্থান। q2 ∈ F, তাই “ε, ε → ε” দিয়ে qe. Input আগেই শেষ; qe আর কিছু পড়বে না। (q1 থেকেও একই প্রস্থান আছে, কারণ q1-ও accept state.)
  4. A ঝাড়া। “ε, A → ε”: (qe, ε, $#).
  5. $ ঝাড়া। “ε, $ → ε”: (qe, ε, #). মূল P≥ নিজে কখনো $ তুলত না; ঝাড়ার loop Γ-এর সব চিহ্নের জন্য থাকে বলেই পারছে।
  6. খালি। “ε, # → ε”: (qe, ε, ε), ১০টি move-এ। aab ∈ N(P′)। আর abb-এর মতো string-এ P≥ পুরো input পড়ে কখনো F-এ পৌঁছায় না, তাই # কখনো ওঠে না।

# কেন সত্যিই দরকার? P≥-এ # বাদ দিলেও ক্ষতি হতো না, কারণ P≥ নিজে কখনো stack খালি করে না। কিন্তু এই যন্ত্রটি দেখুন, L(Pc) = {anbnc : n ≥ 0}, F = {q4}: q0 থেকে $ রেখে q1; q1-এ a, ε → A; ε-তে q2; q2-এ b, A → ε; q2 থেকে ε, $ → ε দিয়ে q3; q3 থেকে c পড়ে q4. ab পড়লে Pc পৌঁছায় (q3, ε, ε)-এ: input শেষ, stack খালি, কিন্তু q3 accept state নয়। # ছাড়া P′ এটিকে empty stack-এ গ্রহণ করে ফেলবে। পরের অংশের Python ব্লক ঠিক এই ভুলটি ধরে।

৫ · Empty stack থেকে final state — # দিয়ে খালি stack চেনা

উপপাদ্য ৫.১

প্রতিটি PDA P-এর জন্য একটি PDA P″ আছে, যাতে L(P″) = N(P). P″ একটি algorithm দিয়ে P থেকে বানানো যায়।

এবার উল্টো সমস্যা: P stack খালি করলে P″-কে একটি accept state-এ যেতে হবে। কিন্তু এই মডেলে PDA সরাসরি জিজ্ঞেস করতে পারে না “stack কি খালি?”। x = ε এমন transition খালি আর ভরা দুই stack-এই চলে, আর x ∈ Γ এমন transition শুধু বলে “top-এ x আছে”। তাই আবার নতুন bottom marker #: P-এর stack খালি হলে P″-এর top-এ # দেখা যায়, আর # দেখলেই accept state-এ যাওয়া।

সরল চেষ্টা: qs থেকে “ε, ε → #” দিয়ে q0, P-এর সব transition, আর P-এর প্রতিটি state q থেকে “ε, # → ε” দিয়ে নতুন accept state qf. প্রায় ঠিক, কিন্তু একটি ফাঁদ আছে: শুরুর মুহূর্তে, P একটিও move করার আগে, top-এ # আছে। ε-র জন্য P″ সঙ্গে সঙ্গে qf-এ চলে যায়, অথচ N(P)-তে অন্তত একটি move লাগে। Pbal-এর মতো যন্ত্রে ε ∉ N(P), কিন্তু সরল P″ ε গ্রহণ করবে।

সঠিক গঠন: P″ = (Q ∪ {qs, s0, qf}, Σ, Γ ∪ {#}, δ″, qs, {qf}), যেখানে

  1. শুরু: qs থেকে “ε, ε → #” দিয়ে s0.
  2. শুরুর কপি: q0-এর প্রতিটি transition (q0, a, x) → (r, y)-এর একটি কপি s0 থেকে, একই গন্তব্য r-এ। s0-এ কোনো তীর ঢোকে না, তাই সেখানে শুধু শুরুতে থাকা যায়।
  3. নকল: P-এর সব transition অপরিবর্তিত।
  4. প্রস্থান: প্রতিটি q ∈ Q থেকে “ε, # → ε” দিয়ে qf. s0 থেকে নয়। qf থেকে কোনো move নেই।

প্রমাণ।

  1. N(P) ⊆ L(P″): ধরুন (q0, w, ε) ⊢+ (q, ε, ε)। এর প্রথম move q0 থেকে কোনো r-এ; P″-এ একই move s0 থেকে কপি হিসেবে আছে। তাই (qs, w, ε) ⊢ (s0, w, #) ⊢ ⋯ ⊢ (q, ε, #) ⊢ (qf, ε, ε), আর qf ∈ F″. — অংশ ৪-এর দাবির মতো, # নিচে রেখে নকল
  2. L(P″) ⊆ N(P), ধাপ ক: ধরুন P″ পুরো w পড়ে qf-এ পৌঁছায়। qf-এ ঢোকার একমাত্র পথ কোনো q ∈ Q থেকে “ε, # → ε”, আর qf থেকে কোনো move নেই; তাই সেই মুহূর্তে input শেষ আর top-এ #, অর্থাৎ নকল-করা stack খালি। — qf-এর গঠন
  3. ধাপ খ: qf-এর আগে computation-টি qs → s0 → (s0 থেকে অন্তত একটি কপি move) → ⋯ → q. s0-কে q0 দিয়ে বদলালে P-এর একটি computation (q0, w, ε) ⊢+ (q, ε, ε) পাওয়া যায়। তাই w ∈ N(P). ∎ — s0 থেকে প্রস্থান নেই, তাই অন্তত একটি move
1q → q : (, ε → X2q → q : ), X → ε3qs → q : ε, ε → # (সরল)4q → qf : ε, # → ε5qs → s0 : ε, ε → #6s0 → q : q-এর ২টি তীরের কপি
এই ধাপে
যন্ত্র
computation
  1. মূল যন্ত্র। Pbal: একটি state q, দুটি loop. () পড়ে দুই move-এ stack খালি, তাই () ∈ N(Pbal). ε-তে কোনো move নেই, তাই ε ∉ N(Pbal).
  2. সরল চেষ্টা। qs # রেখে q-তে যায়, আর q থেকে “ε, # → ε” দিয়ে qf. # top-এ মানে Pbal-এর stack খালি।
  3. ফাঁদ। Input ε: # রাখার পরেই top-এ #, তাই qf. Pbal একটিও move না করেই “খালি stack” পেল। L(সরল P″) = BAL, অথচ N(Pbal) = BAL − {ε}: একটি বাড়তি string.
  4. সমাধান। qs # রেখে যায় নতুন s0-এ। s0-তে q-এর দুটি transition-এর কপি (গন্তব্য q), কিন্তু s0 থেকে qf-এ প্রস্থান নেই। প্রস্থান শুধু q থেকে।
  5. () চালানো। s0-এর কপি-transition ( পড়ে X রেখে q-তে যায়; তারপর ) X তোলে; top-এ #, তাই qf. ৪টি move-এ গৃহীত, যেমন হওয়া উচিত।
  6. ε চালানো। # রেখে s0-এ পৌঁছানোর পর কোনো move নেই: s0-এর একমাত্র চলতে-পারা তীর ( পড়ে, আর ( নেই। তাই ε প্রত্যাখ্যাত। (() -র মতো string-এ শেষে stack X#, top-এ X, তাই qf অধরা।

দুটি রূপান্তর আর দুটি ফাঁদ এবার কোডে। আগের ব্লকের run এখানে কাজে লাগে (data-shared). to_empty অংশ ৪-এর গঠন, to_final অংশ ৫-এর; fix=False দিলে প্রথমটি # ছাড়া, দ্বিতীয়টি s0 ছাড়া বানায়। প্রতিটি যন্ত্রের জন্য তিনটি brute force তুলনা হয়, দৈর্ঘ্য ৭ পর্যন্ত সব string-এ: মূল যন্ত্রের language একটি স্বাধীন সংজ্ঞার (ref) সঙ্গে মেলে কি না, সঠিক রূপান্তর একই language দেয় কি না, আর ভুল রূপান্তর কোন বাড়তি string নেয়।

from itertools import product
import re
def strings(n, sigma):                  # every string of length <= n
    return ("".join(t) for k in range(n + 1) for t in product(sigma, repeat=k))
def lang(P, mode, n, sigma): return {w for w in strings(n, sigma) if run(P, w, mode)}
def to_empty(P, fix=True):              # L(P) = N(P'): drain from F
    d = [("qs", "", "", P["q0"], "#" if fix else "")] + P["d"]
    d += [(f, "", "", "qe", "") for f in P["F"]]
    d += [("qe", "", x, "qe", "") for x in {t[4] for t in P["d"] if t[4]} | {"#"}]
    return {"q0": "qs", "F": set(), "d": d}
def to_final(P, fix=True):              # N(P) = L(P''): escape on #
    s = "s0" if fix else P["q0"]        # s0: copy of q0, never re-entered
    d = [("qs", "", "", s, "#")] + P["d"]
    if fix: d += [(s, a, x, r, y) for p, a, x, r, y in P["d"] if p == P["q0"]]
    Q = {t[0] for t in P["d"]} | {t[3] for t in P["d"]}
    return {"q0": "qs", "F": {"qf"}, "d": d + [(q, "", "#", "qf", "") for q in Q]}
P_c = {"q0": "q0", "F": {"q4"},                   # a^n b^n c, final state
       "d": [("q0", "", "", "q1", "$"), ("q1", "a", "", "q1", "A"),
             ("q1", "", "", "q2", ""), ("q2", "b", "A", "q2", ""),
             ("q2", "", "$", "q3", ""), ("q3", "c", "", "q4", "")]}
P_bal = {"q0": "q", "F": set(),                   # BAL - {ε}, empty stack
         "d": [("q", "(", "", "q", "X"), ("q", ")", "X", "q", "")]}
tests = [("P_ge", P_ge, "final", "ab", lambda w: re.fullmatch("a*b*", w)
          and w.count("a") >= w.count("b")),
         ("P_c", P_c, "final", "abc", lambda w: re.fullmatch("a*b*c", w)
          and w.count("a") == w.count("b")),
         ("P_bal", P_bal, "empty", "()", lambda w: w and w.count("(") == w.count(")")
          and all(w[:i].count("(") >= w[:i].count(")") for i in range(len(w))))]
for name, P, mode, sigma, ref in tests:
    conv, other = (to_empty, "empty") if mode == "final" else (to_final, "final")
    L = lang(P, mode, 7, sigma)
    good, bad = (lang(conv(P, fix), other, 7, sigma) for fix in (True, False))
    print(f"{name:5}: ref {L == {w for w in strings(7, sigma) if ref(w)}}, "
          f"converted {good == L}, unfixed extra {sorted(bad - L, key=len)}")

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

P_ge : ref True, converted True, unfixed extra []
P_c  : ref True, converted True, unfixed extra ['', 'ab', 'aabb', 'aaabbb']
P_bal: ref True, converted True, unfixed extra ['']

তিনটি যন্ত্রই নিজের স্বাধীন সংজ্ঞার সঙ্গে মেলে, আর সঠিক রূপান্তর তিনটিতেই একই language দেয়। ভুল সংস্করণের ফল শিক্ষণীয়। P≥-এ # না রাখলেও বাড়তি কিছু নেই, কারণ P≥ নিজে stack খালি করে না; অর্থাৎ একটি-দুটি উদাহরণে ঠিক চলা মানে গঠন ঠিক, এমন নয়। Pc-এ # ছাড়া রূপান্তর ε, ab, aabb, aaabbb নিয়ে নেয়: ঠিক যেসব anbn-এ Pc q3-এ খালি stack নিয়ে থামে, যা অংশ ৪-এর শেষে বলা হয়েছিল। Pbal-এ s0 ছাড়া রূপান্তর শুধু ε বাড়তি নেয়, stepper-এর ফাঁদটি। দুটি ভুলই এমন জায়গায়, যা হাতে দুটি-একটি string পরীক্ষা করে সহজে চোখে পড়ে না।

ফলাফল ৫.২

একটি language কোনো PDA-র L(P) হয় ঠিক তখন, যখন সেটি কোনো PDA-র N(P′)। পর্ব ৩৪-এ দেখা যাবে, দুটিই ঠিক context-free language-এর শ্রেণি।

একটি তৃতীয় রীতিও আছে: “accept state-এ আর stack খালি, দুটিই একসঙ্গে”। একই ধরনের গঠনে এটিও সমান শক্তির: P′-এর qe-কে accept state বানালেই final state থেকে এই রীতিতে আসা যায়। পরের অংশের library-তে এমন একটি mode-এর নাম আছে, কিন্তু তার মানে অন্য।

৬ · সত্যিকারের run — automata-lib-এ গ্রহণের mode

Python-এর automata-lib (MIT লাইসেন্স) PDA-কে সরাসরি দুই রীতিতে চালাতে পারে: NPDA class-এর acceptance_mode প্যারামিটার নেয় 'final_state', 'empty_stack' বা 'both'. এর মডেল HMU-র মতো: stack শুরু হয় একটি চিহ্ন (initial_stack_symbol) নিয়ে, আর প্রতিটি move top-এর চিহ্নটি তুলে একটি string রাখে। Scratch-এর একটি uv project-এ (automata-lib 9.2.0, Python 3.12.13) L≥-এর যন্ত্র, তার empty-stack রূপান্তর আর BAL-এর এক-state যন্ত্র চালানো হয়েছে। এটি একটি সত্যিকারের run; আউটপুট হুবহু, শুধু path বাদ। L≥-এর যন্ত্রটি এই মডেলে এভাবে লেখা:

GE = {"q1": {"a": {"Z": {("q1", ("A", "Z"))}, "A": {("q1", ("A", "A"))}},
             "": {"Z": {("q2", "Z")}, "A": {("q2", "A")}}},
      "q2": {"b": {"A": {("q2", "")}}}}          # final_states = {q1, q2}
~/bazarghar-toc$ uv run python modes_lib.py
automata-lib 9.2.0 | Python 3.12.13
GE  final_state: ['', 'a', 'aa', 'ab', 'aaa', 'aab', 'aaaa', 'aaab', 'aabb']
GE  empty_stack: []
GE  both       : ['', 'a', 'aa', 'ab', 'aaa', 'aab', 'aaaa', 'aaab', 'aabb']
GEe empty_stack == GE final_state up to length 8: True (25 strings)
BAL empty_stack: ['', '()', '(())', '()()']
BAL final_state: []

চারটি শিক্ষা। প্রথম, একই GE যন্ত্র final_state-এ দৈর্ঘ্য ৪ পর্যন্ত L≥-এর ৯টি string দেয়, আর empty_stack-এ কিছুই নয়, কারণ নিচের Z কখনো ওঠে না; অংশ ২-এর N(P≥) = ∅-এর সঙ্গে হুবহু মিল। দ্বিতীয়, 'both'-এর ফল final_state-এর মতোই। Library-র উৎস কোড (_has_accepted) পড়ে দেখা গেছে, এখানে “both” মানে দুটির যেকোনো একটি শর্ত পূরণ হলেই গ্রহণ, “দুটিই একসঙ্গে” নয়। নাম দেখে অনুমান না করে documentation বা কোড দেখা জরুরি। তৃতীয়, GEe হলো অংশ ৪-এর গঠন এই মডেলে হাতে লেখা (নতুন নিচের চিহ্ন # তার ওপর Z, প্রতিটি accept state থেকে ঝাড়ার state-এ ε-move); দৈর্ঘ্য ৮ পর্যন্ত ২৫টি string-এ এর empty_stack ফল মূল যন্ত্রের final_state ফলের সঙ্গে মেলে। চতুর্থ, BAL-এর যন্ত্রে এখানে একটি বাড়তি move “ε, Z → ε” আছে, যা শুরুর Z তুলতে পারে; তাই ε-ও গৃহীত। HMU মডেলে শুরুতে stack খালি নয়, তাই ⊢+-এর প্রশ্নই ওঠে না।

৭ · DPDA-র ক্ষেত্রে সাবধান — empty stack আর prefix-free language

এ পর্যন্ত সব কথা nondeterministic PDA-র। Deterministic PDA (DPDA)-তে প্রতিটি configuration-এ বড়জোর একটি move সম্ভব: একই (state, input চিহ্ন, top)-এর জন্য একাধিক move নেই, আর কোনো (state, top)-এর জন্য ε-move থাকলে সেই জোড়ায় কোনো input-পড়া move থাকে না। এদের চেনা language-গুলো deterministic CFL (DCFL); বিস্তারিত পর্ব ৩৫-এ। এখানে শুধু একটি প্রশ্ন: DPDA-র জন্য দুই রীতি কি সমান? উত্তর, না।

সংজ্ঞা ৭.১ (prefix-free)

Language L prefix-free, যদি L-এর কোনো string L-এর অন্য কোনো string-এর proper prefix না হয়: u, v ∈ L আর u ≠ v হলে v ≠ ux যেকোনো x-এর জন্য।

উদাহরণ: {anbn : n ≥ 1} prefix-free (ab-এর পরে কিছু জুড়লে আর anbn থাকে না)। a∗ নয় (a, aa দুটিই আছে)। {wcwR} prefix-free, কারণ প্রতিটি string-এ c ঠিক একবার, তাই দুটির c একই জায়গায় হলে string দুটি এক। আর যেকোনো L-এর জন্য L$ = {w$ : w ∈ L}, যেখানে $ ∉ Σ, prefix-free, কারণ $ শুধু শেষে আসে।

নিচের উপপাদ্যের জন্য মডেলটি স্পষ্ট করতে হবে: HMU-র রীতির DPDA, যেখানে stack শুরু হয় Z দিয়ে আর প্রতিটি move top থেকে ঠিক একটি চিহ্ন তোলে (তারপর একটি string রাখে)। এ মডেলে stack খালি হলে আর কোনো move সম্ভব নয়, যন্ত্র থেমে যায়।

উপপাদ্য ৭.২

উপরের মডেলের যেকোনো DPDA D-এর জন্য N(D) prefix-free.

প্রমাণ:

  1. ধরুন u ∈ N(D) আর x ≠ ε. D-এর u-র ওপর একমাত্র computation (q0, u, Z) ⊢∗ (q, ε, ε)। — N(D)-এর সংজ্ঞা আর determinism
  2. ux-এর ওপরও D-কে ঠিক একই move-গুলো করতে হয়: প্রতিটি মুহূর্তে যেখানে u-র computation ε-move করেছে, সেখানে input-পড়া move নিষিদ্ধ; আর যেখানে u-র একটি চিহ্ন পড়েছে, সেখানে ε-move নেই। তাই (q0, ux, Z) ⊢∗ (q, x, ε)। — DPDA-র শর্ত
  3. Stack খালি, তাই আর কোনো move নেই; x পড়া বাকি থেকে যায়। এই একমাত্র computation-এ ux-এর জন্য কখনো stack খালি আর input শেষ একসঙ্গে হয় না। তাই ux ∉ N(D). ∎ — প্রতিটি move top তোলে

উল্টো দিকটিও সত্য, আর HMU-র বইয়ের DPDA অংশে আছে: L = N(D) কোনো DPDA D-এর জন্য, যদি আর কেবল যদি L prefix-free এবং L = L(D′) কোনো DPDA D′-এর জন্য। প্রমাণের রূপরেখা (⇐): D′-এর নিচে একটি নতুন চিহ্ন রাখা হয় (অংশ ৪-এর মতো), আর D′ কোনো accept state-এ পৌঁছানোমাত্র ঝাড়ার state-এ গিয়ে stack খালি করে। এতে determinism ভাঙে না, কারণ accept state-এর বাকি move-গুলো বাদ দেওয়া হয়; আর বাদ দিলে ক্ষতি নেই, কারণ L prefix-free, তাই গৃহীত string-এর পরে কিছু জুড়লে তা আর L-এ থাকে না। (⇒)-এর জন্য অংশ ৫-এর গঠনটিই deterministic থাকে, কারণ # top-এ থাকলে একমাত্র move qf-এ যাওয়া।

ফলাফলগুলো:

  • a∗ regular, তাই একটি DPDA final state-এ সহজেই চেনে (DFA-টিই যথেষ্ট); কিন্তু কোনো DPDA empty stack-এ চেনে না। তাই empty stack-এর DPDA এমনকি সব regular language-ও চেনে না।
  • DPDA-র জন্য final state-ই সঠিক সংজ্ঞা: এর শ্রেণিটি ঠিক DCFL. Empty stack-এর শ্রেণিটি ঠিক prefix-free DCFL.
  • সমাধান endmarker: L যেকোনো DCFL হলে L$ prefix-free DCFL, তাই কোনো DPDA একে empty stack-এ চেনে। বাস্তবের parser ঠিক এটিই করে: input-এর শেষে একটি “end of file” token.
1δ(p, a, Z) = (p, AZ)2δ(p, a, A) = (p, AA)3δ(p, b, A) = (r, ε)4δ(r, b, A) = (r, ε)5δ(r, ε, Z) = (r, ε)
Configuration
state
বাকি input
stack
  1. শুরু। D1 empty stack-এ {anbn : n ≥ 1} চেনে। Input abab, stack-এ শুধু Z. প্রতিটি move top থেকে একটি চিহ্ন তোলে, তারপর একটি string রাখে।
  2. a. δ(p, a, Z) = (p, AZ): Z তুলে AZ রাখা, অর্থাৎ ফলত A যোগ। (p, bab, AZ).
  3. b. δ(p, b, A) = (r, ε): A উঠল। (r, ab, Z). এ পর্যন্ত পড়া হয়েছে ab.
  4. ε-move. (r, Z)-এর জন্য একটি ε-move আছে, তাই determinism অনুযায়ী এখানে input পড়ার কোনো move থাকতে পারে না। Z উঠে গেল: (r, ab, ε)। ab-এর জন্য এখানেই computation শেষ হতো, তাই ab ∈ N(D1).
  5. থেমে যাওয়া। Stack খালি, তোলার মতো top নেই, কোনো move নেই। ab পড়া বাকি, তাই abab প্রত্যাখ্যাত। ab গৃহীত হওয়ার ঠিক এই কারণেই abab, বা ab-এর পরে যা-ই জুড়ুন, গৃহীত হতে পারে না: উপপাদ্য ৭.২ এই একটি run-এ।

শেষ ব্লকে এই মডেলের একটি ছোট deterministic simulator. D1 empty stack-এ {anbn : n ≥ 1}; D2 final state-এ (anbn)-ব্লকের এক বা একাধিক জোড়া, যেমন ab, abab, aabbab (একে L2 বলি); D3 হলো D2-র সঙ্গে একটি move, “$ পড়ে Z তোলা”, যা empty stack-এ L2$ চেনে। প্রতিটির language দৈর্ঘ্য ৮ পর্যন্ত একটি regex-ভিত্তিক সংজ্ঞার সঙ্গে মেলানো হয়, আর কোনো string অন্যটির prefix কি না খোঁজা হয়।

from itertools import product
import re
def drun(D, w):                 # DPDA, book style: stack starts as "Z",
    q, st, i, fin = D["q0"], "Z", 0, False   # every move pops the top
    while True:
        fin |= i == len(w) and q in D["F"]   # final state after all input
        if not st: break                      # empty stack: machine stops
        a, m = "", D["d"].get((q, "", st[0]))  # an ε-move excludes the rest
        if m is None and i < len(w):
            a, m = w[i], D["d"].get((q, w[i], st[0]))
        if m is None: break
        q, st, i = m[0], m[1] + st[1:], i + len(a)
    return fin, i == len(w) and st == ""     # (final state, empty stack)
core = {("p", "a", "Z"): ("p", "AZ"), ("p", "a", "A"): ("p", "AA"),
        ("p", "b", "A"): ("r", ""), ("r", "b", "A"): ("r", "")}
D1 = {"q0": "p", "F": set(), "d": {**core, ("r", "", "Z"): ("r", "")}}
D2 = {"q0": "p", "F": {"f"}, "d": {**core, ("r", "", "Z"): ("f", "Z"),
                                    ("f", "a", "Z"): ("p", "AZ")}}
D3 = {"q0": "p", "F": set(), "d": {**D2["d"], ("f", "$", "Z"): ("f", "")}}
strings = lambda sigma, n=8: sorted(map("".join, (t for k in range(n + 1)
                  for t in product(sigma, repeat=k))), key=lambda w: (len(w), w))
lang = lambda D, mode, sigma: [w for w in strings(sigma) if drun(D, w)[mode == "empty"]]
def prefix_pair(L):             # u, w in L with u a proper prefix of w
    return next(((u, w) for u in L for w in L if u != w and w.startswith(u)), None)
blocks = lambda w: re.fullmatch("(a+b+)+", w) and all(
    len(x) == len(y) for x, y in re.findall("(a+)(b+)", w))
for name, D, mode, sigma, ref in [
        ("D1", D1, "empty", "ab", lambda w: re.fullmatch("a+b+", w) and blocks(w)),
        ("D2", D2, "final", "ab", blocks),
        ("D3", D3, "empty", "ab$", lambda w: w.endswith("$") and blocks(w[:-1]))]:
    L = lang(D, mode, sigma)
    ok = L == [w for w in strings(sigma) if ref(w)]
    print(f"{name} by {mode:5}: {len(L)} strings, correct {ok}, first {L[:3]},"
          f" prefix pair {prefix_pair(L)}")
print("D2 by empty stack:", lang(D2, "empty", "ab"))

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

D1 by empty: 4 strings, correct True, first ['ab', 'aabb', 'aaabbb'], prefix pair None
D2 by final: 15 strings, correct True, first ['ab', 'aabb', 'abab'], prefix pair ('ab', 'abab')
D3 by empty: 7 strings, correct True, first ['ab$', 'aabb$', 'abab$'], prefix pair None
D2 by empty stack: []

D1-এর language prefix-free, উপপাদ্য ৭.২ যেমন বলে। D2 final state-এ L2-এর ১৫টি string ঠিকঠাক চেনে (দৈর্ঘ্য ৮ পর্যন্ত: ১ + ২ + ৪ + ৮), কিন্তু ab আর abab দুটিই L2-এ, তাই L2 prefix-free নয়, আর উপপাদ্য অনুযায়ী কোনো DPDA একে empty stack-এ চিনতে পারে না। শুধু D2 নয়, যেকোনো DPDA. D3 endmarker $ দিয়ে সমস্যা মেটায়: ৭টি string (|w| ≤ ৭, তাই w-এর দৈর্ঘ্য ২, ৪ বা ৬), কোনো prefix জোড়া নেই। শেষ লাইন: D2-কে empty stack রীতিতে চালালে কিছুই নয়, কারণ সে Z কখনো তোলে না। drun-এ D["d"].get((q, "", st[0])) আগে দেখা হয়, কারণ DPDA-তে ε-move থাকলে input-পড়া move থাকে না।

মডেল বদলালে উপপাদ্য বদলায়: এই কোর্সের Sipser-রীতির মডেলে x = ε এমন move খালি stack-এও চলে। সেখানে এক state-এর একটি DPDA, যার একটিই transition “a, ε → ε”, empty stack-এ (⊢+ দিয়ে) a+ = {a, aa, aaa, …} চেনে, যা prefix-free নয়। তাই “empty-stack DPDA মানে prefix-free” বলার আগে মডেলটি বলুন: প্রতিটি move top তোলে, আর খালি stack-এ যন্ত্র থামে। পরীক্ষায় এই শর্ত না লিখলে উত্তর অসম্পূর্ণ।

আরও গভীরে: PDA-র ধারণা ১৯৬০-এর দশকের শুরুতে Oettinger (১৯৬১, “pushdown store”), Chomsky (১৯৬২) আর Schützenberger (১৯৬৩)-এর কাজে আসে বলে পরিচিত, আর CFG-এর সঙ্গে সমতা প্রায় একই সময়ে কয়েকজন আলাদাভাবে দেখান। Ginsburg আর Greibach ১৯৬৬ সালে DCFL নিয়ে মৌলিক প্রবন্ধে দেখান যে DCFL complement-এ বন্ধ; প্রমাণের একটি বড় অংশ ঠিক “DPDA কখন গ্রহণ করে” প্রশ্নটি সামলানো, কারণ input শেষে ε-move-এর শিকলে accept আর non-accept state দুটিই আসতে পারে। দুটি DPDA একই language চেনে কি না, এই প্রশ্নটি decidable, যা Sénizergues ১৯৯০-এর দশকের শেষে প্রমাণ করেন (২০০২ সালের Gödel Prize); nondeterministic PDA-র জন্য একই প্রশ্ন undecidable (পর্ব ৩৭)।

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

  • L(P) আর N(P)-এর সংজ্ঞা দিন। L(P): পুরো input পড়ে কোনো accept state-এ, stack যা-ই হোক। N(P): পুরো input পড়ে stack খালি, state যা-ই হোক।
  • Final state থেকে empty stack-এ রূপান্তর করুন। নতুন bottom marker #, প্রতিটি accept state থেকে ঝাড়ার state qe-তে ε-move, qe-তে সব চিহ্ন তোলা।
  • Empty stack থেকে final state-এ রূপান্তর করুন। নতুন #, প্রতিটি state থেকে “ε, # → ε” দিয়ে নতুন accept state.
  • নতুন bottom marker কেন? প্রথম দিকে মূল PDA-র আকস্মিক খালি stack ঠেকাতে, দ্বিতীয় দিকে খালি stack চিনতে।
  • DPDA-তে দুই রীতি কি সমান? না। প্রতিটি move top তোলে এমন মডেলে empty stack-এ শুধু prefix-free DCFL; a∗-ও চেনা যায় না।

৮ · AI-এর যুগে PDA-র গ্রহণ

AI assistant-কে “এই PDA-কে empty stack থেকে final state-এ রূপান্তর করো” বললে সাধারণত পরিপাটি একটি উত্তর আসে। ভুলগুলো প্রায়ই অংশ ৪ আর ৫-এর ফাঁদের মতো: দেখতে ঠিক, কিন্তু কয়েকটি string-এ ভুল। আর দুই বইয়ের রীতি মিশিয়ে ফেলা খুব সাধারণ ভুল।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
নতুন bottom marker ছাড়াই রূপান্তর, “P তো নিজেই $ রাখে” বলেযে PDA মাঝপথে নিজের $ তোলে (যেমন anbnc), তাতে brute force চালান
শুরুর মুহূর্তের ফাঁদ: ε ভুল করে গৃহীত বা বাদε আলাদা করে পরীক্ষা করুন; কোন মডেল (Z0 আছে কি না) তা জিজ্ঞেস করুন
Sipser-এর মডেলে HMU-র গঠন (বা উল্টো) বসানোstack শুরুতে খালি না Z0, move-এ এক চিহ্ন রাখা না string, মিলিয়ে নিন
“DPDA-তেও দুই রীতি সমান” বা “empty stack DPDA সব DCFL চেনে”a∗ বা {a, aa}-এর মতো non-prefix-free language-এ যুক্তি চান; উপপাদ্য ৭.২ মনে রাখুন
Stack খালি হলেই গ্রহণ, input বাকি থাকলেওসংজ্ঞায় শেষ configuration (q, ε, ε), বাকি input ε কি না দেখুন
বানানো উপপাদ্য-নম্বর বা রেফারেন্সSipser বা Hopcroft–Motwani–Ullman-এ নিজে খুঁজে নিশ্চিত হোন

AI-কে ভালোভাবে কাজে লাগানোর উপায়: মডেল আগে ঠিক করে দেওয়া, পূর্ণ transition-তালিকা চাওয়া, আর একটি যাচাইয়ের কোড চাওয়া, যা আপনি নিজে চালাবেন।

আমি গণনার তত্ত্ব শিখছি। মডেল: Sipser-এর PDA, stack শুরুতে খালি, প্রতিটি transition "a, x → y" (a, x, y প্রত্যেকে একটি চিহ্ন বা ε)। Empty stack-এ গ্রহণ মানে অন্তত একটি move-এর পর পুরো input পড়ে stack খালি। PDA P (empty stack): একটি state q; transition: "(, ε → X" আর "), X → ε"। ১. P-কে final state-এ গ্রহণ করে এমন P″-এ রূপান্তর করো, যাতে L(P″) = N(P). পূর্ণ transition-তালিকা দাও। ২. প্রতিটি নতুন state আর চিহ্ন কেন লাগে, এক লাইনে বলো। ε ∈ N(P) কি না আলাদা করে যাচাই করো। ৩. শুধু standard library দিয়ে একটি ছোট Python কোড দাও, যা দৈর্ঘ্য 8 পর্যন্ত সব string-এ N(P) আর L(P″) মেলায়। ৪. কোনো দাবি নিয়ে নিশ্চিত না হলে স্পষ্ট করে বলো; বানানো রেফারেন্স দিও না।

উত্তর পেলে এই পর্বের to_final আর lang দিয়ে নিজেও মেলান। সবচেয়ে সম্ভাব্য ভুল এখানে ε: AI-এর P″ যদি শুরুতেই # দেখে accept state-এ যেতে পারে, তবে সে ε নেবে, অথচ N(P)-তে ε নেই।

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

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

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

প্র ০১গ্রহণের দুই রীতি এল কোথা থেকে, আর পাঠ্যবইগুলো কেন আলাদা রীতি বেছে নেয়?

Pushdown store-এর ধারণা ১৯৫০-এর দশকের শেষ আর ১৯৬০-এর দশকের শুরুতে যন্ত্রানুবাদ আর compiler-এর কাজ থেকে আসে বলে পরিচিত। Anthony Oettinger ১৯৬১ সালে স্বয়ংক্রিয় বাক্য-বিশ্লেষণে “pushdown store” ব্যবহার করেন, আর Chomsky (১৯৬২) ও Schützenberger (১৯৬৩)-এর কাজে PDA আর context-free grammar-এর সম্পর্ক গাণিতিকভাবে দাঁড়ায়। প্রথম দিকের অনেক লেখায় যন্ত্রটি stack খালি হলে কাজ শেষ বলে ধরা হতো, কারণ parsing-এর দৃষ্টিতে সেটিই স্বাভাবিক: stack-এ থাকে “এখনো যা মেলানো বাকি”, আর কিছু বাকি না থাকলে বাক্যটি সম্পূর্ণ।

পরে automata theory-র একটি একীভূত রূপ গড়ে ওঠে, যেখানে DFA, NFA, PDA আর Turing machine সবাই accept state দিয়ে গ্রহণ করে। Sipser-এর বই এই একরূপতা বেছে নেয়: final state একমাত্র রীতি, আর stack খালি কি না চেনার জন্য PDA নিজে $ রাখে। Hopcroft–Motwani–Ullman দুটি রীতিই সংজ্ঞায়িত করে, আর CFG → PDA গঠনে empty stack ব্যবহার করে, কারণ সেখানে একটি state-ই যথেষ্ট আর প্রমাণ ছোট হয়।

কোনটি “সঠিক”? Nondeterministic PDA-র জন্য প্রশ্নটি রুচির, কারণ অংশ ৪ আর ৫-এর গঠন একটিকে অন্যটিতে আনে, আর খরচ মাত্র কয়েকটি state আর transition. তাই প্রতিটি বই এমন রীতি বেছে নেয় যা তার প্রমাণগুলো সহজ করে। DPDA-তে কিন্তু প্রশ্নটি রুচির নয়, শক্তির, যা অংশ ৭ দেখিয়েছে। তাই যে বই empty stack দিয়ে শুরু করে, সেও DPDA-র সংজ্ঞায় final state-এ ফিরে আসে।

মূল উপলব্ধি: দুই রীতি দুই উৎস থেকে এসেছে: parsing-এর অভিজ্ঞতা থেকে empty stack, automata-র একরূপতা থেকে final state. Nondeterminism থাকলে পার্থক্যটি শুধু সুবিধার, না থাকলে শক্তির।

প্র ০২বাস্তবের parser কেন input-এর শেষে একটি “end of file” চিহ্ন যোগ করে, আর এর সঙ্গে prefix-free উপপাদ্যের সম্পর্ক কী?

মডিউল ৭-এর LL আর LR parser প্রায় সবসময় input-এর শেষে একটি বিশেষ token ধরে নেয়, বইয়ে প্রায়ই $ বা EOF লেখা হয়। LR parser-এর “accept” কাজটি ঘটে শুধু তখন, যখন stack-এ start symbol আর পরের token $। কারণটি ঠিক উপপাদ্য ৭.২-এর মতো। Deterministic যন্ত্র একবারে একটি পথেই চলে; কোনো জায়গায় “এখানে থামলে বাক্যটি বৈধ” হলেও সে জানে না পরে আরও input আসবে কি না। বাজারঘর-এর order query-তে FIND order নিজেই বৈধ হতে পারে, আবার FIND order WHERE amount >= 1000-ও বৈধ। Parser যদি প্রথম বৈধ জায়গায় stack ঝেড়ে থেমে যায়, তবে লম্বা query-টি আর পড়তেই পারবে না।

Endmarker এই দ্বিধা মুছে দেয়। L যা-ই হোক, L$ prefix-free, তাই deterministic যন্ত্রটি $ দেখার পরেই সিদ্ধান্ত নেয় আর stack খালি করে। তত্ত্বের ভাষায়: প্রতিটি DCFL L-এর জন্য L$ একটি empty-stack DPDA-র language. ব্যবহারিক ভাষায়: parser জানে কখন বাক্য শেষ, আর শেষে বাড়তি কিছু থাকলে (যেমন JSON-এর পরে অপ্রত্যাশিত লেখা) পরিষ্কার একটি error দিতে পারে।

Streaming-এর ক্ষেত্রে সমস্যাটি আরও স্পষ্ট। নেটওয়ার্কে আসা একটি বার্তা পড়ার সময় parser অনেক সময় দৈর্ঘ্য-ক্ষেত্র বা একটি সমাপ্তি-চিহ্নের ওপর নির্ভর করে, কারণ prefix-free নয় এমন ভাষায় “এখানে শেষ” বলা যায় না। Protocol নকশায় তাই বার্তাগুলো প্রায়ই prefix-free রাখা হয়, যেমন দৈর্ঘ্য আগে লিখে দেওয়া। এটি prefix code-এর ধারণার কাছাকাছি, যা Huffman coding-এও দেখা যায়।

মূল উপলব্ধি: Endmarker কোনো বাড়তি সৌজন্য নয়; deterministic যন্ত্রকে “কোথায় থামবে” জানানোর একমাত্র নির্ভরযোগ্য উপায়। উপপাদ্য ৭.২ তার গাণিতিক কারণ।

প্র ০৩“গ্রহণের সংজ্ঞা” বদলালে কোন যন্ত্রের শক্তি বদলায় আর কোনটির বদলায় না? অন্য যন্ত্রের সঙ্গে তুলনা করুন।

সসীম automaton-এ প্রশ্নটি ছোট: DFA-তে state ছাড়া আর কোনো স্মৃতি নেই, তাই গ্রহণের নিয়ম মানেই accept state-এর set. NFA-তে “অন্তত একটি পথ গ্রহণ করে” নিয়মটি শক্তি বাড়ায় না, কারণ subset construction (পর্ব ১০) একটি DFA দেয়। কিন্তু NFA-তে নিয়ম যদি হতো “সব পথ গ্রহণ করে”, তাও একই শ্রেণি দিত; পার্থক্য শুধু আকারে।

PDA-তে, এই পর্বে দেখলেন, nondeterministic যন্ত্রের জন্য তিন রীতি (final state, empty stack, দুটিই) সমান। DPDA-তে empty stack দুর্বল। Turing machine-এ (পর্ব ৪৩) গ্রহণ মানে accept state-এ পৌঁছে থামা; সেখানে “থামা” নিজেই এমন একটি ঘটনা, যা সবসময় ঘটে না, আর এখান থেকেই recognizable আর decidable language-এর পার্থক্য আসে (পর্ব ৫০)।

সবচেয়ে চমকপ্রদ উদাহরণ অসীম string-এর automaton, যা model checking-এ ব্যবহার হয়। সেখানে input কখনো শেষ হয় না, তাই “শেষে কোন state” প্রশ্নটিই অর্থহীন; বদলে প্রশ্ন হয় “কোন state অসীমবার আসে”। Büchi-র নিয়মে (কোনো accept state অসীমবার) nondeterministic যন্ত্র সব ω-regular language চেনে, কিন্তু deterministic Büchi যন্ত্র চেনে না; যেমন “শেষ পর্যন্ত শুধু a” language-টি। Muller-এর মতো শক্তিশালী নিয়মে deterministic যন্ত্রও যথেষ্ট, যা McNaughton-এর ১৯৬৬ সালের উপপাদ্য বলে পরিচিত। প্যাটার্নটি PDA-র মতোই: nondeterminism থাকলে গ্রহণের নিয়ম নিয়ে স্বাধীনতা বেশি, deterministic যন্ত্রে নিয়মটি শক্তি নির্ধারণ করে।

মূল উপলব্ধি: “গ্রহণ” সংজ্ঞার অংশ, স্বাভাবিক সত্য নয়। নতুন কোনো যন্ত্র-মডেল দেখলে জিজ্ঞেস করুন: গ্রহণের নিয়ম বদলালে শ্রেণি বদলায় কি না, আর deterministic রূপে বদলায় কি না।

প্র ০৪একটি রূপান্তর “দেখতে ঠিক” কিন্তু আসলে ভুল, এমন ভুল কেন এত সহজে ঘটে, আর brute force দিয়ে যাচাই কতটা নির্ভরযোগ্য?

অংশ ৫-এর দুটি ভুল রূপান্তরই এই ধরনের। # ছাড়া রূপান্তর P≥-এ পুরোপুরি ঠিক চলে, কারণ P≥ নিজে কখনো stack খালি করে না; ভুলটি দেখা দেয় শুধু এমন যন্ত্রে, যা মাঝপথে নিজের $ তোলে। s0 ছাড়া রূপান্তর একটিমাত্র string-এ ভুল করে, ε, আর সেটিও শুধু যখন ε ∉ N(P). কেউ দুই-তিনটি “সাধারণ” string হাতে চালালে দুটি ভুলই পার পেয়ে যায়। নির্মাণ-প্রমাণের ভুল প্রায়ই এমন সীমান্তে লুকিয়ে থাকে: শুরুর মুহূর্ত, ফাঁকা string, বা এমন আচরণ যা উদাহরণের যন্ত্রে ঘটে না।

Brute force দুটি দিকে সাহায্য করে। প্রথমত, এটি ছোট সব string পরীক্ষা করে, তাই ε আর ছোট সীমান্ত-ক্ষেত্র কখনো বাদ যায় না। দ্বিতীয়ত, এটি আপনাকে বাধ্য করে একটি স্বাধীন সংজ্ঞা (এই পর্বের ref) লিখতে, আর সেই সংজ্ঞা লিখতে গিয়েই অনেক সময় ভুল ধরা পড়ে। তবে এর সীমা স্পষ্ট: দৈর্ঘ্য ৭ পর্যন্ত মিল মানে সব দৈর্ঘ্যে মিল নয়, আর পরীক্ষাটি শুধু যে যন্ত্রগুলো দেওয়া হয়েছে তাদের ওপর। P≥-এর মতো একটি “সহজ” যন্ত্রে পরীক্ষা করলে # ছাড়া রূপান্তরও পাস করত।

তাই পূর্ণ আস্থার পথ দুটি একসঙ্গে: একটি প্রমাণ, যা সব PDA আর সব দৈর্ঘ্যের জন্য খাটে, আর একটি পরীক্ষা-সংগ্রহ, যা ইচ্ছাকৃতভাবে কঠিন যন্ত্র রাখে: যে PDA মাঝপথে stack খালি করে, যে PDA ε গ্রহণ করে না, যে PDA-র accept state থেকে আরও move আছে। Software testing-এ একে বলা হয় সীমান্ত-মান আর পাল্টা-উদাহরণ খোঁজা।

মূল উপলব্ধি: Brute force একটি পাল্টা-উদাহরণ খুঁজে পেলে সেটি নিশ্চিত প্রমাণ যে গঠন ভুল; না পেলে সেটি শুধু আস্থা বাড়ায়। প্রমাণ সাধারণ সত্য দেয়, পরীক্ষা প্রমাণের ভুল ধরে।

প্র ০৫বাজারঘর-এর order-query validator-এ দুই রীতির কোনটি কাজে লাগে, আর stream থেকে পড়ার সময় কী সমস্যা হয়?

ধরুন বাজারঘর-এর order query-তে বন্ধনী আর AND/OR থাকে, যেমন (district = "Dhaka" AND (amount >= 1000 OR paid = 1)). বন্ধনী মেলানোর অংশটি empty stack রীতিতে খুব স্বাভাবিক: প্রতিটি খোলা বন্ধনী stack-এ একটি চিহ্ন রাখে, প্রতিটি বন্ধ বন্ধনী একটি তোলে, আর শেষে stack খালি মানে সব বন্ধনী মিলেছে। কিন্তু validator শুধু বন্ধনী গোনে না; শেষে query-টি ব্যাকরণগতভাবে সম্পূর্ণ কি না দেখতে হয়, যেমন শেষ চিহ্নটি AND হলে query অসম্পূর্ণ। এই “সম্পূর্ণ” অবস্থাটি একটি state-এর ধর্ম, তাই final state রীতি এখানে স্বাভাবিক। বাস্তবের যন্ত্র প্রায়ই দুটিই দেখে: stack খালি এবং সম্পূর্ণ state, অর্থাৎ অংশ ৫-এর শেষে বলা তৃতীয় রীতি।

Stream-এ সমস্যা অংশ ৭-এর মতো। Validator যদি একটি চিহ্ন করে পড়ে আর প্রথম বৈধ মুহূর্তেই “ঠিক আছে” বলে দেয়, তবে FIND order পড়েই সে থামবে, যদিও পরে WHERE ... আসছিল। Query যদি একটি HTTP অনুরোধের body হয়, তবে body-র শেষটিই endmarker; সেখানে পৌঁছালেই সিদ্ধান্ত। আবার কেউ যদি টাইপ করার সঙ্গে সঙ্গে সবুজ বা লাল চিহ্ন দেখাতে চায়, তবে প্রশ্নটি অন্য: “এখন পর্যন্ত লেখাটি কোনো বৈধ query-র prefix কি না”, যা আরেকটি language (L-এর prefix-বন্ধ রূপ)।

নকশার এই তিন প্রশ্ন (কখন বাক্য শেষ, শেষে কোন শর্ত দেখা হবে, মাঝপথে কী দেখানো হবে) আলাদা রাখলে validator-এর ভুল অনেক কমে। ঠিক যেমন এই পর্বে L(P), N(P) আর DPDA-র সীমা আলাদা করে ভাবা হয়েছে।

মূল উপলব্ধি: বাস্তবের যন্ত্রে গ্রহণের নিয়ম একটি নকশার সিদ্ধান্ত। Empty stack নেস্টিং মেলায়, final state বাক্যের সম্পূর্ণতা দেখে, আর endmarker বলে কখন বিচার করতে হবে।

অনুশীলন

প্রতিটি নিজে করে তারপর উত্তর মেলান।

  1. নকশা ও রূপান্তর: {wwR : w ∈ {a, b}∗} (জোড় দৈর্ঘ্যের palindrome, ε-সহ)-এর জন্য empty stack রীতিতে একটি PDA নকশা করুন। তারপর অংশ ৫-এর গঠনে final state-এর P″ বানিয়ে state আর transition গুনুন।

    নকশা (অনুমান আর যাচাই): q0-এ a, ε → A আর b, ε → B (প্রথম অর্ধেক stack-এ); q0 থেকে ε, ε → ε দিয়ে q1 (মাঝখান অনুমান); q1-এ a, A → ε আর b, B → ε (দ্বিতীয় অর্ধেক মিলিয়ে তোলা)। পাঁচটি transition, দুটি state, $ লাগে না। ε-ও আসে: (q0, ε, ε) ⊢ (q1, ε, ε), একটি move. abba: (q0, abba, ε) ⊢ (q0, bba, A) ⊢ (q0, ba, BA) ⊢ (q1, ba, BA) ⊢ (q1, a, A) ⊢ (q1, ε, ε)।

    রূপান্তর: qs, s0, q0, q1, qf: ৫টি state. Transition: # রাখা ১টি, মূল ৫টি, s0-এ q0-এর তিনটির কপি, আর q0, q1 থেকে প্রস্থান ২টি, মোট ১১টি। Scratch-এ দৈর্ঘ্য ৮ পর্যন্ত N(P) ঠিক ৩১টি জোড় palindrome (ε-সহ) দিয়েছে, আর L(P″) হুবহু একই। এখানে s0 বাদ দিলেও ফল একই হতো, কারণ ε ∈ N(P); কিন্তু সাধারণ গঠনে s0 রাখাই নিরাপদ।

  2. ভুল খুঁজুন: একজন লিখলেন: “Final state থেকে empty stack: প্রতিটি f ∈ F থেকে qe-তে ε-move, আর qe-তে Γ-এর সব চিহ্ন তোলা। নতুন নিচের চিহ্নের দরকার নেই, কারণ P নিজেই শুরুতে $ রাখে, তাই stack কখনো আগেভাগে খালি হবে না। অতএব N(P′) = L(P).” প্রমাণের কোন ধাপটি ভুল? একটি পাল্টা-উদাহরণ দিন।

    ভুল ধাপ: “P নিজেই $ রাখে, তাই stack আগেভাগে খালি হবে না।” P নিজের $ তুলতেও পারে, আর তুলে কোনো non-accept state-এ পুরো input শেষ করতে পারে। তখন P′-এর stack খালি, input শেষ, তাই P′ গ্রহণ করে, অথচ P করে না। প্রমাণের “N(P′) ⊆ L(P)” দিকটি এখানে ভাঙে: “stack খালি ⇒ qe-তে পৌঁছেছে” দাবিটির জন্যই # দরকার।

    পাল্টা-উদাহরণ: Pc (L = {anbnc : n ≥ 0}, F = {q4})। ab পড়ে Pc পৌঁছায় (q3, ε, ε), q3 ∉ F. ভুল P′ ab গ্রহণ করে। অংশ ৫-এর Python ব্লক দেখিয়েছে, দৈর্ঘ্য ৭ পর্যন্ত ভুল P′ ৪টি বাড়তি string নেয়: ε, ab, aabb, aaabbb.

  3. Trace আর অনুমান: অংশ ৫-এর সঠিক P″ (Pbal থেকে বানানো: qs → s0 “ε, ε → #”; s0 আর q-তে “(, ε → X” আর “), X → ε”, যার গন্তব্য q; q থেকে “ε, # → ε” দিয়ে qf) (()) আর ()) পড়লে কী হয়? চালানোর আগে অনুমান করুন: কোনটি গৃহীত, আর গৃহীত হলে কয়টি move?

    (()): (qs, (()), ε) ⊢ (s0, (()), #) ⊢ (q, ()), X#) ⊢ (q, )), XX#) ⊢ (q, ), X#) ⊢ (q, ε, #) ⊢ (qf, ε, ε)। ৬টি move, গৃহীত: দৈর্ঘ্য ৪-এর string-এ চারটি পড়ার move, আর শুরুর # ও শেষের প্রস্থান।

    ()): (qs, ()), ε) ⊢ (s0, ()), #) ⊢ (q, )), X#) ⊢ (q, ), #). এখন ) পড়তে top-এ X লাগে, কিন্তু top-এ #. একমাত্র বাকি move qf-এ প্রস্থান, কিন্তু তখন ) পড়া বাকি আর qf-এর কোনো move নেই। প্রত্যাখ্যাত। Scratch-এর simulator-ও এই দুই ফল দিয়েছে।

  4. প্রমাণ: প্রমাণ করুন, প্রতিটি move top তোলে এমন মডেলে কোনো DPDA empty stack-এ L = {a, aa} চেনে না, যদিও একটি DPDA final state-এ L চেনে। তারপর L$ = {a$, aa$}-এর জন্য empty stack-এর একটি DPDA দিন।
    1. a আর aa দুটিই L-এ, আর a হলো aa-র proper prefix; তাই L prefix-free নয়। — সংজ্ঞা ৭.১
    2. উপপাদ্য ৭.২ বলে, প্রতিটি DPDA D-এর N(D) prefix-free. তাই N(D) = L অসম্ভব। ∎ — উপপাদ্য ৭.২
    3. Final state-এ: δ(p, a, Z) = (q, Z), δ(q, a, Z) = (r, Z), F = {q, r}। এটি deterministic, আর ঠিক a ও aa গ্রহণ করে। — DFA-কে DPDA হিসেবে চালানো

    L$-এর জন্য: δ(p, a, Z) = (q, Z), δ(q, $, Z) = (f, ε), δ(q, a, Z) = (r, Z), δ(r, $, Z) = (f, ε)। $ পড়ার সময়ই Z ওঠে, আর তার পরে কোনো move নেই। Scratch-এ {a, $}-এর ওপর দৈর্ঘ্য ৫ পর্যন্ত সব string চালিয়ে ঠিক a$ আর aa$ গৃহীত পাওয়া গেছে।

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

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

ক্রমএকটি final-state PDA P থেকে empty-stack PDA P′ বানানোর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. নতুন শুরুর state qs থেকে “ε, ε → #” দিয়ে P-এর q0-এ যাওয়া
  2. P-এর সব transition অপরিবর্তিত রাখা
  3. প্রতিটি accept state থেকে “ε, ε → ε” দিয়ে ঝাড়ার state qe-এ যাওয়া
  4. qe-তে Γ ∪ {#}-এর প্রতিটি চিহ্নের জন্য “ε, x → ε” loop
  5. ছোট দৈর্ঘ্যে L(P) আর N(P′) brute force-এ মেলানো

PDA P-এর transition: q0 থেকে “ε, ε → $” দিয়ে q1; q1-এ “a, ε → A”; q1 থেকে “ε, ε → ε” দিয়ে q2; q2-এ “b, A → ε”; F = {q1, q2}, stack শুরুতে খালি। Empty stack-এ গৃহীত language N(P) কী?

  • {aibj : i ≥ j}
  • {anbn : n ≥ 0}
  • ∅
  • {ε}

Final-state PDA P থেকে empty-stack PDA P′ বানানোর সময় P′ শুরুতেই stack-এর নিচে একটি নতুন চিহ্ন # রাখে কেন?

  • যাতে P-কে আর নিজের $ রাখতে না হয়
  • যাতে P নিজে non-accept state-এ stack খালি করলে P′ ভুল করে গ্রহণ না করে
  • যাতে P′ deterministic হয়
  • যাতে ε সবসময় গৃহীত হয়

Stack শুরুতে খালি এমন মডেলে empty-stack PDA P থেকে final-state P″ বানানো হলো এভাবে: নতুন qs থেকে “ε, ε → #” দিয়ে সরাসরি P-এর q0, আর P-এর প্রতিটি state থেকে “ε, # → ε” দিয়ে নতুন accept state qf. N(P)-তে অন্তত একটি move লাগে। কোন string P″ ভুল করে গ্রহণ করতে পারে?

  • ε
  • N(P)-এর দীর্ঘতম string
  • যেসব string-এ P মাঝপথে stack খালি করে
  • সব string

প্রতিটি move stack-এর top থেকে একটি চিহ্ন তোলে আর stack খালি হলে যন্ত্র থামে, এমন মডেলে নিচের কোন language কোনো DPDA empty stack-এ চিনতে পারে না?

  • {anbn : n ≥ 1}
  • {wcwR : w ∈ {a, b}∗}
  • a∗
  • {anbn$ : n ≥ 0}

Nondeterministic PDA-র জন্য দুটি শ্রেণি তুলনা করুন: 𝓛F = {L(P) : P একটি PDA} আর 𝓛N = {N(P) : P একটি PDA}। কোনটি সত্য?

  • 𝓛N ⊊ 𝓛F
  • 𝓛F = 𝓛N
  • 𝓛F ⊊ 𝓛N
  • কোনোটি অন্যটির অংশ নয়

PDA P-এর একটিমাত্র state q, stack শুরুতে খালি, transition “(, ε → X” আর “), X → ε”। এই মডেলে ε-push move খালি stack-এও চলে। নিচের কোন string N(P)-এ আছে?

  • (()
  • ())
  • )(
  • ()()

Empty-stack রীতিতে PDA P-এর গ্রহণের শর্ত নিচের কোনটি? (Configuration (q, w, γ): state, বাকি input, stack; stack শুরুতে খালি।)

  • (q0, w, ε) ⊢+ (q, ε, ε), কোনো q ∈ Q-এর জন্য
  • (q0, w, ε) ⊢∗ (q, ε, γ), কোনো q ∈ F-এর জন্য
  • (q0, w, ε) ⊢∗ (q, v, ε), কোনো v-এর জন্য
  • (q0, w, ε) ⊢∗ (q, ε, ε), শূন্য move-সহ

শব্দকোষ

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

মনে রাখুন

  1. L(P): পুরো input পড়ে কোনো accept state, stack যা-ই হোক। N(P): পুরো input পড়ে stack খালি, state যা-ই হোক; stack খালি দিয়ে শুরু হলে অন্তত একটি move.
  2. Final state → empty stack: নতুন #, প্রতিটি accept state থেকে ঝাড়ার state, সেখানে সব চিহ্ন তোলা।
  3. Empty stack → final state: নতুন #, প্রতিটি state থেকে “ε, # → ε” দিয়ে নতুন accept state; শুরুর state-এর কপি s0 ε-র ফাঁদ ঠেকায়।
  4. Nondeterministic PDA-তে দুই রীতি সমান শক্তির; নকশা যেটিতে সহজ সেটিতে করুন, আর রূপান্তরের পর brute force-এ মেলান।
  5. DPDA-তে final state-ই সঠিক: প্রতিটি move top তোলে এমন মডেলে empty stack শুধু prefix-free DCFL দেয়; endmarker $ সমাধান।

পরের পর্বে: PDA আর CFG-এর সমতা: grammar থেকে PDA (stack-এ leftmost derivation চালানো, empty stack-এ স্বাভাবিক) আর PDA থেকে grammar (Apq variable দিয়ে)।

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

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