上下文无关语法
英文: Context-free grammars, CFG.
替换规则:
\[
S \rightarrow 0S1 \\
S \rightarrow R \\
R \rightarrow \varepsilon
\]
缩写:
\[
S \rightarrow 0S1 | R \\
R \rightarrow \varepsilon
\]
\[
L(G_1) = \{ 0^k1^k \mid k \geq 0 \}
\]
正式定义
上下文无关语法(以下简称 CFG)是一个四元组 \((V, \Sigma, R, S)\), 其中:
- \(V\) 是变量的有限集.
- \(\Sigma\) 是终结字符的有限集.
- \(R: V \rightarrow (V \cup \Sigma)^*\) 是规则的有限集.
- $S \in Vf $ 是初始变量.
对于 \(u, v \in (V \cup \Sigma)^*\):
- \(u \Rightarrow v\): 可以通过一次替换, 从 \(u\) 变成 \(v\).
- \(u \stackrel{*}{\Rightarrow} v\): 可以通过多次替换, 从 \(u\) 变成 \(v\), 即 \(u \Rightarrow u_1 \Rightarrow u_2 \Rightarrow \dots \Rightarrow u_k \Rightarrow v\).
如果对于某些 CFG \(G\) 来说, \(A = L(G)\), 则 \(A\) 是上下文无关语言 (context-free language, CFL).
\[
L(G) = \{ w \mid w \in \Sigma^* \text{ and } S \stackrel{*}{\Rightarrow} w\}
\]