上下文無關文法

數學敘述

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。

代表公式（精確 TeX）

G(N,T)

成立條件

• nonterminal與terminal alphabets finite、unique且disjoint。
• 每條production lhs恰一nonterminal，rhs symbols合法。

符號作用域

• G — 上下文無關文法
• N — 非終結符字母表
• T — 終結符字母表

直觀、定義與常見誤解

grammar qualification與derivation分開。

terminal-only final word是membership witness。

bounded failure不是nonmembership proof。

有限深度找不到derivation便稱word不在language，或混同empty language與epsilon。

已採用的推導導讀

原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。

前置知識

• 抽象計算模型 — grammar execution model。
• 集合 — alphabets與production set。
• 數列 — finite strings與derivations。

驗證界線

本輪不宣稱ambiguity、regularity或CFG-PDA equivalence。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。

下一個義務

加入pushdown automata與parsing。

同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。