Context-Free Grammar ও Pushdown Automata — Stack যখন Memory

Pushdown Automaton — DFA + একটা Stack

আনুষ্ঠানিক সংজ্ঞা — একটা 6-টুপল (কনভেনশনভেদে 7-টুপল, stack bottom marker আলাদা রাখলে):

$P = (Q, \Sigma, \Gamma, \delta, q_0, F)$

উপাদান	অর্থ
Q	State-এর সসীম সেট (DFA-র মতোই)
Σ	Input alphabet
Γ	Stack alphabet (input alphabet থেকে আলাদা হতে পারে)
δ	Q × (Σ∪{ε}) × Γ → 𝒫(Q × Γ*) — state + ঐচ্ছিক input + stack-top দেখে নতুন state ও stack-এ কী push হবে তা ঠিক করে
q0	Start state
F	Accepting state-এর সেট

δ-র টাইপটা মনোযোগ দিয়ে দেখুন — এটা DFA-র δ-র চেয়ে অনেক বেশি কিছু এনকোড করে: প্রতিটা transition stack-এর top দেখতে পারে (pop-এর মতো) আর নতুন symbol push করতে পারে, এবং input না পড়েও (ε) transition নিতে পারে। এই কারণেই PDA স্বভাবতই nondeterministic — NFA-র মতোই, “কোনো একটা path accept করলেই” গ্রহণ। (Deterministic PDA-ও সংজ্ঞায়িত করা যায়, কিন্তু — NFA/DFA-র বিপরীতে — deterministic PDA strictly কম শক্তিশালী সাধারণ PDA-র চেয়ে; এই অসামঞ্জস্যটাই compilers/parsing-এ LR(k) parser-এর সীমাবদ্ধতার তাত্ত্বিক শিকড়।)

একটা সম্পূর্ণ PDA — {0ⁿ1ⁿ : n ≥ 0}

states: {q_push, q_pop, q_accept}
stack alphabet: {Z, 0}    (Z = bottom marker)

δ(q_push, 0, X)  = {(q_push, 0X)}     — যেকোনো 0 পড়লে push, state একই
δ(q_push, 1, 0)  = {(q_pop, ε)}       — প্রথম 1 দেখলে pop শুরু, একটা 0 বাদ দিন
δ(q_pop, 1, 0)   = {(q_pop, ε)}       — প্রতিটা 1-এ একটা 0 pop
δ(q_pop, ε, Z)   = {(q_accept, Z)}    — ইনপুট শেষ, stack-এ শুধু Z বাকি থাকলে accept

start: q_push,  initial stack: Z,  F = {q_accept}

"000111" ইনপুটে ট্রেস:

state    বাকি ইনপুট   stack (top বামে)
q_push   000111       Z
q_push   00111        0Z
q_push   0111         00Z
q_push   111           000Z
q_pop    11            00Z      (প্রথম 1 — pop)
q_pop    1              0Z      (দ্বিতীয় 1 — pop)
q_pop    ε               Z      (তৃতীয় 1 — pop, ঠিক সমান!)
q_accept ε               Z      (ε-move, stack-এ শুধু Z, accept)

Push-ধাপে stack-এর গভীরতাই “কতগুলো 0 দেখেছি”-র গণনা — ঠিক সেই memory যেটা DFA-র কখনো ছিল না (গত লেসনের pigeonhole যুক্তি মনে করুন)। Stack unbounded, তাই যেকোনো n-এর জন্য কাজ করে।

CFG ↔ PDA সমতুল্যতা

উপপাদ্য: একটা ভাষা context-free (কোনো CFG দিয়ে generate হয়) যদি এবং কেবল যদি কোনো PDA সেটা accept করে।

CFG → PDA (গঠনমূলক, সহজ দিক): যেকোনো CFG থেকে একটা standard PDA বানানো যায় যা leftmost derivation-কে সরাসরি simulate করে —

১. Stack-এ start symbol S পুশ করে শুরু করুন
২. যতক্ষণ stack-এর top একটা nonterminal A:
     grammar-এর যেকোনো rule A → γ nondeterministically বেছে নিন,
     A pop করুন, γ push করুন (উল্টো ক্রমে, যাতে γ-র প্রথম symbol top-এ থাকে)
৩. যতক্ষণ stack-এর top একটা terminal a:
     ইনপুট থেকে a পড়ুন, মিললে pop করুন, না মিললে reject
৪. Stack খালি ও ইনপুট শেষ হলে accept

এই construction-এ NFA-র nondeterminism ঠিক grammar-এর “কোন rule বাছব” সিদ্ধান্তের প্রতিরূপ — PDA আসলে সব সম্ভাব্য derivation “একসাথে” (conceptually) অনুসরণ করে, যেকোনো একটা successfully ইনপুট মিলিয়ে দিলেই accept।

PDA → CFG (কঠিন দিক): সম্ভব, কিন্তু construction জটিল — প্রতিটা PDA state-transition-stack-symbol triple-এর জন্য একটা nonterminal বানিয়ে stack-এর push/pop-কে grammar rule-এ এনকোড করা হয়। এই লেসনের সীমার বাইরে বিস্তারিত, কিন্তু অস্তিত্ব প্রমাণিত — এটাই যথেষ্ট সমতুল্যতা প্রতিষ্ঠা করতে।

1. Regular (Type 3)Regex ↔ NFA ↔ DFA — সসীম state, কোনো memory নেই
2. Context-Free (Type 2)CFG ↔ PDA — সসীম state + ১টা unbounded stack
3. সমতুল্যতার প্রমাণের প্যাটার্ন একইদুই স্তরেই: generator (grammar/regex) ↔ recognizer (automaton), দুই দিকেই গঠনমূলক রূপান্তর

↓ নিচের দিকে — বেশি concrete

Recursive descent parser — একটা লুকানো PDA

এখানেই এই লেসনের সবচেয়ে সুন্দর সংযোগ। compilers/parsing-এ আপনি লিখেছিলেন এমন কিছু:

def parse_E():
    parse_T()
    while peek() == '+':
        consume('+')
        parse_T()

def parse_T():
    parse_F()
    while peek() == '*':
        consume('*')
        parse_F()

এখানে কোনো explicit stack variable নেই — অথচ এটা একটা PDA। কীভাবে? প্রতিটা function call push — call stack-এ একটা নতুন frame যোগ হয়, যা বলে “আমরা এখন E বা T বা F পার্স করছি, আর শেষ হলে কোথায় ফিরে যাব”। প্রতিটা function return pop — সেই frame সরে যায়। Function call stack-টাই আক্ষরিক অর্থে PDA-র Γ*।

এই অন্তর্দৃষ্টিটা ব্যাখ্যা করে কেন recursive descent parser স্বাভাবিকভাবে নেস্টেড expression সামলায় কোনো বিশেষ কৌশল ছাড়াই — নেস্টিং-এর “গভীরতা” মনে রাখাটা programming language-এর নিজস্ব call stack ব্যবস্থাপনা থেকেই বিনামূল্যে পাওয়া যায়। এটাই আবার mathematics/induction-এর সেই থিমের প্রতিফলন — recursion আর stack-based computation একই জিনিসের দুই মুখ।