A CFG production list and derivation witness

Goal and scope

The grammar S to aSb or epsilon has finite derivation witnesses for aaabbb and epsilon.

Grammar qualification and specified-word membership are separate; no regularity or CFG-PDA equivalence claim.

Givens and symbols

• calc

• G1 — N={S}, terminals {a,b}, start S; all productions are S to aSb and S to epsilon; epsilon is the empty rhs.

• N,\Sigma — nonterminal and terminal sets
• P — complete production set

Rules and sources

• calc · prerequisite — Assume finite sets, finite strings and indices, stepwise function updates and induction on natural numbers; epsilon denotes the length-zero word.
• mko_definition · cited — Each right side is a finite string over terminal and nonterminal symbols, with the epsilon convention explicit. A derivation is a finite production sequence. The generated language contains only terminal-only words derivable from the start. The empty language is not a language containing epsilon. A derivation witness proves membership, but bounded-search failure does not prove nonmembership. Unambiguity, regularity and CFG-PDA equivalence do not follow automatically. · mko-context-free-grammar

Main derivation

N=\{S\},\quad\Sigma=\{a,b\}

N\cap\Sigma=\varnothing,\quad S\in N

P=\{S\to aSb,\ S\to\varepsilon\}

\text{each lhs is one nonterminal; every rhs symbol is legal}

S

aSb

aSb

aaSbb

aaSbb

aaaSbbb

aaaSbbb

aaabbb

S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aaaSbbb\Rightarrow aaabbb

aaabbb\in L(G)

S\Rightarrow\varepsilon

\varepsilon\in L(G),\quad L(G)\ne\varnothing

\text{search depth }2

aaabbb\text{ not found by depth 2, but has the depth-4 witness above}

Substeps and lemmas

No substeps in this guide.

Reverse audits

• S09 · premise_audit · G1, S03, S04, S05, S06, S07 — The grammar's explicit witness suffices without invoking CFG-PDA equivalence.
• S08 · premise_audit · G1, S02, S07 — Epsilon is an element of the language, whereas the empty language has no elements.
• S07 · premise_audit · G1, S03, S04, S05, S06 — This witness certifies this word only, not unambiguity.
• S06 · premise_audit · G1, S02, S05 — An epsilon replacement has length zero and does not output a letter called epsilon.
• S05 · premise_audit · G1, S02, S04 — Each step rewrites the actual single S rather than replacing an arbitrary whole word.
• S04 · premise_audit · G1, S02, S03 — A previously produced terminal a cannot be rewritten as S.
• S03 · premise_audit · G1, S02 — A nonterminal remains, so this is not a terminal-only endpoint.
• S02 · premise_audit · G1, S01 — Grammar qualification does not imply every word is derivable.
• S01 · premise_audit · G1 — S is not terminal; a sentential form containing S is not a terminal word.

Error controls and negative controls

Terminal-only endpoint

A sentential form containing S is not an accepted terminal word.

Production location

Rewrite only a valid lhs occurrence and preserve other symbols' order.

• aaSbb is already a terminal word in the language. → reject — It still contains nonterminal S.
• Deriving epsilon makes the language empty. → reject — Epsilon is already an element, and aaabbb is another.
• No hit at depth 2 rejects aaabbb. → reject — The explicit depth-four derivation certifies membership.

Result and limitations

The grammar S to aSb or epsilon has finite derivation witnesses for aaabbb and epsilon.

Verification and source binding

0 declared checks for this guide; only the listed expressions are covered.

• source commit: b1b2f1dcf8c50d67a93fe52d95f8eef7b3abba9f
• adopted source SHA-256: a8dca2b816c0c085ecbc6756e9970e00e0953a31ba8d0a4e35d497a9265aa220
• original source SHA-256: a8dca2b816c0c085ecbc6756e9970e00e0953a31ba8d0a4e35d497a9265aa220
• Lean: NOT_RUN · independent AI: SCOPED_LEAD_AND_BILINGUAL_CONTEXT_REVIEW

Same-source full JSON (formulas, ASTs, controls and revision log)