Unknown
theory of computation में, theoretical computer science की एक branch है , एक Pushdown Automata (PDA) एक प्रकार का Automata है जो एक stack को Employed करता है।
machines द्वारा computation किया जा सकता है, इसके लिये Pushdown Automata का उपयोग किया जाता है
वे finite-state machines से अधिक capable हैं लेकिन Turing machines की तुलना में कम capable हैं । Deterministic pushdown automata सभी deterministic context-free languages को पहचान सकता है, जबकि nondeterministic वाले सभी context-free languages को पहचान सकते हैं
" Pushdown" शब्द इस fact को refers करता है कि एक cafeteria में tray dispenser की तरह Stack को " Pushdown" माना जा सकता है, क्योंकि operation कभी भी deeper elements के अलावा अन्य element पर काम नहीं करते हैं। stack automaton Pushdown Automata की तुलना में language के strictly से larger set को पहचान सकता है। एक nested stack automaton full access allow करता है, और केवल एक finite symbols के बजाय पूरे sub-stacks होने के लिए stacked values को भी अनुमति देता है।
Formal definition
Pushdown Automata को 7 tuple का उपयोग कर define किया जाता है
M = (Q , ∑ , Γ , δ , q0 , Z , F)