ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-09-12

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Building a PDA for ${a^{n} b^{n} : n \geq 0}$ from the standard grammar

Example

Start with the grammar $S \to a S b ∣ ε .$

The standard grammar-to-PDA construction produces a one-state PDA whose initial stack symbol is $S$ , with $ε$ -moves replacing $S$ by $a S b$ or $ε$ , and with input-reading moves that match $a$ or $b$ against the top terminal on the stack.

Facts & Assumptions

Given: The grammar $S \to a S b ∣ ε$ for ${a^{n} b^{n} : n \geq 0}$ .

[L1]

By Every context-free grammar has an equivalent PDA, the standard pop/expand construction turns a CFG into an equivalent PDA that accepts by empty stack.

Verification

technique · direct

1.1

On input $a a b b$ , the unread-input/stack pairs may evolve as $(a a b b, S) \to (a a b b, a S b) \to (a b b, S b) \to (a b b, a S b b) \to (b b, S b b) \to (b b, b b) \to (b, b) \to (ε, ε) .$ The four input-consuming moves pop the displayed top terminal, while the three other moves expand $S$ by $a S b$ , expand it once more, and finally replace it by $ε$ .

given

2.1

The same pattern works for every word $a^{n} b^{n}$ : repeat $S \to a S b$ and immediately read and pop the new top $a$ , exactly $n$ times; then use $S \to ε$ and read and pop the remaining $n$ symbols $b$ . Therefore the constructed PDA recognizes ${a^{n} b^{n} : n \geq 0}$ .

L1step 1.1

3.1

This is the standard grammar-to-PDA construction from [L1] on a concrete language.

L1step 2.1∎

Depends on

Every context-free grammar has an equivalent PDA

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

5 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Jean Gallier and Jocelyn Quaintance, Introduction to the Theory of Computation: Some Notes for CIS511 (standard reference, not scraped)

Building a PDA for {anbn:n≥0}{anbn:n≥0} from the standard grammar