Pushdown automaton

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

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 — The transition model is finite.
• Deterministic finite automaton — Control states are finite.
• Sequence — Input, stacks and runs are finite sequences.
• 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.