##### 正则语法 - 正则语法 - **正则语法**是[[正则语言]]的[[形式语法]] $G = (V, \Sigma, P, S)$, 规则集 $P$ 中每条产生规则右侧最多只能有一个非终结符, 且位置固定在最左或最右, 以下是[[递归]]的右正则产生规则 - $A\to aB$, $A\to a$ - $A,B \in V$ 是非终结符 - $a \in \Sigma$ 是终结符 >[!example]- 正则语法 > - 语言 $L = \{ a^n b \mid n \geq 0 \}$ > - 这个语言包含字符串 `b`, `ab`, `aab`, `aaab` 等 > - 正则语法 > - 非终结符 $V = \{ S \}$ > - 终结符 $\Sigma = \{ a, b \}$ > - 产生规则 $P = \{S \to aS, S \to b\}$ > - 开始符号 $S\in V$