##### 上下文无关语法 - 上下文无关语法 - **上下文无关语法**是[[上下文无关语言]]的[[形式语法]] $G = (V, \Sigma, P, S)$, 规则集 $P$ 中每条产生规则的左侧必须是单个非终结符, 这意味着无论这个非终结符出现在句子中的哪个位置, 它都可以独立[[递归]]地被规则替换, 而不依赖于它的上下文 - $A \to \gamma$ - $A \in V$ 是单个非终结符 - $\gamma \in (V \cup \Sigma)^*$ 是由终结符和非终结符组成的字符串 >[!example]- 上下文无关语法 > - 语言 $B = \{0^n 1^n \mid n \geq 0\}$ > - 字符串由 $n$ 个 $0$ 后接 $n$ 个 $1$ 构成. 例如 $\varepsilon$, $01$, $0011$ 属于, 而 $0$, $001$ 不属于 > - 正则语法 > - 非终结符 $V = \{ S \}$ > - 终结符 $\Sigma = \{ 0, 1 \}$ > - 产生规则 $P = \{S \to 0S1, S \to \varepsilon\}$ > - 开始符号 $S\in V$