CFG的完整production與推導witness

目標與範圍

grammar S→aSb或ε具有aaabbb與ε的有限推導witness。

grammar合法性與指定word membership分開，不宣稱regularity或CFG-PDA等價。

已知條件與符號

• calc

• G1 — N={S}，Σ={a,b}，start S；完整production P={S→aSb,S→ε}；ε為空rhs。

• N,\Sigma — nonterminal與terminal集合
• P — 完整production集合

規則與來源

• calc · prerequisite — 假設有限集合、有限字串與索引、逐步函數更新及自然數歸納；ε表示長度0字串。
• mko_definition · cited — rhs為terminal/nonterminal finite strings並明示epsilon convention。derivation是finite production sequence；language只含start導出的terminal-only words。空語言不等於含epsilon。witness證membership，但bounded search failure不證nonmembership，亦不自動推unambiguous、regular或PDA equivalence。 · mko-context-free-grammar

逐步主鏈

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}

局部子步與引理

本稿無局部子步。

逐步反向審查

• S09 · premise_audit · G1, S03, S04, S05, S06, S07 — 只有本grammar的完整witness足以接受，不借CFG-PDA等價。
• S08 · premise_audit · G1, S02, S07 — ε是集合的一個元素，∅則沒有元素。
• S07 · premise_audit · G1, S03, S04, S05, S06 — 此witness只證這個word，未自動證grammar無歧義。
• S06 · premise_audit · G1, S02, S05 — ε替換長度0，因此不輸出字母epsilon。
• S05 · premise_audit · G1, S02, S04 — 每步lhs是實際存在的單一S，沒有跳步換整個word。
• S04 · premise_audit · G1, S02, S03 — 不能同時把前面的terminal a改成S。
• S03 · premise_audit · G1, S02 — 此時仍有nonterminal，尚非terminal-only結束。
• S02 · premise_audit · G1, S01 — grammar資格不等於任意word都可導出。
• S01 · premise_audit · G1 — S不是terminal，含S的中途字不是language member。

錯誤控制與反例

終點純terminal

中途含S的sentential form不算接受word。

production位置

每步只替換合法lhs出現處，保持其他symbols順序。

• aaSbb已是language中的terminal word。 → reject — 它仍含nonterminal S。
• 因可導出ε，language是空集。 → reject — ε本身已是一個元素，且aaabbb亦在內。
• depth2未命中aaabbb證拒絕。 → reject — 上面depth4完整推導認證membership。

結論與限制

grammar S→aSb或ε具有aaabbb與ε的有限推導witness。

驗證及來源綁定

0 個本稿宣告算術檢查；只支持所列算式。

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

同源完整 JSON（含公式、AST、反控制與修訂記錄）