# Pushdown automaton

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

A nondeterministic PDA uses finite control, input and stack transitions; this slice accepts only after reading the whole input in a final state.

mko-pushdown-automaton · definition · v0.10.0



## Mathematical statement

The PDA tuple specifies finite states Q, input/stack alphabets, start q0, bottom Z, final states and a transition relation. Each transition is [from state,input symbol or null,required top,to state,replacement bottom-to-top]. null denotes epsilon and consumes no input. A stack is bottom-first/top-last and its bottom may not underflow. An acceptance witness is a finite run consuming all input and ending in a final state. Do not substitute empty-stack acceptance. Bounded-search failure does not prove rejection; neither CFG equivalence nor determinism follows automatically.





## Representative formula (exact TeX)

P(Q,Z)





## Assumptions


- States and input/stack alphabets are finite, unique and pairwise disjoint.
- A configuration is [state,input position,stack], bottom first and top last; null transitions do not advance the input position, and bottom transitions preserve the bottom.





## Symbol scope


- P — pushdown automaton
- Q — finite state set
- Z — bottom stack marker





## Intuition, definition, and misconceptions

Fix acceptance as full input consumption plus final state.

Audit every transition field, input consumption and bottom-to-top replacement.

A finite run proves acceptance; a premature final state does not, and a bounded no-hit does not prove nonmembership.

Do not let epsilon consume input, pop the bottom, conflate empty-stack/final-state acceptance or call an insufficient search depth a rejection proof.





## Adopted derivation guide

[A bottom-first PDA run accepting aabb](https://ocme.evemisslab.com/en/derivations/derivation-mko-pushdown-automaton-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Abstract computational model](https://ocme.evemisslab.com/en/mko/mko-computational-model/) — The transition model is finite.
- [Deterministic finite automaton](https://ocme.evemisslab.com/en/mko/mko-finite-automaton/) — Control states are finite.
- [Sequence](https://ocme.evemisslab.com/en/mko/mko-sequence/) — Input, stacks and runs are finite sequences.
- [Context-free grammar](https://ocme.evemisslab.com/en/mko/mko-context-free-grammar/) — Language context is provided without an equivalence claim.





## Verification boundary

This slice makes no general CFG-PDA conversion, determinism or language-nonmembership claim.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.





## Next obligation

Add CFG-PDA equivalence and the pumping lemma.





## Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/pushdown-automaton.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-pushdown-automaton/index.md)