# 上下文無關文法

CFG由有限且不交的nonterminals、terminals、start與單一nonterminal左側的finite productions生成語言。

mko-context-free-grammar · definition · v0.10.0



## 數學敘述

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。





## 已採用的推導導讀

[CFG的完整production與推導witness](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-context-free-grammar-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [抽象計算模型](https://ocme.evemisslab.com/zh-Hant/mko/mko-computational-model/) — grammar execution model。
- [集合](https://ocme.evemisslab.com/zh-Hant/mko/mko-set/) — alphabets與production set。
- [數列](https://ocme.evemisslab.com/zh-Hant/mko/mko-sequence/) — finite strings與derivations。





## 驗證界線

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

not_formalized

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





## 下一個義務

加入pushdown automata與parsing。





## 同源結構化資料

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

[原始 MKO JSON](https://ocme.evemisslab.com/data/mko/context-free-grammar.json) · [純文字 Markdown](https://ocme.evemisslab.com/zh-Hant/mko/mko-context-free-grammar/index.md)