# Question 22424: A Finite Valid Full-Input Run Proves Acceptance, Not Search Completeness

[Return to catalogue page 113](https://ocme.evemisslab.com/en/questions/page/113/)

[← Question derivation index](https://ocme.evemisslab.com/en/questions/) · [Original question batch](https://ocme.evemisslab.com/en/practice/batch-20261014-advance-20261110-r07-pushdown-automaton-foundations/#q-20261014-advance-20261110-r07-pushdown-automaton-0074)

This teaching derivation has second-context AI mathematical and bilingual semantic review, limited to the model and assumptions stated in this question. It has no human review or new Lean proof and does not promote the original question or MKO to Canonical truth.

R0043-22424 · q-20261014-advance-20261110-r07-pushdown-automaton-0074



## Original question and givens

Use the complete finite nondeterministic PDA: states=[push23, pop23, accept23], input_alphabet=[a23, b23], stack_alphabet=[Z23, A23], start_state=push23, bottom_symbol=Z23, final_states=[accept23], transitions=[[push23, a23, Z23, push23, [Z23, A23]], [push23, a23, A23, push23, [A23, A23]], [push23, b23, A23, pop23, []], [pop23, b23, A23, pop23, []], [push23, null, Z23, accept23, [Z23]], [pop23, null, Z23, accept23, [Z23]]]. Alphabets are unique and pairwise disjoint. Each transition is [from,input symbol or null,required top,to,replacement bottom-to-top]. null is epsilon and consumes no input. Configurations are [state,input position,stack] with bottom first and top last. Preserve the bottom marker and accept only after consuming the entire input in a final state, not by empty stack. Input=[a23, a23, a23, b23, b23, b23], supplied trace=[[push23, 0, [Z23]], [push23, 1, [Z23, A23]], [push23, 2, [Z23, A23, A23]], [push23, 3, [Z23, A23, A23, A23]], [pop23, 4, [Z23, A23, A23]], [pop23, 5, [Z23, A23]], [pop23, 6, [Z23]], [accept23, 6, [Z23]]]. Give (input, trace, transition_indices, valid_run, accepted, step_count, certificate).


- G001 — Use the complete finite nondeterministic PDA: states=[push23, pop23, accept23], input_alphabet=[a23, b23], stack_alphabet=[Z23, A23], start_state=push23, bottom_symbol=Z23, final_states=[accept23], transitions=[[push23, a23, Z23, push23, [Z23, A23]], [push23, a23, A23, push23, [A23, A23]], [push23, b23, A23, pop23, []], [pop23, b23, A23, pop23, []], [push23, null, Z23, accept23, [Z23]], [pop23, null, Z23, accept23, [Z23]]]. Alphabets are unique and pairwise disjoint. Each transition is [from,input symbol or null,required top,to,replacement bottom-to-top]. null is epsilon and consumes no input. Configurations are [state,input position,stack] with bottom first and top last. Preserve the bottom marker and accept only after consuming the entire input in a final state, not by empty stack. Input=[a23, a23, a23, b23, b23, b23], supplied trace=[[push23, 0, [Z23]], [push23, 1, [Z23, A23]], [push23, 2, [Z23, A23, A23]], [push23, 3, [Z23, A23, A23, A23]], [pop23, 4, [Z23, A23, A23]], [pop23, 5, [Z23, A23]], [pop23, 6, [Z23]], [accept23, 6, [Z23]]]. Give (input, trace, transition_indices, valid_run, accepted, step_count, certificate).





## Definition and scope

Use the original question domain, assumptions and cited MKO definitions. This item has second-context mathematical and bilingual review, with the model, answer and every arithmetic step independently recomputed from the original parameters; the source question remains a candidate.


- [mko-pushdown-automaton](https://ocme.evemisslab.com/en/mko/mko-pushdown-automaton/)





## Step-by-step derivation

S001 · impliesBefore

source operation=pda-accepting-run-witness;original snapshot and mathematics retained

After

explicit ordered source output fields=[input, trace, transition_indices, valid_run, accepted, step_count, certificate]

Conditions: none

Retain the historical interface marker and list ordered source fields without JavaScript.MVT fields come from the original mode,without padding or answer-shape inference.Tags and fixed No markers retain their claim scope.

Step identifiers and dependenciesRule: source_ordered_interface_explicit_without_javascript · Uses: G001





S002 · impliesBefore

ORIGINAL transition index=0;[from,input_or_null,required_top,to,replacement_bottom_to_top]=[push23, a23, Z23, push23, [Z23, A23]];bottom=Z23

After

states/input/stack symbols legal;null input consumes0;top=bottom requires replacement first bottom,otherwise replacement contains NO bottom;ORIGINAL transition position retained

Conditions: none

Check each original transition's state,input and stack roles without mixing alphabets.Null is epsilon,not an input symbol.The stack is bottom-first/top-last:pop one top then append the replacement in its original order.Apply the declared bottom guard,not an invented stronger convention.

Step identifiers and dependenciesRule: pda_EVERY_original_transition_roles_epsilon_bottom_guard · Uses: G001, S001





S003 · impliesBefore

ORIGINAL transition index=1;[from,input_or_null,required_top,to,replacement_bottom_to_top]=[push23, a23, A23, push23, [A23, A23]];bottom=Z23

After

states/input/stack symbols legal;null input consumes0;top=bottom requires replacement first bottom,otherwise replacement contains NO bottom;ORIGINAL transition position retained

Conditions: none

Check each original transition's state,input and stack roles without mixing alphabets.Null is epsilon,not an input symbol.The stack is bottom-first/top-last:pop one top then append the replacement in its original order.Apply the declared bottom guard,not an invented stronger convention.

Step identifiers and dependenciesRule: pda_EVERY_original_transition_roles_epsilon_bottom_guard · Uses: G001, S002





S004 · impliesBefore

ORIGINAL transition index=2;[from,input_or_null,required_top,to,replacement_bottom_to_top]=[push23, b23, A23, pop23, []];bottom=Z23

After

states/input/stack symbols legal;null input consumes0;top=bottom requires replacement first bottom,otherwise replacement contains NO bottom;ORIGINAL transition position retained

Conditions: none

Check each original transition's state,input and stack roles without mixing alphabets.Null is epsilon,not an input symbol.The stack is bottom-first/top-last:pop one top then append the replacement in its original order.Apply the declared bottom guard,not an invented stronger convention.

Step identifiers and dependenciesRule: pda_EVERY_original_transition_roles_epsilon_bottom_guard · Uses: G001, S003





S005 · impliesBefore

ORIGINAL transition index=3;[from,input_or_null,required_top,to,replacement_bottom_to_top]=[pop23, b23, A23, pop23, []];bottom=Z23

After

states/input/stack symbols legal;null input consumes0;top=bottom requires replacement first bottom,otherwise replacement contains NO bottom;ORIGINAL transition position retained

Conditions: none

Check each original transition's state,input and stack roles without mixing alphabets.Null is epsilon,not an input symbol.The stack is bottom-first/top-last:pop one top then append the replacement in its original order.Apply the declared bottom guard,not an invented stronger convention.

Step identifiers and dependenciesRule: pda_EVERY_original_transition_roles_epsilon_bottom_guard · Uses: G001, S004





S006 · impliesBefore

ORIGINAL transition index=4;[from,input_or_null,required_top,to,replacement_bottom_to_top]=[push23, null, Z23, accept23, [Z23]];bottom=Z23

After

states/input/stack symbols legal;null input consumes0;top=bottom requires replacement first bottom,otherwise replacement contains NO bottom;ORIGINAL transition position retained

Conditions: none

Check each original transition's state,input and stack roles without mixing alphabets.Null is epsilon,not an input symbol.The stack is bottom-first/top-last:pop one top then append the replacement in its original order.Apply the declared bottom guard,not an invented stronger convention.

Step identifiers and dependenciesRule: pda_EVERY_original_transition_roles_epsilon_bottom_guard · Uses: G001, S005





S007 · impliesBefore

ORIGINAL transition index=5;[from,input_or_null,required_top,to,replacement_bottom_to_top]=[pop23, null, Z23, accept23, [Z23]];bottom=Z23

After

states/input/stack symbols legal;null input consumes0;top=bottom requires replacement first bottom,otherwise replacement contains NO bottom;ORIGINAL transition position retained

Conditions: none

Check each original transition's state,input and stack roles without mixing alphabets.Null is epsilon,not an input symbol.The stack is bottom-first/top-last:pop one top then append the replacement in its original order.Apply the declared bottom guard,not an invented stronger convention.

Step identifiers and dependenciesRule: pda_EVERY_original_transition_roles_epsilon_bottom_guard · Uses: G001, S006





S008 · calculationBefore

PDA complete ORIGINAL transition count := sum(1, 1, 1, 1, 1, 1)

After

PDA complete ORIGINAL transition count = 6

Conditions: none

Substitute original roles,order and established intermediates exactly,without changing source bindings or using floating-point approximations.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S007





S009 · impliesBefore

ORIGINAL states=[push23, pop23, accept23],input alphabet=[a23, b23],stack alphabet=[Z23, A23];start=push23,bottom=Z23,final states=[accept23]

After

finite unique pairwise-disjoint alphabets qualified;transition count=6;acceptance convention FULL input in final state,NOT empty stack;qualification alone proves NO run,determinism or CFG equivalence

Conditions: none

A qualified complete definition gives no accepting run,determinism or CFG-equivalence proof.Acceptance may retain a nonempty stack,including its bottom,but requires full input consumption in a final state.

Step identifiers and dependenciesRule: pda_complete_definition_not_determinism_or_accepting_run · Uses: G001, S008





S010 · impliesBefore

ORIGINAL input=[a23, a23, a23, b23, b23, b23];ALL source configurations=[[push23, 0, [Z23]], [push23, 1, [Z23, A23]], [push23, 2, [Z23, A23, A23]], [push23, 3, [Z23, A23, A23, A23]], [pop23, 4, [Z23, A23, A23]], [pop23, 5, [Z23, A23]], [pop23, 6, [Z23]], [accept23, 6, [Z23]]];declared start=push23,bottom=Z23

After

first configuration EXACTLY=[push23, 0, [Z23]];all state/position/stack values legal;this is NOT yet a valid-run or acceptance certificate

Conditions: none

Require the exact initial state,position0 and one bottom.All configurations must be structurally legal before checking their transitions.A legal configuration list alone need not be a valid run.

Step identifiers and dependenciesRule: pda_trace_ALL_configurations_qualified_actual_initial_required · Uses: G001, S009





S011 · impliesBefore

ORIGINAL trace step=0;from=[push23, 0, [Z23]];to=[push23, 1, [Z23, A23]];actual input=[a23, a23, a23, b23, b23, b23]

After

ALL [ORIGINAL transition index,applied_result_or_null]=[[0, [push23, 1, [Z23, A23]]], [1, null], [2, null], [3, null], [4, [accept23, 0, [Z23]]], [5, null]];FIRST matching index=0

Conditions: none

Select the first original transition that actually yields the next configuration.Input-or-null determines consumption;replace only the top and preserve replacement order.On failure retain prior partial indices;a later final state cannot repair a bad step.

Step identifiers and dependenciesRule: pda_each_actual_stack_update_FIRST_original_transition · Uses: G001, S010





S012 · impliesBefore

ORIGINAL trace step=1;from=[push23, 1, [Z23, A23]];to=[push23, 2, [Z23, A23, A23]];actual input=[a23, a23, a23, b23, b23, b23]

After

ALL [ORIGINAL transition index,applied_result_or_null]=[[0, null], [1, [push23, 2, [Z23, A23, A23]]], [2, null], [3, null], [4, null], [5, null]];FIRST matching index=1

Conditions: none

Select the first original transition that actually yields the next configuration.Input-or-null determines consumption;replace only the top and preserve replacement order.On failure retain prior partial indices;a later final state cannot repair a bad step.

Step identifiers and dependenciesRule: pda_each_actual_stack_update_FIRST_original_transition · Uses: G001, S011





S013 · impliesBefore

ORIGINAL trace step=2;from=[push23, 2, [Z23, A23, A23]];to=[push23, 3, [Z23, A23, A23, A23]];actual input=[a23, a23, a23, b23, b23, b23]

After

ALL [ORIGINAL transition index,applied_result_or_null]=[[0, null], [1, [push23, 3, [Z23, A23, A23, A23]]], [2, null], [3, null], [4, null], [5, null]];FIRST matching index=1

Conditions: none

Select the first original transition that actually yields the next configuration.Input-or-null determines consumption;replace only the top and preserve replacement order.On failure retain prior partial indices;a later final state cannot repair a bad step.

Step identifiers and dependenciesRule: pda_each_actual_stack_update_FIRST_original_transition · Uses: G001, S012





S014 · impliesBefore

ORIGINAL trace step=3;from=[push23, 3, [Z23, A23, A23, A23]];to=[pop23, 4, [Z23, A23, A23]];actual input=[a23, a23, a23, b23, b23, b23]

After

ALL [ORIGINAL transition index,applied_result_or_null]=[[0, null], [1, null], [2, [pop23, 4, [Z23, A23, A23]]], [3, null], [4, null], [5, null]];FIRST matching index=2

Conditions: none

Select the first original transition that actually yields the next configuration.Input-or-null determines consumption;replace only the top and preserve replacement order.On failure retain prior partial indices;a later final state cannot repair a bad step.

Step identifiers and dependenciesRule: pda_each_actual_stack_update_FIRST_original_transition · Uses: G001, S013





S015 · impliesBefore

ORIGINAL trace step=4;from=[pop23, 4, [Z23, A23, A23]];to=[pop23, 5, [Z23, A23]];actual input=[a23, a23, a23, b23, b23, b23]

After

ALL [ORIGINAL transition index,applied_result_or_null]=[[0, null], [1, null], [2, null], [3, [pop23, 5, [Z23, A23]]], [4, null], [5, null]];FIRST matching index=3

Conditions: none

Select the first original transition that actually yields the next configuration.Input-or-null determines consumption;replace only the top and preserve replacement order.On failure retain prior partial indices;a later final state cannot repair a bad step.

Step identifiers and dependenciesRule: pda_each_actual_stack_update_FIRST_original_transition · Uses: G001, S014





S016 · impliesBefore

ORIGINAL trace step=5;from=[pop23, 5, [Z23, A23]];to=[pop23, 6, [Z23]];actual input=[a23, a23, a23, b23, b23, b23]

After

ALL [ORIGINAL transition index,applied_result_or_null]=[[0, null], [1, null], [2, null], [3, [pop23, 6, [Z23]]], [4, null], [5, null]];FIRST matching index=3

Conditions: none

Select the first original transition that actually yields the next configuration.Input-or-null determines consumption;replace only the top and preserve replacement order.On failure retain prior partial indices;a later final state cannot repair a bad step.

Step identifiers and dependenciesRule: pda_each_actual_stack_update_FIRST_original_transition · Uses: G001, S015





S017 · impliesBefore

ORIGINAL trace step=6;from=[pop23, 6, [Z23]];to=[accept23, 6, [Z23]];actual input=[a23, a23, a23, b23, b23, b23]

After

ALL [ORIGINAL transition index,applied_result_or_null]=[[0, null], [1, null], [2, null], [3, null], [4, null], [5, [accept23, 6, [Z23]]]];FIRST matching index=5

Conditions: none

Select the first original transition that actually yields the next configuration.Input-or-null determines consumption;replace only the top and preserve replacement order.On failure retain prior partial indices;a later final state cannot repair a bad step.

Step identifiers and dependenciesRule: pda_each_actual_stack_update_FIRST_original_transition · Uses: G001, S016





S018 · impliesBefore

ORIGINAL last config=[accept23, 6, [Z23]];input length=6;matched prior indices=[0, 1, 1, 2, 3, 3, 5]

After

valid_run=Yes;FULL input consumed=Yes;last state final=Yes;accepted=Yes;residual stack may be NONEMPTY

Conditions: none

Acceptance conjoins a valid run,full input consumption and a final state.A residual bottom or other stack symbols may remain.Validity and acceptance differ;the tag cannot turn a false flag into a certificate.

Step identifiers and dependenciesRule: pda_run_validity_full_consumption_final_state_SEPARATE · Uses: G001, S017





S019 · calculationBefore

PDA ORIGINAL full trace length minus one := sub(8, 1)

After

PDA ORIGINAL full trace length minus one = 7

Conditions: none

Substitute original roles,order and established intermediates exactly,without changing source bindings or using floating-point approximations.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S018





S020 · impliesBefore

ORIGINAL trace configuration count=8;actual matched transition-index count=7;accepted=Yes

After

SOURCE step_count=ORIGINAL trace.length-1=7;does NOT substitute partial matched count;acceptedTrue is a finite witness,not search completeness

Conditions: none

The source step count uses the whole supplied trace length,even on a partial failure.Only accepted=True supplies the finite accepting-run witness;it proves neither all runs,shortest length nor search completeness.

Step identifiers and dependenciesRule: pda_original_step_count_not_partial_matched_count · Uses: G001, S019









## Reverse checks


- S020 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S019 · premise_and_result_audit — Recompute PDA ORIGINAL full trace length minus one with exact rational arithmetic, not rounded decimals.
- S018 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S017 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S016 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S015 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S014 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S013 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S012 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S011 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S010 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S009 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S008 · premise_and_result_audit — Recompute PDA complete ORIGINAL transition count with exact rational arithmetic, not rounded decimals.
- S007 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S006 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S005 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S004 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S003 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S002 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S001 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.





## Result

([a23, a23, a23, b23, b23, b23], [[push23, 0, [Z23]], [push23, 1, [Z23, A23]], [push23, 2, [Z23, A23, A23]], [push23, 3, [Z23, A23, A23, A23]], [pop23, 4, [Z23, A23, A23]], [pop23, 5, [Z23, A23]], [pop23, 6, [Z23]], [accept23, 6, [Z23]]], [0, 1, 1, 2, 3, 3, 5], Yes, Yes, 7, finite_full_run_witness_proves_acceptance_under_final_state_convention)

The full substitutions and premise checks give the original answer; source identity,format and status are unchanged.





## This question review and source binding

Review date: 2026-10-26

Original questions, answers, step expressions, numeric ASTs and historical records are retained. Source candidate labels remain historical and are not overwritten as formal proof.

Source hashes and review receipts
- input commit: 0f7be61e2c22317a4075561dc822c87d881a50db
- original question SHA-256: 2b8c5aeaf4ececa97063d2f5acd2a8c410972fb98b1654aea05578355e2c7123
- candidate record SHA-256: ba787ecf171fd47ec685c9ff4b1580efc667da4f1244b75e886d5b0513c8f61b
- semantic review receipt SHA-256: 49cf6ec60211c92d1c0c302663af4d44479635dc8181fb61a20c3374288e21c5
- question-first witness SHA-256: 10fd25b4643e5ff12753daceaa61f9f2499bf381f65ef96e9d21185c7c0d0c5e
- Lean: NOT_RUN · human review: NOT_PERFORMED

[Same-source full JSON](https://ocme.evemisslab.com/data/question-derivations/questions/q-20261014-advance-20261110-r07-pushdown-automaton-0074.json)