Pushdown Automaton
পুশডাউন অটোমাটন
একটা DFA/NFA-তে একটা unbounded stack (LIFO) যোগ করলে যা পাওয়া যায় — context-free grammar-এর সমতুল্য শক্তির automaton, যা 0ⁿ1ⁿ বা balanced parentheses-এর মতো নেস্টেড ভাষা চিনতে পারে।
also: PDA
আনুষ্ঠানিক সংজ্ঞা: P = (Q, Σ, Γ, δ, q0, F) যেখানে
δ: Q × (Σ∪{ε}) × Γ → 𝒫(Q × Γ*) — প্রতিটা transition stack-এর
top দেখে (pop-এর সমতুল্য) আর নতুন symbol push করতে পারে।
CFG ↔ PDA সমতুল্যতা: যেকোনো CFG-র জন্য একটা PDA বানানো যায় যা leftmost derivation simulate করে (stack-এ grammar symbol রাখে, nonterminal দেখলে rule apply করে expand করে, terminal দেখলে input-এর সাথে মিলিয়ে pop করে)। উল্টো দিকও (PDA→CFG) প্রমাণিত, জটিলতর।
লুকানো PDA — recursive descent parser। Function call stack-ই
আক্ষরিক অর্থে PDA-র Γ*; প্রতিটা call push, প্রতিটা return pop।
তাই compilers/parsing-এর recursive descent parser-এর maximum
nesting depth বাস্তব call stack memory দিয়ে সীমাবদ্ধ — deeply
nested malicious input দিয়ে stack overflow একটা পরিচিত DoS vector।
সীমা: একটামাত্র LIFO stack বলে দুইটা স্বাধীন matching (0ⁿ1ⁿ2ⁿ-এর
মতো) সামলাতে পারে না — সেটার জন্য linear-bounded automaton লাগে,
CFL pumping lemma দিয়ে প্রমাণযোগ্য।