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

PDA আর CFG-এর সমতা — দুই দিকের রূপান্তর

Equivalence of Pushdown Automata and Context-Free Grammars — CFG to PDA, Normalising a PDA, the Apq Construction and Proofs

Taught in Bangla, this lesson proves that a language is context-free exactly when some pushdown automaton recognises it. It builds a three-state PDA from any CFG that simulates leftmost derivations on its stack, then normalises a PDA and constructs the A_pq grammar with its three rule types, proving each direction by induction. In-page Python (Pyodide) converts a balanced-bracket grammar to a PDA and back and checks every string up to length 10, and a real run compares a lark parser with an automata-lib PDA.

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

  • যেকোনো CFG থেকে PDA বানানো, transition-এর পূর্ণ তালিকা লেখা আর একটি input-এ চালিয়ে দেখানো
  • CFG → PDA গঠন কেন সঠিক, derivation আর configuration-এর invariant দিয়ে প্রমাণ
  • একটি PDA-কে তিন শর্তে normalise করা, আর প্রতিটি শর্ত কেন দরকার
  • Apq গঠনে PDA থেকে grammar বানানো, তিন ধরনের নিয়ম আর দুই দিকের induction-প্রমাণ
  • ফলাফল (CFL = PDA-র language, regular ⊂ CFL), রূপান্তরের আকার, আর brute force দিয়ে রূপান্তর যাচাই

১ · কেন সমতা — grammar লেখে, PDA পড়ে

এই মডিউলে আপনি এখন পর্যন্ত দুটি আলাদা জিনিস দেখেছেন। মডিউল ৫-এ context-free grammar (CFG): G = (V, Σ, R, S), যার নিয়ম থেকে string তৈরি হয় (পর্ব ২৫)। পর্ব ৩২-এ PDA: P = (Q, Σ, Γ, δ, q0, F), একটি finite automaton যার সঙ্গে একটি সীমাহীন stack, যা একটি string পড়ে গ্রহণ বা বর্জন করে। একটি লেখার যন্ত্র, অন্যটি পড়ার যন্ত্র। এই পর্বের প্রশ্ন: দুটি কি একই শ্রেণির language বর্ণনা করে?

উত্তর হ্যাঁ, আর এটি এই মডিউলের কেন্দ্রীয় উপপাদ্য। Regular language-এর জন্য একই ধরনের ফল আপনি দেখেছেন: Kleene-এর উপপাদ্য বলে regex আর finite automaton সমান শক্তিশালী (পর্ব ১৪ আর পর্ব ১৫)। এখানে এক ধাপ ওপরে, Chomsky hierarchy-র Type 2 স্তরে (পর্ব ০৬), একই কাজ।

উপপাদ্য ১.১ (PDA আর CFG-এর সমতা)

একটি language L context-free, অর্থাৎ কোনো CFG G-এর জন্য L = L(G), যদি এবং কেবল যদি কোনো PDA P-এর জন্য L = L(P) (final state দিয়ে গ্রহণ)। দুই দিকের রূপান্তরই algorithm দিয়ে করা যায়।

প্রমাণ দুই ভাগে: লেমা ২.১ (CFG থেকে PDA, অংশ ২–৩) আর লেমা ৫.১ (PDA থেকে CFG, অংশ ৪–৬)। প্রথম দিকটি সহজ আর সুন্দর; দ্বিতীয়টি কঠিন, কিন্তু তার মূল ধারণা একটি ছবিতে ধরা যায়।

বাজারের ফর্দের কথা ভাবুন। মা লিখে দিলেন: “সবজি, মাছ”। দোকানে গিয়ে আপনি ফর্দের ওপরের জিনিসটি দেখেন। “সবজি” একটি সাধারণ নাম, তাই আপনি সেটি কেটে তার জায়গায় লেখেন “আলু, পটল” (variable-কে একটি নিয়ম দিয়ে বদলানো)। এখন ওপরে “আলু”, একটি আসল জিনিস; দোকানে আলু পেলে কিনে টিক দেন আর ফর্দ থেকে মুছে ফেলেন (terminal মিলিয়ে pop). ফর্দ ফাঁকা হলে আর বাজারের ব্যাগ ঠিকঠাক ভরলে কাজ শেষ। CFG থেকে বানানো PDA ঠিক এভাবে কাজ করে: stack হলো ফর্দ, input হলো যা আসলে কেনা হলো।

এই সমতা কেন গুরুত্বপূর্ণ? প্রথমত, এটি দুই দিকের প্রমাণের হাতিয়ার দেয়। কোনো language-কে CFL দেখাতে কখনো grammar লেখা সহজ (palindrome), কখনো PDA (একটি regular language-এর সঙ্গে intersection, পর্ব ৩৭)। দ্বিতীয়ত, এটি parser-এর তাত্ত্বিক ভিত্তি: প্রতিটি parser আসলে একটি stack-ভিত্তিক যন্ত্র যা একটি grammar থেকে বানানো। মডিউল ৭-এর LL আর LR parser এই পর্বের CFG → PDA গঠনের deterministic রূপ।

ইতিহাস: “Pushdown store” বা stack-কে grammar-এর সঙ্গে যুক্ত করার কাজ সাধারণত Noam Chomsky (১৯৬২), Robert J. Evey (১৯৬৩) আর Marcel-Paul Schützenberger (১৯৬৩)-এর নামে ধরা হয়; তিনজন প্রায় একই সময়ে, আংশিক স্বাধীনভাবে, সমতাটি দেখান বলে পরিচিত। তার আগে Friedrich Bauer আর Klaus Samelson ১৯৫০-এর দশকের শেষে গাণিতিক সূত্র অনুবাদে stack (“Kellerprinzip”) ব্যবহার করেন বলে পরিচিত। এই পর্বে আমরা Sipser-এর বইয়ের রূপ মানছি।

২ · CFG থেকে PDA — stack-এ leftmost derivation

লক্ষ্য: যেকোনো CFG G দেওয়া থাকলে একটি PDA P বানানো (CFG থেকে PDA গঠন), যাতে L(P) = L(G). মূল ধারণা: P input পড়তে পড়তে G-এর একটি leftmost derivation “অনুমান” করে। Leftmost derivation-এর প্রতিটি sentential form দুই ভাগে দেখা যায়: বাঁয়ে terminal-এর একটি টুকরো x (যা ইতিমধ্যে চূড়ান্ত), আর ডানে বাকি অংশ γ, যা শুরু হয় প্রথম variable থেকে। P-র কৌশল: x-কে input থেকে পড়ে ফেলা, আর γ-কে stack-এ রাখা, প্রথম চিহ্ন ওপরে।

লেমা ২.১ (CFG → PDA)

G = (V, Σ, R, S) একটি CFG হলে একটি PDA P আছে যাতে L(P) = L(G). P-র তিনটি মূল state qs (শুরু), ql (loop), qa (accept), stack alphabet Γ = V ∪ Σ ∪ {$}, আর transition (“a, x → y” মানে a পড়া, ওপরের x pop, y push):
১. qs থেকে ql: ε, ε → S$ (প্রথমে bottom marker $, তার ওপরে S)
২. প্রতিটি নিয়ম A → w-এর জন্য ql-এ: ε, A → w (ওপরের A সরিয়ে w বসানো, w-এর প্রথম চিহ্ন ওপরে)
৩. প্রতিটি terminal a ∈ Σ-এর জন্য ql-এ: a, a → ε (input-এর a আর ওপরের a মিলিয়ে pop)
৪. ql থেকে qa: ε, $ → ε (stack-এ শুধু $ বাকি মানে derivation শেষ)। F = {qa}।

একটি খুঁটিনাটি: Sipser-এর সংজ্ঞায় এক চালে একটিমাত্র চিহ্ন push করা যায়, অথচ ১ আর ২ নম্বর চালে পুরো একটি string (S$, বা w) push হচ্ছে। এটি একটি সংক্ষেপ। w = w1w2⋯wk push করতে k − 1টি নতুন মধ্যবর্তী state লাগে: প্রথম চালে A pop করে wk push, তারপর ε-চালে wk−1, …, শেষে w1, যাতে w1 ওপরে থাকে। Language বদলায় না, শুধু state বাড়ে; এই পর্বের Python-কোড পুরো string একবারে push করে।

সুষম বন্ধনীর grammar BAL: S → (S)S ∣ ε-এর জন্য PDA-টি নিচের ছবিতে। এটি nondeterministic: ওপরে S থাকলে দুটি নিয়মের যেকোনোটি খাটানো যায়, আর PDA “ঠিক” পছন্দটি অনুমান করে। ভুল অনুমানের শাখাগুলো কোথাও আটকে যায়, তাতে ক্ষতি নেই; একটি শাখা গ্রহণ করলেই string গৃহীত (পর্ব ০৯-এর NFA-র মতো)।

BAL: S → (S)S ∣ ε থেকে বানানো PDA

তিনটি state; ql-এর loop-এ নিয়মের দুটি আর terminal মেলানোর দুটি চাল। Accept state দুই বৃত্তে।

PDA built from the grammar S → (S)S | ε qsqlqa ε,ε→S$ε,$→ε ε, S → (S)S ε, S → ε (, ( → ε ), ) → ε শুরুগ্রহণ
ছবি ৩৪.১ — ওপরের দুটি loop-চাল grammar-এর দুটি নিয়ম, নিচের দুটি terminal মেলানো। মোট ৬টি চাল: ১ + ২ + ২ + ১।

সাধারণ হিসাব: |R|টি নিয়ম আর |Σ|টি terminal থাকলে চাল 2 + |R| + |Σ|টি (সংক্ষেপ-push খুলে লিখলে মধ্যবর্তী state-সহ, নিয়মগুলোর ডান দিকের মোট দৈর্ঘ্যের সমানুপাতিক)। অর্থাৎ PDA-র আকার grammar-এর আকারের রৈখিক। নিচের stepper ছবির PDA-টিকে “(())”-এ চালায়। configuration (q, বাকি input, stack) লেখা হয়েছে পর্ব ৩২-এর রীতিতে, stack-এর ওপর বাঁয়ে। শেষ সারিটি লক্ষ করুন: পড়া অংশ আর stack ($ বাদে) পাশাপাশি রাখলে সবসময় derivation-এর একটি sentential form.

1qs: ε, ε → S$2ql: ε, S → (S)S3ql: ε, S → ε4ql: (, ( → ε5ql: ), ) → ε6ql → qa: ε, $ → ε
Configuration
state
বাকি input
stack
পড়া + stack
  1. শুরু। State qs, পুরো input বাকি, stack ফাঁকা।
  2. প্রস্তুতি। ε-চালে $ আর তার ওপরে S. Stack-এর ওপরে start symbol মানে derivation-এর প্রথম sentential form S.
  3. Expand. ওপরে S আর পরের input “(”. PDA S → (S)S বেছে নেয়; S → ε নিলে ওপরে ) বা $ আসত, যা “(”-এর সঙ্গে মেলে না, তাই সেই শাখা মরে যেত।
  4. Match. ওপরে terminal “(”, input-এও “(”: পড়া আর pop. পড়া অংশ “(” + stack “S)S” = (S)S, একই sentential form.
  5. Expand. আবার ওপরে S, পরের input “(”: S → (S)S. Sentential form ((S)S)S, ঠিক leftmost derivation-এর দ্বিতীয় ধাপ।
  6. Match. দ্বিতীয় “(” মিলল। বাকি input “))”.
  7. ε-নিয়ম। ওপরে S কিন্তু পরের input “)”. এবার S → ε-ই একমাত্র বাঁচার পথ; S সরে গিয়ে ওপরে “)”.
  8. Match. “)” মিলল। পড়া “(()”, stack “S)S$”; sentential form (()S)S.
  9. ε-নিয়ম। S → ε, ওপরে আবার “)”.
  10. Match. শেষ “)” মিলল, input শেষ। Stack-এ এখনো S$: derivation-এ শেষ S-টি মুছতে হবে।
  11. ε-নিয়ম। S → ε. পড়া অংশ (()), stack শুধু $: derivation শেষ।
  12. গ্রহণ। ε, $ → ε চালে qa. Input শেষ আর accept state: গৃহীত। মোট ১১টি চাল: ১টি প্রস্তুতি, ৫টি expand, ৪টি match, ১টি শেষ।

Expand-গুলো পরপর পড়লে পাওয়া যায় S ⇒ (S)S ⇒ ((S)S)S ⇒ (()S)S ⇒ (())S ⇒ (()), ঠিক “(())”-এর leftmost derivation (পর্ব ২৬)। PDA-র computation আর grammar-এর derivation একই গল্প, শুধু দুই ভাষায় বলা।

দুই বইয়ের দুই রীতি: Hopcroft–Motwani–Ullman-এর বইয়ে একই গঠন একটিমাত্র state-এর PDA দেয়, যা empty stack দিয়ে গ্রহণ করে (start symbol নিজেই শুরুর stack symbol, তাই $ আর qa লাগে না)। Final state আর empty stack-এর মধ্যে রূপান্তর পর্ব ৩৩-এর বিষয়। আর grammar Greibach normal form-এ থাকলে (পর্ব ৩০) expand আর match এক চালে মেশানো যায়: প্রতিটি A → aα-এর জন্য “a, A → α”, ফলে প্রস্তুতি আর শেষের চাল ছাড়া প্রতিটি চাল ঠিক একটি input চিহ্ন পড়ে।

৩ · গঠনটি কেন সঠিক — প্রমাণ আর Python-এ যাচাই

Stepper-এর শেষ সারির পর্যবেক্ষণটিই প্রমাণের মূল: “পড়া অংশ + stack = একটি leftmost sentential form”. এটি একটি simulation argument (পর্ব ০৪)। নিচে x ∈ Σ∗ পড়া অংশ, γ ∈ (V ∪ Σ)∗ stack-এর $-এর ওপরের অংশ।

দাবি ৩.১ (invariant)

(ক) যদি (ql, xy, S$) ⊢∗ (ql, y, γ$), তবে S ⇒∗lm xγ।
(খ) উল্টো দিকে, যদি S ⇒∗lm xAβ (A ∈ V সবচেয়ে বাঁয়ের variable) বা S ⇒∗lm x, তবে যেকোনো y-এর জন্য (ql, xy, S$) ⊢∗ (ql, y, Aβ$) বা (ql, y, $)।

প্রমাণ (ক), চালের সংখ্যার ওপর induction:

  1. ভিত্তি, ০টি চাল: x = ε, γ = S, আর S ⇒∗ S সত্য। — ⇒∗-এর সংজ্ঞায় শূন্য ধাপ চলে
  2. ধরুন k চালের পর (ql, y′, γ′$)-এ পৌঁছে S ⇒∗lm x′γ′ সত্য, যেখানে x′ পড়া অংশ। পরের চাল দুই রকম হতে পারে। — induction hypothesis; ql-এর চাল মাত্র দুই ধরনের
  3. Expand: γ′ = Aβ আর A → w ∈ R. নতুন stack wβ, পড়া অংশ একই x′. x′Aβ ⇒ x′wβ একটি leftmost ধাপ, কারণ x′-এ কোনো variable নেই, তাই A-ই সবচেয়ে বাঁয়ের variable. — leftmost derivation-এর সংজ্ঞা
  4. Match: γ′ = aβ আর input-এর পরের চিহ্ন a. নতুন পড়া অংশ x′a, stack β; x′a·β = x′·aβ, তাই sentential form বদলায়নি, দাবি টিকে থাকে। ∎ — শুধু ভাগের সীমানা সরল

প্রমাণ (খ), derivation-এর ধাপের ওপর induction (রূপরেখা): শূন্য ধাপে xAβ = S, আর শুরুর configuration-ই যথেষ্ট। ধরুন S ⇒∗lm xAβ-এর জন্য PDA (ql, y, Aβ$)-এ পৌঁছায়, আর পরের ধাপ A → w খাটায়। PDA একই নিয়মে expand করে stack wβ পায়। এখন wβ-এর শুরুতে যত terminal আছে (ধরুন z, যাতে wβ = zA′β′ বা wβ = z), সেগুলো input-এর সঙ্গে একে একে match করে; নতুন sentential form xzA′β′, আর PDA ঠিক x z পড়ে A′β′-তে দাঁড়ায়। ∎

লেমা ২.১-এর উপসংহার: w ∈ L(G) ⇔ S ⇒∗lm w (প্রতিটি derivation-এর একটি leftmost রূপ আছে) ⇔ (দাবি ৩.১, x = w, γ = ε) PDA (ql, ε, $)-এ পৌঁছাতে পারে ⇔ শেষ চালে qa, অর্থাৎ w ∈ L(P). (ক) দিক থেকে আসে L(P) ⊆ L(G), (খ) দিক থেকে L(G) ⊆ L(P). একটি সূক্ষ্মতা: qa-তে যাওয়া যায় শুধু $ ওপরে থাকলে, অর্থাৎ γ = ε হলে, তাই input শেষ হওয়ার আগে qa-তে গেলে আর কিছু পড়া যায় না, আর সেই শাখা গ্রহণ করে না।

এবার গঠন আর simulator কোডে। PDA একটি চালের তালিকা: (p, পড়া, pop, q, push). Simulator configuration-এর ওপর BFS চালায়, পর্ব ৩২-এর মতো। একটি সমস্যা: ε-চালে stack অসীম পর্যন্ত বাড়তে পারে, তাই অনুসন্ধানকে সসীম রাখতে stack-এর দৈর্ঘ্যের একটি সীমা cap দেওয়া হয়েছে, বাকি input-এর দৈর্ঘ্য k হলে 2k + 3. BAL-এর জন্য এটি নিরাপদ: সঠিক computation-এ stack-এর প্রতিটি terminal এখনো-না-পড়া একটি input চিহ্নের অপেক্ষায়, আর দুটি S-এর মাঝে অন্তত একটি “)” থাকে। তবু সীমা একটি অনুমান, তাই শেষে brute force-এ সব string মিলিয়ে দেখা হয়েছে। এই পর্বের তিনটি Python ব্লক একই namespace ভাগ করে।

from collections import deque
from itertools import product
def cfg_to_pda(G, S, terms):       # move = (p, read, pop, q, push), top first
    T = [("qs", "", "", "ql", (S, "$"))]
    T += [("ql", "", A, "ql", r) for A, R in G.items() for r in R]
    T += [("ql", t, t, "ql", ()) for t in terms]   # match a terminal
    return T + [("ql", "", "$", "qa", ())]
def run(T, start, acc, w, cap):    # BFS over configurations (q, i, stack)
    first = (start, 0, ()); prev = {first: None}; todo = deque([first])
    while todo:
        c = todo.popleft(); p, i, st = c
        if i == len(w) and p in acc:           # accepting: rebuild the path
            path = []
            while c: path.append(c); c = prev[c]
            return path[::-1]
        for (pp, a, x, q, y) in T:
            if pp != p or (a and w[i:i + 1] != a) or (x and st[:1] != (x,)):
                continue
            ns = y + (st[1:] if x else st)
            if len(ns) <= cap(len(w) - i):     # keep the search finite
                n = (q, i + len(a), ns)
                if n not in prev: prev[n] = c; todo.append(n)
    return None
bal = {"S": [("(", "S", ")", "S"), ()]}
P = cfg_to_pda(bal, "S", "()")
print(len(P), "moves; accepting computation on (()):")
for q, i, st in run(P, "qs", {"qa"}, "(())", lambda k: 2 * k + 3):
    print(f"  ({q}, {'(())'[i:] or 'ε'}, {''.join(st) or 'ε'})")
balanced = lambda w: w.count("(") == w.count(")") and all(
    w[:k].count("(") >= w[:k].count(")") for k in range(len(w)))
ws = ["".join(t) for k in range(11) for t in product("()", repeat=k)]
acc = [w for w in ws if run(P, "qs", {"qa"}, w, lambda k: 2 * k + 3)]
print(len(ws), "strings, accepted", len(acc),
      "| same as balanced:", acc == [w for w in ws if balanced(w)])

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

6 moves; accepting computation on (()):
  (qs, (()), ε)
  (ql, (()), S$)
  (ql, (()), (S)S$)
  (ql, ()), S)S$)
  (ql, ()), (S)S)S$)
  (ql, )), S)S)S$)
  (ql, )), )S)S$)
  (ql, ), S)S$)
  (ql, ), )S$)
  (ql, ε, S$)
  (ql, ε, $)
  (qa, ε, ε)
2047 strings, accepted 65 | same as balanced: True

৬টি চাল, ছবি ৩৪.১-এর মতো। ১২টি configuration হুবহু ওপরের stepper-এর ১২টি ধাপ; BFS সবচেয়ে কম চালের গ্রহণযোগ্য পথ খুঁজে prev ধরে পেছন দিকে পুনর্গঠন করেছে। শেষ লাইন: দৈর্ঘ্য ০ থেকে ১০-এর সব 211 − 1 = 2047টি string-এর মধ্যে PDA ঠিক ৬৫টি গ্রহণ করেছে, আর তালিকাটি সুষম string-এর তালিকার সঙ্গে হুবহু এক (1 + 1 + 2 + 5 + 14 + 42 = 65, Catalan সংখ্যার যোগফল)। এটি প্রমাণ নয়, প্রমাণ ওপরে; কিন্তু গঠন বা কোডে কোনো ভুল থাকলে এখানে ধরা পড়ত।

Left recursion আর simulator: E → E+T-এর মতো left-recursive নিয়মে PDA ওপরের E-কে বারবার E+T দিয়ে বদলাতে পারে, কিছু না পড়েই; stack অসীম বাড়ে। গাণিতিকভাবে এতে সমস্যা নেই, কারণ গ্রহণের জন্য একটি সফল শাখাই যথেষ্ট। কিন্তু depth-first simulator বা naive recursive-descent parser এখানে চিরকাল ঘুরতে পারে (পর্ব ৩০-এর left recursion-এর আলোচনা)। BFS আর একটি সীমা, বা Earley-র মতো algorithm (পর্ব ৪১), এই সমস্যা এড়ায়।

৪ · PDA থেকে CFG-এর প্রস্তুতি — PDA-কে normalise করা

উল্টো দিক কঠিন, কারণ একটি সাধারণ PDA-র state আর stack যা খুশি করতে পারে। Grammar বানানোর আগে PDA-কে একটি বাঁধা রূপে আনা হয়, ঠিক যেমন grammar-কে CNF-এ আনা হয় (পর্ব ২৯)। Normalised PDA-র তিনটি শর্ত:

  1. একটিই accept state qaccept.
  2. গ্রহণের আগে stack ফাঁকা: qaccept-এ পৌঁছানোর মুহূর্তে stack-এ কিছু নেই।
  3. প্রতিটি চাল ঠিক একটি push বা ঠিক একটি pop করে, দুটো একসঙ্গে নয়, কোনোটি-না-করাও নয়।

কেন এই শর্ত? প্রথম দুটি দিয়ে গ্রহণকে একটি পরিষ্কার প্রশ্নে আনা যায়: “ফাঁকা stack নিয়ে q0 থেকে ফাঁকা stack নিয়ে qaccept-এ যাওয়া যায় কি?” তৃতীয়টি দিয়ে stack-এর উচ্চতা প্রতি চালে ঠিক এক বাড়ে বা কমে, তাই উচ্চতার গ্রাফ একটি পাহাড়ের রেখা, যেখানে প্রতিটি “ওঠা”-র একটি নির্দিষ্ট জোড়া “নামা” আছে। অংশ ৫-এর পুরো গঠন এই জোড়ার ওপর দাঁড়িয়ে।

লেমা ৪.১ (normalisation)

প্রতিটি PDA P-এর জন্য একটি normalised PDA P′ আছে যাতে L(P′) = L(P).

গঠন: (ক) P যদি নিজে শুরুতে একটি bottom marker push না করে, একটি নতুন শুরুর state যোগ করুন যা নতুন চিহ্ন $ push করে পুরোনো শুরুতে যায়। (খ) পুরোনো প্রতিটি accept state থেকে ε, ε → ε চালে একটি নতুন “ফাঁকা করার” state qd; qd-এ প্রতিটি x ∈ Γ − {$}-এর জন্য ε, x → ε loop, আর ε, $ → ε চালে নতুন qaccept. পুরোনো accept state-গুলো আর accept নয়। (গ) যে চাল একসঙ্গে pop আর push করে (a, x → y), তাকে দুই চালে ভাঙুন: a, x → ε একটি নতুন state-এ, তারপর ε, ε → y. যে চাল কিছুই করে না (a, ε → ε), তাকে একটি নতুন চিহ্ন X দিয়ে ভাঙুন: a, ε → X নতুন state-এ, তারপর ε, X → ε. প্রতিটি বদল একটি পুরোনো চালকে এক বা দুই চালে অনুকরণ করে, আর নতুন state-গুলো অন্য কোনো পথ খোলে না, তাই language একই থাকে।

উদাহরণ: L = {aibj : i ≥ j ≥ 0}-এর একটি সরল PDA P1: q1 থেকে ε, ε → $ চালে q2; q2-এ a, ε → a (a গোনা); q2 থেকে ε, ε → ε চালে q3 (মাঝখান অনুমান); q3-এ b, a → ε; accept state q3. এটি ঠিক কাজ করে, কিন্তু তিনটি শর্তের দুটি ভাঙে: aab পড়ে গ্রহণের সময় stack-এ এখনো “a$” থাকে, আর q2 → q3 চাল কিছুই push বা pop করে না।

1মূল PDA P12শর্ত ১: নতুন q_d আর q_f3শর্ত ২: q_d-তে stack খালি4শর্ত ৩: কোন চাল ভাঙে?5শর্ত ৩: X দিয়ে ভাঙা6ফল P2 আর যাচাই
এই ধাপের PDA
বদল
state
চাল
  1. শুরু। P1-এর ৪টি চাল। শুরুতেই $ push হয়, তাই শর্তের কাজে নতুন bottom marker লাগবে না। সমস্যা: গ্রহণের সময় stack-এ বাড়তি a আর $ থাকতে পারে, আর একটি চাল কিছুই করে না।
  2. একটি accept state. নতুন state qd (ফাঁকা করার জন্য) আর qf (নতুন accept). q3 থেকে ε, ε → ε চালে qd; q3 আর accept নয়।
  3. ফাঁকা stack. qd-এ ε, a → ε loop (Γ − {$} = {a}), আর ε, $ → ε চালে qf. $ সবার নিচে, তাই qf-এ ঢোকার মুহূর্তে stack ফাঁকা।
  4. ভাঙা চাল খোঁজা। সব চাল পরখ: $ push, a push, a pop, a pop (qd), $ pop ঠিক আছে। কিন্তু q2 → q3 আর নতুন q3 → qd, দুটিই ε, ε → ε: push-ও নয়, pop-ও নয়।
  5. প্রথম ভাঙন। নতুন চিহ্ন X আর state m1: q2 থেকে ε, ε → X চালে m1, তারপর ε, X → ε চালে q3. একসঙ্গে দুটি চাল পুরোনো একটির সমান।
  6. দ্বিতীয় ভাঙন। একইভাবে m2: q3 → m2 (push X), m2 → qd (pop X).
  7. ফল। P2: ৭টি state (q1, q2, q3, m1, m2, qd, qf), ৯টি চাল, প্রতিটি ঠিক একটি push বা pop. পরের Python ব্লক দেখায়, দৈর্ঘ্য ৮ পর্যন্ত P1 আর P2 হুবহু একই ২৫টি string গ্রহণ করে, আর P2-তে aab-এর গ্রহণ শেষ হয় ফাঁকা stack-এ।

৫ · Apq গঠন — দুই state-এর মাঝের সব string

এবার মূল ধারণা, Apq গঠন। Normalised PDA P-এর প্রতিটি state-জোড়া p, q-এর জন্য একটি variable Apq, যার কাজ:

Apq ⇒∗ x ⇔ P ফাঁকা stack নিয়ে p থেকে শুরু করে x পড়ে ফাঁকা stack নিয়ে q-তে পৌঁছাতে পারে

(আরও সাধারণভাবে: যেকোনো stack নিয়ে শুরু করে একই stack নিয়ে শেষ, মাঝখানে কখনো শুরুর stack-এর নিচে হাত না দিয়ে; নিচের অংশ তো ছোঁয়াই হয় না, তাই এটি একই কথা।) তাহলে start variable Aq0,qaccept, আর শর্ত ১–২-এর কারণে এটি ঠিক L(P) তৈরি করে।

Apq-এর নিয়ম কী হবে? ফাঁকা stack-এ p থেকে ফাঁকা stack-এ q-তে যাওয়ার একটি computation নিন, যা x পড়ে। x ≠ ε হলে বা computation-এ অন্তত একটি চাল থাকলে, প্রথম চালটি অবশ্যই push (ফাঁকা stack থেকে pop করা যায় না), আর শেষ চালটি অবশ্যই pop (শেষে stack ফাঁকা)। এখন দুটি সম্ভাবনা:

  • ক্ষেত্র ১: প্রথম চালে push করা চিহ্ন u-টিই শেষ চালে pop হয়। তাহলে মাঝখানে stack কখনো ফাঁকা হয় না (u নিচে বসে থাকে)। প্রথম চাল p → r, a পড়ে; শেষ চাল s → q, b পড়ে; মাঝের অংশ r থেকে s, u-এর ওপরে, “ফাঁকা থেকে ফাঁকা”। নিয়ম: Apq → a Ars b.
  • ক্ষেত্র ২: প্রথম push-এর চিহ্ন মাঝপথে কোথাও pop হয়ে যায়, ধরুন state r-এ, যেখানে stack আবার ফাঁকা। তাহলে computation দুই টুকরো, দুটিই ফাঁকা থেকে ফাঁকা। নিয়ম: Apq → AprArq.
গঠন ৫.১ (Apq grammar)

Normalised P = (Q, Σ, Γ, δ, q0, {qaccept}) থেকে G-এর variable {Apq : p, q ∈ Q}, start Aq0,qaccept, আর নিয়ম:
১. প্রতিটি p, q, r, s ∈ Q, u ∈ Γ, a, b ∈ Σε-এর জন্য: যদি δ(p, a, ε)-এ (r, u) থাকে আর δ(s, b, u)-এ (q, ε) থাকে, তবে Apq → aArsb.
২. প্রতিটি p, q, r ∈ Q-এর জন্য Apq → AprArq.
৩. প্রতিটি p ∈ Q-এর জন্য App → ε।

নিচের ছবি একটি computation-এর stack-উচ্চতার পাহাড় দেখায়: BAL-এর একটি normalised PDA, যেখানে state 0 থেকে ε, ε → $ চালে 1; 1-এ “(, ε → (” আর “), ( → ε”; 1 থেকে ε, $ → ε চালে accept state 2. Input “(())()”।

“(())()”-এর stack-উচ্চতা আর Apq-এর দুই ক্ষেত্র

প্রতি চালে উচ্চতা এক ওঠে বা নামে। বাইরের $-জোড়া ক্ষেত্র ১; উচ্চতা ১-এর দাগ মাঝপথে ছোঁয়া (কমলা বিন্দু) ক্ষেত্র ২।

Stack height profile of (())() on the normalised BAL PDA ε(() )()ε (())() 0123 r = 1 সবুজ: $ push আর $ pop → A02 → A11
ছবি ৩৪.২ — নীল অংশ $-এর ওপরে, state 1 থেকে state 1. সেটি উচ্চতা ১-এ একবার ফেরে, তাই দুই টুকরো (()) আর (), প্রতিটি আবার ক্ষেত্র ১।
1লক্ষ্য: A02 ⇒* (())()2ক্ষেত্র ১: A02 → A113ক্ষেত্র ২: A11 → A11 A114ক্ষেত্র ১: A11 → ( A11 )5ধরন ৩: A11 → ε
এই ধাপের হিসাব
টুকরো
উচ্চতা
derivation
  1. লক্ষ্য। PDA “(())()” পড়ে state 0 থেকে 2-তে যায়, উচ্চতা 0 থেকে শুরু, 0-তে শেষ। দেখাতে হবে A02 ⇒∗ (())()।
  2. ক্ষেত্র ১। প্রথম চাল 0 → 1-এ $ push (কিছু না পড়ে), শেষ চাল 1 → 2-এ সেই $ pop. a = b = ε, r = s = 1: নিয়ম A02 → A11.
  3. ক্ষেত্র ২। $-এর ওপরের অংশ state 1 থেকে state 1. (()) পড়ার পর উচ্চতা আবার ১ (ছবির কমলা বিন্দু), state 1. তাই A11 → A11A11, r = 1.
  4. ক্ষেত্র ১, বাঁ টুকরো। (())-এ প্রথম “(”-এর push শেষ “)”-এ pop: p = r = s = q = 1, a = (, b = ). নিয়ম A11 → (A11).
  5. আবার ক্ষেত্র ১। ভেতরের ()-ও একই জোড়া: A11 → (A11).
  6. ধরন ৩। সবচেয়ে ভেতরে কোনো চাল নেই: state 1 থেকে state 1, শূন্য চাল। A11 → ε.
  7. ডান টুকরো। ()-ও ক্ষেত্র ১: A11 → (A11).
  8. শেষ। A11 → ε. A02 ⇒ A11 ⇒ A11A11 ⇒ (A11)A11 ⇒ ((A11))A11 ⇒ (())A11 ⇒ (())(A11) ⇒ (())(), ৭টি ধাপ। Derivation-এর গাছ আর পাহাড়ের আকার হুবহু এক।

এবার পুরো গঠন কোডে। pda_to_cfg তিন ধরনের নিয়ম বানায়: প্রতিটি push-চালকে প্রতিটি pop-চালের সঙ্গে জোড়া দিয়ে দেখে একই চিহ্ন কি না (ধরন ১), সব p, q, r-এর জন্য ধরন ২, আর সব p-এর জন্য ধরন ৩. strings প্রতিটি variable থেকে দৈর্ঘ্য ≤ n-এর সব string বের করে, fixpoint iteration-এ (পর্ব ২৫-এর মতো)। Variable এখানে state-এর একটি জোড়া, যেমন ("1", "1") মানে A11.

def pda_to_cfg(T, Q):              # Sipser's A_pq grammar, variable = (p, q)
    R = {(p, q): [] for p in Q for q in Q}
    for (p, a, _, r, y) in T:
        for (s, b, x, q, _) in T:      # a push of u matched with a pop of u
            if len(y) == 1 and x == y[0]:
                R[p, q].append(tuple(c for c in (a, (r, s), b) if c))
    for p, q, r in product(Q, Q, Q): R[p, q].append(((p, r), (r, q)))
    for p in Q: R[p, p].append(())
    return R
def strings(R, S, n):              # every string of length <= n (fixpoint)
    L, ch = {A: set() for A in R}, True
    while ch:
        ch = False
        for A in R:
            for r in R[A]:
                for c in product(*[L[X] if X in R else {X} for X in r]):
                    if len(w := "".join(c)) <= n and w not in L[A]:
                        L[A].add(w); ch = True
    return L
PB = [("0", "", "", "1", ("$",)), ("1", "(", "", "1", ("(",)),
      ("1", ")", "(", "1", ()), ("1", "", "$", "2", ())]
G = pda_to_cfg(PB, "012")
L = strings(G, ("0", "2"), 8)
print(len(G), "variables,", sum(map(len, G.values())), "rules")
print("generating:", sorted("A" + p + q for (p, q) in G if L[p, q]))
for A in [("0", "2"), ("1", "1")]:
    print("A" + "".join(A), "->", " | ".join(" ".join(
        x if type(x) is str else "A" + "".join(x) for x in r) or "ε"
        for r in G[A] if all(type(x) is str or L[x] for x in r)))
ws = ["".join(t) for k in range(9) for t in product("()", repeat=k)]
print("A02 up to 8:", len(L["0", "2"]), "strings | PDA agrees:",
      sorted(L["0", "2"]) == sorted(w for w in ws
                                   if run(PB, "0", {"2"}, w, lambda k: 9)))

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

9 variables, 32 rules
generating: ['A00', 'A02', 'A11', 'A22']
A02 -> A11 | A00 A02 | A02 A22
A11 -> ( A11 ) | A11 A11 | ε
A02 up to 8: 23 strings | PDA agrees: True

৩টি state থেকে 32 = ৯টি variable, আর ৩২টি নিয়ম: ২টি ধরন ১ ($-জোড়া থেকে A02 → A11, বন্ধনী-জোড়া থেকে A11 → (A11)), 33 = ২৭টি ধরন ২, ৩টি ধরন ৩. মাত্র ৪টি variable generating; যেমন A01 কিছুই তৈরি করে না, কারণ 0 থেকে 1-এ যেতে $ push হয়, তাই “ফাঁকা থেকে ফাঁকা” অসম্ভব। Useless নিয়ম বাদ দিয়ে ছাপা দুটি লাইনে A00 আর A22 শুধু ε দেয়, তাই grammar-টি কার্যত S → S′, S′ → (S′) ∣ S′S′ ∣ ε. দৈর্ঘ্য ৮ পর্যন্ত ২৩টি string (1 + 1 + 2 + 5 + 14), PDA-র সঙ্গে হুবহু এক। লক্ষ করুন, এই grammar ambiguous (S′S′ নিয়মের কারণে “()()()”-এর দুটি গাছ), যদিও শুরুর BAL grammar ambiguous ছিল না (পর্ব ২৭)। গঠন language রক্ষা করে, grammar-এর ধর্ম নয়।

৬ · Apq গঠন কেন সঠিক — দুই দিকে induction

লেমা ৫.১ (PDA → CFG)

প্রতিটি PDA P-এর জন্য একটি CFG G আছে যাতে L(G) = L(P). লেমা ৪.১ দিয়ে P-কে normalise করে গঠন ৫.১ খাটালে G পাওয়া যায়; নিচের দুটি দাবি থেকে Aq0,qaccept ⇒∗ x ⇔ x ∈ L(P).

দাবি ৬.১: Apq ⇒∗ x হলে, P x পড়ে ফাঁকা stack নিয়ে p থেকে ফাঁকা stack নিয়ে q-তে যেতে পারে। প্রমাণ (derivation-এর ধাপ-সংখ্যা k-এর ওপর induction):

  1. ভিত্তি k = 1: এক ধাপে terminal string আসে শুধু ধরন ৩ থেকে (ধরন ১ আর ২-এর ডান দিকে variable আছে)। তাই নিয়মটি App → ε, x = ε, আর শূন্য চালে p থেকে p যাওয়া যায়। — নিয়মের আকার
  2. ধাপ: ধরুন k + 1 ধাপের derivation, প্রথম ধাপ ধরন ১: Apq ⇒ aArsb, আর x = ayb যেখানে Ars ⇒∗ y, k ধাপে। Hypothesis-এ y-এর জন্য r থেকে s পর্যন্ত একটি ফাঁকা-থেকে-ফাঁকা computation আছে। — induction hypothesis
  3. নিয়মটি আছে মানে δ(p, a, ε)-এ (r, u) আর δ(s, b, u)-এ (q, ε)। তাই: p-তে a পড়ে u push করে r; তারপর y-এর computation, u-এর ওপরে, u না ছুঁয়ে, s-এ শেষ; তারপর b পড়ে u pop করে q. মোট x = ayb পড়া, শেষে stack ফাঁকা। — নিচের stack না ছোঁয়া computation যেকোনো stack-এর ওপর চলে
  4. প্রথম ধাপ ধরন ২: Apq ⇒ AprArq, x = yz, প্রতিটি অংশ k-এর কম ধাপে। Hypothesis-এ y-এর computation p → r আর z-এর computation r → q, দুটিই ফাঁকা থেকে ফাঁকা; পরপর জুড়লে x-এর computation p → q. ∎ — computation জোড়া দেওয়া

দাবি ৬.২: P x পড়ে ফাঁকা stack নিয়ে p থেকে ফাঁকা stack নিয়ে q-তে যেতে পারলে, Apq ⇒∗ x. প্রমাণ (computation-এর চাল-সংখ্যা k-এর ওপর induction):

  1. ভিত্তি k = 0: শূন্য চালে p = q আর x = ε; ধরন ৩-এর App → ε আছে। — গঠনের ধরন ৩
  2. ধাপ k ≥ 1: শুরুতে stack ফাঁকা, তাই প্রথম চাল push (pop অসম্ভব); শেষে ফাঁকা, তাই শেষ চাল pop. শর্ত ৩-এর জন্য প্রতিটি চাল এর একটি। — normalisation
  3. ক্ষেত্র ১: প্রথম চালে push করা u-ই শেষ চালে pop হয়। প্রথম চাল p → r, a পড়ে; শেষ চাল s → q, b পড়ে; x = ayb. মাঝের y-এর computation r থেকে s, u-এর ওপরে, u না ছুঁয়ে, k − 2 চালে; u সরিয়ে নিলে এটি ফাঁকা-থেকে-ফাঁকা। Hypothesis-এ Ars ⇒∗ y, আর ধরন ১-এর নিয়ম Apq → aArsb আছে। — গঠনের ধরন ১
  4. ক্ষেত্র ২: u আগেই কোথাও pop হয়। সেই মুহূর্তে stack আবার ফাঁকা; ধরুন state r, আর তখন পর্যন্ত পড়া y, বাকি z. দুই টুকরোই ফাঁকা-থেকে-ফাঁকা আর প্রতিটি k-এর কম চালে। Hypothesis-এ Apr ⇒∗ y, Arq ⇒∗ z, আর ধরন ২ দিয়ে Apq ⇒ AprArq ⇒∗ yz = x. ∎ — গঠনের ধরন ২

দুই দাবি মিলিয়ে, শর্ত ১–২ ব্যবহার করে: x ∈ L(P) ⇔ ফাঁকা stack-এ q0 থেকে ফাঁকা stack-এ qaccept ⇔ Aq0,qaccept ⇒∗ x. এতে উপপাদ্য ১.১ সম্পূর্ণ। (একটি সূক্ষ্মতা: শর্ত ৩ না থাকলে ধাপ ২-এর “প্রথম চাল push” যুক্তি ভেঙে যায়, কারণ প্রথম চাল কিছু না-ও করতে পারত। Normalisation ঠিক এজন্যই।)

এবার অংশ ৪-এর normalisation নিজে যাচাই করি, আর বড় একটি PDA থেকে grammar বানাই। নিচের ব্লক P1 আর P2 দুটিকে দৈর্ঘ্য ৮ পর্যন্ত লক্ষ্য-language-এর সঙ্গে মেলায়, দুটির গ্রহণের শেষে stack দেখায়, তারপর P2 থেকে Apq grammar বানিয়ে দৈর্ঘ্য ৬ পর্যন্ত মেলায়।

P1 = [("q1", "", "", "q2", ("$",)), ("q2", "a", "", "q2", ("a",)),
      ("q2", "", "", "q3", ()), ("q3", "b", "a", "q3", ())]   # accept q3
P2 = [("q1", "", "", "q2", ("$",)), ("q2", "a", "", "q2", ("a",)),
      ("q2", "", "", "m1", ("X",)), ("m1", "", "X", "q3", ()),
      ("q3", "b", "a", "q3", ()), ("q3", "", "", "m2", ("X",)),
      ("m2", "", "X", "qd", ()), ("qd", "", "a", "qd", ()),
      ("qd", "", "$", "qf", ())]                             # accept qf
def target(w):                      # a^i b^j with i >= j
    i = len(w) - len(w.lstrip("a"))
    return set(w[i:]) <= {"b"} and len(w) - i <= i
ws = ["".join(t) for k in range(9) for t in product("ab", repeat=k)]
cap = lambda k: 11
one = [w for w in ws if run(P1, "q1", {"q3"}, w, cap)]
two = [w for w in ws if run(P2, "q1", {"qf"}, w, cap)]
print("P1 == P2 == target up to 8:",
      one == two == [w for w in ws if target(w)], f"({len(two)} strings)")
for w in ["aab", "aabb"]:
    print(w, "P1 ends with stack", "".join(run(P1, "q1", {"q3"}, w, cap)[-1][2]),
          "| P2 ends with stack", "".join(run(P2, "q1", {"qf"}, w, cap)[-1][2]) or "ε")
Q = ["q1", "q2", "q3", "m1", "m2", "qd", "qf"]
G = pda_to_cfg(P2, Q)
L = strings(G, ("q1", "qf"), 6)
pairs = sum(1 for t in P2 for u in P2 if len(t[4]) == 1 and u[2] == t[4][0])
print(len(G), "variables,", sum(map(len, G.values())), "rules =", pairs,
      "push/pop pairs +", len(Q) ** 3, "A_pr A_rq rules +", len(Q), "A_pp -> ε")
print("generating:", sum(1 for A in G if L[A]), "variables")
print("A(q1,qf) up to 6 == target:",
      sorted(L["q1", "qf"]) == sorted(w for w in ws if len(w) <= 6 and target(w)),
      f"({len(L['q1', 'qf'])} strings)")

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

P1 == P2 == target up to 8: True (25 strings)
aab P1 ends with stack a$ | P2 ends with stack ε
aabb P1 ends with stack $ | P2 ends with stack ε
49 variables, 357 rules = 7 push/pop pairs + 343 A_pr A_rq rules + 7 A_pp -> ε
generating: 11 variables
A(q1,qf) up to 6 == target: True (16 strings)

Normalisation language বদলায়নি: দৈর্ঘ্য ৮ পর্যন্ত তিনটি তালিকাই একই ২৫টি string. P1 aab গ্রহণ করে “a$” রেখে, P2 ফাঁকা stack-এ, ঠিক শর্ত ২. P2-র ৭টি state থেকে 72 = ৪৯টি variable আর ৩৫৭টি নিয়ম: ৭টি push/pop জোড়া ($-এর ১টি, a-এর ২টি কারণ a দুই জায়গায় pop হয়, X-এর ২ × ২ = ৪টি), 73 = ৩৪৩টি ধরন ২, ৭টি ধরন ৩. তবু মাত্র ১১টি variable generating. দৈর্ঘ্য ৬ পর্যন্ত Aq1,qf ঠিক লক্ষ্য-language-এর ১৬টি string দেয়। শিক্ষা: গঠনটি সঠিক কিন্তু অপচয়ী; বাস্তবে এর পরে পর্ব ২৮-এর useless-symbol অপসারণ চালানো হয়।

৭ · ফলাফল, আকার আর সত্যিকারের যাচাই

উপপাদ্য ১.১-এর কয়েকটি সরাসরি ফল:

  • CFL = PDA-র language: এখন থেকে কোনো language-কে CFL দেখাতে grammar বা PDA, যেটি সহজ সেটিই চলে। পর্ব ৩৭-এ CFL ∩ regular-এর closure PDA দিয়ে প্রমাণ হবে, আর union, concatenation, star grammar দিয়ে।
  • Regular ⊂ CFL: প্রতিটি DFA একটি PDA যা stack ব্যবহারই করে না: δ(q, a) = q′-এর জায়গায় “a, ε → ε”। তাই প্রতিটি regular language context-free; আর anbn CFL কিন্তু regular নয় (পর্ব ১৭), তাই অন্তর্ভুক্তি কঠোর।
  • একটি state যথেষ্ট: যেকোনো PDA → CFG → (HMU রীতিতে) এক-state PDA, empty stack দিয়ে গ্রহণ। অর্থাৎ PDA-র state-এর সসীম স্মৃতি stack-চিহ্নের ভেতরেই ঢোকানো যায়; ক্ষমতা আসে stack থেকে।
  • Deterministic নয়: CFG → PDA-র ফল সাধারণত nondeterministic. প্রতিটি CFL-এর জন্য deterministic PDA নেই, যেমন জোড় দৈর্ঘ্যের palindrome; এটি পর্ব ৩৫-এর বিষয়।
রূপান্তরফলের আকারএই পর্বের উদাহরণ
CFG → PDA৩টি মূল state; চাল 2 + |R| + |Σ|; সংক্ষেপ-push খুললে রৈখিকBAL: ২টি নিয়ম, ২টি terminal, ৬টি চাল
Normalisationপ্রতিটি চালে বড়জোর একটি নতুন state; রৈখিক৩টি state, ৪টি চাল থেকে ৭টি state, ৯টি চাল
PDA → CFG (Apq)|Q|2 variable; |Q|3টি ধরন ২ নিয়ম; ধরন ১ বড়জোর (push-চাল) × (pop-চাল)৭টি state থেকে ৪৯টি variable, ৩৫৭টি নিয়ম

দুই দিকই polynomial, তাই “একটি দেওয়া PDA-র language কি ফাঁকা?” প্রশ্নটি grammar-এ রূপান্তর করে generating চিহ্নের algorithm দিয়ে polynomial সময়ে উত্তর দেওয়া যায় (পর্ব ৩৭)। আবার membership: PDA → CFG → CNF → CYK (পর্ব ৩১)। একটি সতর্কতা: যে PDA এক চালে লম্বা string push করে, তার জন্য সরাসরি “তিন-অংশের variable” গঠন (Hopcroft–Motwani–Ullman-এর [pXq] রীতি) push-এর দৈর্ঘ্যে exponential হতে পারে; আগে normalise করলে, অর্থাৎ লম্বা push ভেঙে নিলে, বৃদ্ধি polynomial থাকে।

সত্যিকারের run: lark-এর parser বনাম automata-lib-এর PDA

নিজের লেখা simulator-এর ওপর পুরো ভরসা না রেখে দুটি স্বাধীন library দিয়ে একই প্রশ্ন করা হয়েছে। Grammar-এর দিক: lark (MIT লাইসেন্স), যার Earley parser যেকোনো CFG নেয় (Earley parser, পর্ব ৪১)। Machine-এর দিক: automata-lib (MIT লাইসেন্স)-এর NPDA class, যাতে এই পর্বের CFG → PDA গঠনে বানানো PDA বসানো হয়েছে। automata-lib Hopcroft–Motwani–Ullman রীতি মানে: শুরুতে stack-এ একটি চিহ্ন Z থাকে আর প্রতিটি চাল একটি চিহ্ন pop করে, তাই আমাদের $-এর ভূমিকা Z নিয়েছে। Scratch-এর একটি uv project-এ (Python 3.12.13, lark 1.3.1, automata-lib 9.2.0) চালানো হয়েছে; এটি একটি সত্যিকারের run, path বাদে আউটপুট হুবহু।

~/bazarghar-toc$ uv run python lark_vs_pda.py
lark 1.3.1 | automata-lib 9.2.0
8495 strings: lark accepts 203, PDA and lark agree on 8495
tree for (()):
start
  s
    s
      s
      s
    s

পরীক্ষার set: দৈর্ঘ্য ০ থেকে ১২-এর সব ৮,১৯১টি string, fixed seed (34)-এ দৈর্ঘ্য ১৩–২০-এর ৩০০টি random string, আর (k)k আকারের ৪টি লম্বা string. দুটি library প্রতিটি string-এ একমত; lark ২০৩টি গ্রহণ করেছে (দৈর্ঘ্য ১২ পর্যন্ত ১৯৭টি সুষম string, ৪টি লম্বা, আর random-এর মধ্যে ২টি)। lark-এর গাছটি “(())”-এর parse tree: মূলের s-এর দুই s-সন্তান, বাঁয়েরটির আবার দুই ফাঁকা s-সন্তান; বন্ধনী token lark নিজে থেকে লুকিয়ে রাখে। এটি ঠিক stepper ১-এর derivation S ⇒ (S)S ⇒ ((S)S)S ⇒ ⋯-এর গাছ। মিল সব সঠিকতার প্রমাণ নয় (৮,৪৯৫টি string সসীম), কিন্তু গঠন বা কোডের সাধারণ ভুল এতে ধরা পড়ে।

আরও গভীরে: Apq গঠনের পাহাড়-ছবি একটি গভীর ফলের আভাস দেয়: প্রতিটি CFL-এর ভেতরে বন্ধনী মেলানোর একটি কাঠামো আছে। Chomsky–Schützenberger উপপাদ্য (১৯৬৩) বলে, প্রতিটি CFL = h(Dk ∩ R), যেখানে Dk হলো k রকম বন্ধনীর Dyck language, R regular আর h একটি homomorphism. আবার PDA-র deterministic রূপের সঙ্গে LR parsing-এর যোগ: Knuth ১৯৬৫ সালে দেখান বলে পরিচিত যে deterministic CFL ঠিক সেই language-গুলো, যাদের LR(k) grammar আছে (পর্ব ৩৫ আর ৩৯)।

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

  • S → aSb ∣ ε-এর PDA বানান। qs → ql: ε, ε → S$; ql-এ ε, S → aSb; ε, S → ε; a, a → ε; b, b → ε; ql → qa: ε, $ → ε. মোট ৬টি চাল।
  • CFG → PDA-র PDA কোন derivation অনুকরণ করে? Leftmost derivation; ওপরের variable সবসময় সবচেয়ে বাঁয়ের variable.
  • PDA → CFG-এর আগে কোন তিন শর্ত? একটি accept state; গ্রহণের আগে stack ফাঁকা; প্রতিটি চাল ঠিক একটি push বা একটি pop.
  • Apq-এর তিন ধরনের নিয়ম লিখুন। Apq → aArsb (push u আর pop u-এর জোড়া), Apq → AprArq, App → ε.
  • n state-এর normalised PDA থেকে কয়টি variable? n2, আর ধরন ২-এর নিয়ম n3টি।

৮ · AI-এর যুগে PDA ↔ CFG রূপান্তর

AI assistant-কে “এই grammar-এর PDA বানাও” বা “এই PDA-র grammar দাও” বললে সে সাধারণত দেখতে ঠিক একটি উত্তর দেয়। ভুলগুলো সূক্ষ্ম: একটি terminal-এর match-চাল বাদ পড়া, $ রাখতে ভুলে যাওয়া, push-এর ক্রম উল্টো লেখা (w-এর শেষ চিহ্ন ওপরে), বা Apq গঠন normalise না করেই চালানো। আরও আছে প্রমাণে দিক গুলিয়ে ফেলা: শুধু L(G) ⊆ L(P) দেখিয়ে সমতা দাবি করা।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
w push করার সময় ক্রম উল্টো, ফলে rightmost চিহ্ন ওপরেএকটি ছোট string-এ configuration ধরে ধরে trace করুন; প্রথম match-ই ব্যর্থ হবে
শুরুতে $ না রাখা, অথচ শেষে “stack ফাঁকা হলে accept” লেখাSipser-এর PDA stack ফাঁকা কি না দেখতে পারে না; $ আছে কি না খুঁজুন
Normalise না করে Apq নিয়ম লেখা, বা ধরন ২ বাদ দেওয়া“()()”-এর মতো মাঝপথে stack ফাঁকা হওয়া string-এ grammar পরখ করুন
ε-কে ভুলে যাওয়া: ε ∈ L অথচ PDA বা grammar ε দেয় নাbrute force-এ দৈর্ঘ্য ০ থেকে শুরু করে তালিকা মেলান
এক দিকের প্রমাণ দিয়ে সমতা দাবি; বা “PDA → CFG-এর grammar unambiguous” জাতীয় ভুল দাবি⊆ আর ⊇ দুটি আলাদা দেখুন; ambiguity-র দাবি একটি দুই-গাছের string দিয়ে পরখ করুন
বানানো রেফারেন্স বা সাল (যেমন সমতার আবিষ্কারক)Sipser বা Hopcroft–Motwani–Ullman-এ নিজে মিলিয়ে নিন

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

আমি গণনার তত্ত্ব শিখছি। Sipser-এর রীতিতে (PDA = (Q, Σ, Γ, δ, q0, F), final state দিয়ে গ্রহণ) এই grammar থেকে PDA বানাও: S → aSa ∣ bSb ∣ c. ১. সব transition "a, x → y" আকারে একটি তালিকায় লেখো, আর বলো কোনটি কোন নিয়ম বা terminal থেকে এসেছে। ২. "abcba" string-এ PDA-র পুরো configuration-ক্রম (state, বাকি input, stack, ওপর বাঁয়ে) লেখো। ৩. এরপর এই PDA-কে normalise করে A_pq গঠনে আবার grammar বানানোর প্রথম তিনটি ধাপ দেখাও, প্রতিটি শর্ত কেন দরকার তা বলো। ৪. শুধু standard library দিয়ে একটি ছোট Python কোড দাও, যা দৈর্ঘ্য 7 পর্যন্ত সব string-এ PDA আর grammar মেলায়। ৫. কোনো দাবি নিয়ে নিশ্চিত না হলে স্পষ্ট করে বলো; বানানো রেফারেন্স দিও না।

(উত্তর পেলে এই পর্বের প্রথম Python ব্লকে cfg_to_pda দিয়ে নিজেও PDA বানান, run দিয়ে "abcba" চালান, আর দুই তালিকা মিলিয়ে দেখুন।)

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

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

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

প্র ০১Stack আর grammar-এর যোগ কে, কবে খুঁজে পেলেন? একই ফল প্রায় একসঙ্গে কয়েকজনের হাতে কেন এল?

Stack প্রথমে এসেছিল তত্ত্ব থেকে নয়, প্রয়োগ থেকে। ১৯৫০-এর দশকের শেষে জার্মানির Friedrich Bauer আর Klaus Samelson গাণিতিক সূত্রকে যন্ত্রের নির্দেশে অনুবাদের একটি পদ্ধতি দেন, যেখানে অপেক্ষমাণ operator আর বন্ধনী একটি “Keller” (ভাঁড়ার ঘর) বা stack-এ রাখা হয়; ১৯৫৭ সালে এর একটি patent আবেদনও করা হয়েছিল বলে পরিচিত। একই সময়ে ALGOL ভাষার নকশা চলছিল, যার syntax প্রথমবার BNF-এ, অর্থাৎ একটি context-free grammar-এ, লেখা হয়। ফলে প্রশ্নটি স্বাভাবিকভাবে উঠল: grammar-এ লেখা যেকোনো ভাষা কি একটি stack-যন্ত্র দিয়ে পড়া যায়, আর উল্টোটা?

তাত্ত্বিক উত্তর এল ১৯৬২–৬৩ সালের দিকে। Noam Chomsky ১৯৬২ সালে MIT-র একটি গবেষণা প্রতিবেদনে “Context-free grammars and pushdown storage” শিরোনামে, Robert Evey ১৯৬৩ সালে Harvard-এর একটি doctoral thesis-এ pushdown store machine নিয়ে, আর Marcel-Paul Schützenberger ১৯৬৩ সালে Information and Control পত্রিকায় সমতার বিভিন্ন রূপ দেখান বলে সাধারণত ধরা হয়। কে ঠিক কোন অংশ প্রথম প্রমাণ করেছেন, সূত্রভেদে বর্ণনা আলাদা; তাই সাধারণত তিনজনের নামই একসঙ্গে বলা হয়।

একসঙ্গে কয়েকজনের হাতে আসার কারণ পরিবেশ। Compiler-নির্মাতারা stack ব্যবহার করছিলেন, ভাষাবিজ্ঞানীরা grammar-এর শ্রেণি নিয়ে ভাবছিলেন, আর automata তত্ত্বে Rabin–Scott (১৯৫৯)-এর পরে “finite automaton-এর সঙ্গে একটু স্মৃতি যোগ করলে কী হয়” প্রশ্নটি স্বাভাবিক ছিল। বিজ্ঞানে এমন সমকালীন আবিষ্কার প্রায়ই ঘটে যখন প্রশ্নের উপকরণ সবার হাতে আসে।

মূল উপলব্ধি: PDA ↔ CFG-এর সমতা প্রয়োগ (stack দিয়ে সূত্র অনুবাদ) আর তত্ত্ব (grammar-এর শ্রেণি) মিলিত হওয়ার ফল। ইতিহাসের খুঁটিনাটি নিয়ে সূত্রভেদ থাকায় নাম আর সাল সতর্কভাবে বলা ভালো।

প্র ০২যদি এক-state PDA-ই সব CFL চেনে, তবে PDA নকশায় আমরা অনেক state কেন ব্যবহার করি?

গাণিতিকভাবে দাবিটি সত্য: যেকোনো PDA-কে grammar-এ রূপান্তর করে, তারপর Hopcroft–Motwani–Ullman-এর এক-state গঠনে PDA বানালে empty stack দিয়ে গ্রহণ করে এমন একটি এক-state PDA পাওয়া যায়। অর্থাৎ state-এর সসীম স্মৃতি পুরোপুরি stack-চিহ্নের ভেতরে ঢোকানো যায়; Apq-এর variable নিজেই দুটি state-এর তথ্য বহন করে, আর সেই variable stack-এ চড়ে।

কিন্তু “ক্ষমতা” আর “নকশার সুবিধা” আলাদা প্রশ্ন। প্রথমত, পড়ার সুবিধা: anbn-এর PDA-তে “এখনো a পড়ছি” আর “এখন b পড়ছি” দুটি state থাকলে যন্ত্রটি এক নজরে বোঝা যায়; এক-state রূপে একই তথ্য একটি অদ্ভুত variable-এ লুকানো থাকে। দ্বিতীয়ত, আকার: এক-state রূপে যাওয়ার পথে |Q|2 variable আর |Q|3 নিয়ম তৈরি হয়, তারপর আরও চাল। তৃতীয়ত, determinism: final state দিয়ে গ্রহণ করে এমন deterministic PDA-কে এক-state empty-stack রূপে আনলে সাধারণত deterministic থাকে না, আর empty-stack DPDA শুধু prefix-free language চেনে (পর্ব ৩৩ আর ৩৫)। Parser-এর জন্য determinism সবচেয়ে মূল্যবান ধর্ম।

একই ঘটনা অন্য জায়গায়ও দেখবেন। Turing machine-এর state-সংখ্যা কমানো যায় tape alphabet বাড়িয়ে, আর উল্টোটা (Shannon-এর ১৯৫৬ সালের কাজ হিসেবে পরিচিত); বাস্তব program-এও কোন তথ্য control flow-এ আর কোন তথ্য data-তে রাখবেন, সেটি নকশার পছন্দ। বাজারঘরের checkout workflow-এ “পেমেন্ট বাকি” একটি state হতে পারে, বা order-এর একটি field; দুটিই চলে, কিন্তু একটি পড়তে বা পরীক্ষা করতে সহজ।

মূল উপলব্ধি: PDA-র ক্ষমতা আসে stack থেকে, state থেকে নয়। তবু state পড়ার সুবিধা, আকার আর determinism দেয়, তাই নকশায় এর মূল্য বিশাল।

প্র ০৩CFG → PDA গঠনটি এত সরল হলে বাস্তবের parser কেন সরাসরি এটি ব্যবহার করে না?

কারণ গঠনটি nondeterministic. ওপরে S থাকলে PDA কোন নিয়ম খাটাবে, তা সে “অনুমান” করে; গণিতে এটি নিখুঁত, কারণ একটি সফল শাখাই যথেষ্ট। কিন্তু বাস্তব কম্পিউটার অনুমান করতে পারে না; তাকে শাখাগুলো একটি একটি করে বা একসঙ্গে অনুকরণ করতে হয়। Backtracking দিয়ে শাখা খুঁজলে সময় exponential হতে পারে, আর left recursion থাকলে অসীম loop-ও হতে পারে (অংশ ৩-এর সতর্কতা)। এই পর্বের BFS simulator ছোট input-এ চলে, কিন্তু configuration-এর সংখ্যা বড় input-এ দ্রুত বাড়ে।

বাস্তব সমাধান তিন রকম। এক, grammar-কে এমন আকারে আনা যাতে অনুমানের দরকারই না থাকে: পরের এক token দেখে কোন নিয়ম খাটবে তা নিশ্চিত বলা যায়। এটাই LL(1) parsing (পর্ব ৩৮), যা আসলে CFG → PDA গঠনের deterministic রূপ, যেখানে expand-এর পছন্দ একটি টেবিল থেকে আসে। দুই, উল্টো দিক থেকে কাজ: input থেকে শুরু করে নিয়মের ডান দিক খুঁজে বাঁ দিকে বদলানো (shift-reduce), যা LR parsing (পর্ব ৩৯); এটিও একটি deterministic PDA. তিন, nondeterminism-কে বুদ্ধিমানভাবে অনুকরণ করা: Earley আর GLR algorithm সব শাখা একসঙ্গে রাখে, কিন্তু একই অবস্থা দুবার হিসাব করে না, ফলে যেকোনো CFG-তে বড়জোর O(n3) সময় লাগে (পর্ব ৪১)। ওপরের lark run ঠিক এই তৃতীয় পথের।

তাই এই পর্বের গঠন বাস্তবের parser-এর “পূর্বপুরুষ”: top-down parser তার deterministic উত্তরসূরি, আর bottom-up parser একই সমতার আরেকটি রূপ। ভবিষ্যতের Programming Languages & Compilers কোর্সে এগুলো বিস্তারিত আসবে।

মূল উপলব্ধি: তত্ত্বের PDA অনুমান করে, বাস্তবের parser পারে না। LL, LR, Earley আর GLR হলো এই অনুমানকে টেবিল বা চতুর অনুকরণ দিয়ে বদলানোর চারটি উপায়।

প্র ০৪Apq গঠনের “পাহাড়” ছবি বন্ধনী মেলানোর কথা মনে করায়। এই মিল কি কাকতালীয়, নাকি গভীর কিছু?

গভীর। Normalised PDA-র প্রতিটি চাল একটি push বা একটি pop, আর প্রতিটি push-এর একটি নির্দিষ্ট pop জোড়া আছে। Push-কে “(” আর pop-কে “)” লিখলে যেকোনো গ্রহণযোগ্য computation হয়ে যায় একটি সুষম বন্ধনীর string; বিভিন্ন stack-চিহ্নের জন্য বিভিন্ন রকম বন্ধনী। Apq-এর ক্ষেত্র ১ (বাইরের জোড়া) আর ক্ষেত্র ২ (পাশাপাশি দুই জোড়া) ঠিক Dyck language-এর grammar S → (S) ∣ SS ∣ ε-এর দুই নিয়ম। BAL-এর ক্ষেত্রে Python ব্লক এই grammar-ই ফেরত দিয়েছে।

এই পর্যবেক্ষণটি সাধারণ করলে Chomsky–Schützenberger উপপাদ্য (১৯৬৩) পাওয়া যায়: প্রতিটি CFL হলো কোনো Dyck language-কে একটি regular language দিয়ে ছেঁকে (intersection), তারপর একটি homomorphism দিয়ে বন্ধনীগুলো আসল চিহ্নে বদলে পাওয়া ভাষা। Regular অংশটি PDA-র state-এর নিয়ম (কোন চালের পর কোন চাল চলে) বহন করে, Dyck অংশটি stack-এর নিয়ম। অর্থাৎ প্রতিটি context-free language আসলে “সসীম নিয়ন্ত্রণ + বন্ধনী মেলানো”।

এর একটি ব্যবহারিক প্রতিফলনও আছে। বাজারঘরের order-query ভাষায় (মডিউল ৫) বন্ধনী আর AND/OR-এর নেস্টিং-ই একে regular-এর বাইরে নেয়; বাকি সব (keyword, সংখ্যা, field-এর নাম) lexer-এর regular কাজ (পর্ব ২২)। Compiler-এর lexer আর parser-এর ভাগাভাগি ঠিক এই উপপাদ্যের আকারে: regular অংশ একদিকে, বন্ধনী মেলানো অন্যদিকে।

মূল উপলব্ধি: Stack-এর push/pop জোড়াই বন্ধনী, আর Apq গঠন সেই বন্ধনীর grammar. প্রতিটি CFL-এর হৃদয়ে Dyck language আর একটি regular ছাঁকনি।

প্র ০৫রূপান্তর algorithm দিয়ে করা যায়, তবু “দুটি CFG একই language দেয় কি?” প্রশ্নটি undecidable. এটি কীভাবে সম্ভব?

দুটি আলাদা প্রশ্ন গুলিয়ে ফেলা সহজ। এই পর্বের উপপাদ্য বলে: প্রতিটি grammar-এর জন্য একটি PDA আছে, আর সেটি যান্ত্রিকভাবে বানানো যায়; প্রতিটি PDA-র জন্যও একটি grammar. এটি একটি বর্ণনা থেকে বর্ণনায় অনুবাদ। কিন্তু দুটি বর্ণনা একই language দেয় কি না, অর্থাৎ L(G1) = L(G2)?, এটি একটি ধর্ম যাচাইয়ের প্রশ্ন, আর অনুবাদ করে সেটি সহজ হয় না: দুই grammar-কে PDA বানালেও প্রশ্ন থাকে “দুই PDA-র language এক কি না”।

Regular language-এ পরিস্থিতি আলাদা ছিল: DFA-কে minimize করলে একটি অনন্য রূপ পাওয়া যায়, তাই সমতা decidable (পর্ব ১৯ আর ২০)। CFL-এর জন্য এমন কোনো অনন্য “minimal PDA” নেই, আর বাস্তবে সমতা, universality (L = Σ∗?), inclusion বা ambiguity, এই প্রশ্নগুলো undecidable; প্রমাণ আসবে Post correspondence problem দিয়ে (পর্ব ৫৪), আর তালিকাটি পর্ব ৩৭-এ। তবে emptiness আর membership decidable, আর ঠিক এই পর্বের রূপান্তরের কারণে PDA-র জন্যও: PDA → CFG, তারপর generating চিহ্ন বা CYK.

একটি চমকপ্রদ সূক্ষ্মতা: deterministic PDA-র জন্য সমতার প্রশ্ন decidable, যা Géraud Sénizergues ১৯৯০-এর দশকের শেষে প্রমাণ করেন বলে পরিচিত, আর এর জন্য ২০০২ সালে তিনি Gödel Prize পান বলে উল্লেখ পাওয়া যায় (পর্ব ৩৫)। অর্থাৎ nondeterminism শুধু নকশার সুবিধা নয়, এটি কিছু প্রশ্নকে আক্ষরিক অর্থেই অসমাধানযোগ্য করে।

মূল উপলব্ধি: “রূপান্তর করা যায়” আর “ধর্ম যাচাই করা যায়” এক কথা নয়। PDA ↔ CFG অনুবাদ সবসময় সম্ভব, কিন্তু দুটি grammar-এর সমতা যাচাই সাধারণভাবে অসম্ভব।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। cfg_to_pda.py আর pda_to_cfg.py ব্লকের function দিয়ে নিজের উত্তর যাচাইও করতে পারেন।

  1. নকশা ও trace: G: S → aSa ∣ bSb ∣ c (language {wcwR : w ∈ {a, b}∗})। লেমা ২.১-এর গঠনে PDA-র সব চাল লিখুন, তারপর “abcba”-এর গ্রহণযোগ্য computation দিন। কয়টি চাল লাগে?

    চাল (মোট ৮টি): qs → ql: ε, ε → S$; ql-এ ε, S → aSa; ε, S → bSb; ε, S → c; a, a → ε; b, b → ε; c, c → ε; ql → qa: ε, $ → ε.

    Computation: (qs, abcba, ε) ⊢ (ql, abcba, S$) ⊢ (ql, abcba, aSa$) ⊢ (ql, bcba, Sa$) ⊢ (ql, bcba, bSba$) ⊢ (ql, cba, Sba$) ⊢ (ql, cba, cba$) ⊢ (ql, ba, ba$) ⊢ (ql, a, a$) ⊢ (ql, ε, $) ⊢ (qa, ε, ε).

    ১০টি চাল: ১টি প্রস্তুতি, ৩টি expand, ৫টি match, ১টি শেষ। Scratch-এ এই পর্বের run হুবহু এই ক্রমই দিয়েছে। লক্ষ করুন, এই language deterministic PDA-তেও চেনা যায় (c দেখে মাঝখান বোঝা যায়, পর্ব ৩৫), কিন্তু গঠনের PDA তবু nondeterministic.

  2. ভুল খুঁজুন: একজন লিখলেন: “Apq গঠনে ধরন ২-এর নিয়ম (Apq → AprArq) অপ্রয়োজনীয়, কারণ প্রতিটি computation-এর প্রথম push শেষ চালে pop হয়। তাই BAL-এর normalised PDA থেকে শুধু ধরন ১ আর ৩ নিলেই চলে।” যুক্তির ভুল কোথায়, আর এই ছোট grammar কোন language দেয়?

    ভুল দাবি: “প্রথম push শেষ চালে pop হয়”। এটি শুধু ক্ষেত্র ১; ক্ষেত্র ২-এ প্রথম push মাঝপথে pop হয় আর stack আবার ফাঁকা হয়, যেমন “()()”-এ $-এর ওপরের অংশ প্রথম “()”-এর পরেই ফাঁকা। দাবি ৬.২-এর প্রমাণে এই ক্ষেত্রটিই ধরন ২ চায়।

    ধরন ২ বাদ দিলে নিয়ম থাকে A02 → A11, A11 → (A11) ∣ ε, আর language {(n)n : n ≥ 0}। Scratch-এ দৈর্ঘ্য ৮ পর্যন্ত ঠিক ε, (), (()), ((())), (((()))) এই ৫টি string এসেছে; “()()” নেই। অর্থাৎ grammar-টি L(P)-এর একটি উপসেট দেয়, সমান নয়।

  3. হিসাব ও trace: অংশ ৪-এর normalised PDA P2 (৭টি state, ৯টি চাল)। (ক) Apq গঠনে কয়টি variable, ধরন ২-এর কয়টি নিয়ম আর ধরন ৩-এর কয়টি? (খ) চালানোর আগে অনুমান করুন: “aab”-এর গ্রহণযোগ্য computation-এ কয়টি চাল, আর কোন state-গুলো দিয়ে যায়?

    (ক) 72 = ৪৯টি variable, 73 = ৩৪৩টি ধরন ২, ৭টি ধরন ৩; সঙ্গে ৭টি ধরন ১, মোট ৩৫৭টি, normalise_check.py-এর আউটপুটের মতো।

    (খ) ১০টি চাল: q1 (push $) → q2 (a: push a) → q2 (a: push a) → q2 (push X) → m1 (pop X) → q3 (b: pop a) → q3 (push X) → m2 (pop X) → qd (pop a) → qd (pop $) → qf. Stack: $, a$, aa$, Xaa$, aa$, a$, Xa$, a$, $, ε. Scratch-এর simulator ঠিক এই ক্রম দিয়েছে। শেষ stack ফাঁকা, শর্ত ২ অনুযায়ী।

  4. প্রমাণ: প্রমাণ করুন যে প্রতিটি regular language context-free: একটি DFA M = (Q, Σ, δ, q0, F) থেকে একটি PDA P বানান আর L(P) = L(M) দেখান।
    1. P = (Q, Σ, Γ, δ′, q0, F), Γ = {$} (ব্যবহার হবে না), আর প্রতিটি δ(q, a) = q′-এর জন্য δ′(q, a, ε) = {(q′, ε)}, অর্থাৎ চাল “a, ε → ε”। অন্য কোনো চাল নেই। — গঠন
    2. দাবি: |w|-এর ওপর induction-এ, (q0, w, ε) ⊢∗ (q, ε, ε) ⇔ δ̂(q0, w) = q. ভিত্তি w = ε: দুই দিকেই q = q0 (P-র কোনো ε-চাল নেই)। ধাপ w = va: P-র প্রতিটি চাল একটি চিহ্ন পড়ে আর stack ছোঁয় না, তাই শেষ চাল δ(q″, a) = q, যেখানে hypothesis-এ q″ = δ̂(q0, v). — induction, পর্ব ০৭-এর δ̂
    3. P-র computation deterministic আর সবসময় stack ফাঁকা, তাই w পড়ার পর একমাত্র configuration (δ̂(q0, w), ε, ε)। এটি F-এ ⇔ M w গ্রহণ করে। তাই L(P) = L(M), আর উপপাদ্য ১.১-এ L context-free. ∎ — দুই দিক একসঙ্গে

    বিকল্প: DFA থেকে সরাসরি একটি right-linear grammar (q → aq′ প্রতিটি δ(q, a) = q′-এর জন্য, আর q → ε প্রতিটি q ∈ F-এর জন্য), যা পর্ব ০৬-এর regular grammar.

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

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

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

  1. PDA-কে normalise করা: একটি accept state, শেষে ফাঁকা stack, প্রতিটি চালে ঠিক একটি push বা pop
  2. প্রতিটি state-জোড়া p, q-এর জন্য একটি variable Apq নেওয়া
  3. push আর pop-এর প্রতিটি মিলে-যাওয়া জোড়া থেকে Apq → aArsb নিয়ম লেখা
  4. সব p, q, r-এর জন্য Apq → AprArq আর সব p-এর জন্য App → ε যোগ করা
  5. Aq0,qaccept-কে start variable করে useless symbol মুছে ফেলা

Sipser-এর CFG → PDA গঠনে grammar S → aSb ∣ ε (terminal a, b) থেকে বানানো PDA-তে মোট কয়টি চাল (সংক্ষেপ-push একটি চাল ধরে)?

  • ৪
  • ৫
  • ৬
  • ৮

Grammar থেকে বানানো PDA (Sipser-এর গঠন) loop state-এ আছে আর stack-এর ওপরে একটি terminal a. PDA কী করে?

  • a-কে কোনো নিয়মের ডান দিক দিয়ে বদলায়
  • input-এর পরের চিহ্ন a হলে সেটি পড়ে আর a pop করে
  • সরাসরি accept state-এ চলে যায়
  • a-এর ওপরে start symbol আবার push করে

PDA থেকে CFG বানানোর (Apq গঠন) আগে PDA-কে normalise করা হয়। নিচের কোনটি normalisation-এর শর্ত নয়?

  • ঠিক একটি accept state থাকা
  • accept state-এ পৌঁছানোর আগে stack ফাঁকা হওয়া
  • প্রতিটি চালে ঠিক একটি push বা ঠিক একটি pop
  • PDA-টি deterministic হওয়া

৫টি state-এর একটি normalised PDA থেকে Apq গঠনে কয়টি variable আর কয়টি Apq → AprArq আকারের নিয়ম তৈরি হয়?

  • ২৫টি variable, ১২৫টি নিয়ম
  • ৫টি variable, ২৫টি নিয়ম
  • ২৫টি variable, ২৫টি নিয়ম
  • ১০টি variable, ১২৫টি নিয়ম

Apq-এর সঠিকতার প্রমাণে একটি computation ফাঁকা stack-এ p থেকে শুরু হয়ে ফাঁকা stack-এ q-তে শেষ হয়, আর মাঝপথে state r-এ stack একবার ফাঁকা হয়। কোন নিয়মটি ব্যবহার হয়?

  • Apq → aArsb
  • App → ε
  • Apq → AprArq
  • Apq → Aqp

PDA আর context-free grammar-এর সমতার উপপাদ্য থেকে নিচের কোন দাবিটি সত্য?

  • প্রতিটি context-free language কোনো deterministic PDA চেনে
  • একটি language context-free ঠিক তখন, যখন কোনো (nondeterministic) PDA সেটি চেনে
  • PDA থেকে Apq গঠনে পাওয়া grammar সবসময় unambiguous
  • CFG থেকে PDA বানাতে grammar-এর variable-এর সমান সংখ্যক state লাগে

শব্দকোষ

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

মনে রাখুন

  1. L context-free ⇔ কোনো PDA L চেনে; দুই দিকের রূপান্তরই algorithm দিয়ে, polynomial আকারে।
  2. CFG → PDA: ε, ε → S$; ε, A → w; a, a → ε; ε, $ → ε. PDA একটি leftmost derivation অনুকরণ করে: পড়া অংশ + stack = sentential form.
  3. Normalise: একটি accept state, শেষে ফাঁকা stack, প্রতিটি চালে ঠিক একটি push বা pop.
  4. Apq: ফাঁকা stack-এ p থেকে ফাঁকা stack-এ q; নিয়ম Apq → aArsb, Apq → AprArq, App → ε; প্রমাণ দুই দিকে induction.
  5. রূপান্তর language রক্ষা করে, ambiguity বা determinism নয়; রূপান্তরের পর brute force-এ language মেলানো অভ্যাস করুন।

পরের পর্বে: Deterministic PDA আর deterministic CFL: কোন language-এ অনুমান লাগে না, wcwR আর wwR-এর পার্থক্য, আর কেন parser-এর জগৎ এই শ্রেণির ওপর দাঁড়িয়ে।

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

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