推导（Derivations）和规约（Reductions）

给定文法 $G=(V_T, V_N, P, S)$, 如果 $\alpha \to \beta \in P$ ,那么可以将符号串 $\gamma \alpha \delta$ 中的 $\alpha$ 替换为 $\beta$ ，就是将 $\gamma \alpha \delta$ 重写（rewrite） 为 $\gamma \beta \delta$ ,记作 $\gamma \alpha \delta \Rightarrow \gamma \beta \delta$ 。此时，称文法中的符号串 $\gamma \alpha \delta$ 直接推导（directly derive） 出 $\gamma \beta \delta$

简而言之，就是用产生式的右部替换产生式的左部。

如果 $\alpha_0 \Rightarrow \alpha_1, \alpha_1 \Rightarrow \alpha_2, ... , \alpha_{n-1} \Rightarrow \alpha_n$, 则可以记作 $\alpha_0 \Rightarrow \alpha_1 \Rightarrow \alpha_2 \Rightarrow ...\Rightarrow \alpha_n$, 称符号串 $\alpha_0$ 经过 n步推导出 $\alpha_n$，可简记为 $\alpha_0 \Rightarrow ^n a_n$

• $\alpha \Rightarrow ^0 \alpha$
• $\Rightarrow ^+$ 表示“经过正数步推导”
• $\Rightarrow ^*$ 表示“经过若干（可以是0）步推导”

有了文法（语言规则），如何判定某一词串是否是该语言的句子？

• 句子的推导（派生） —— 从生成语言的角度
• 句子的规约 —— 从识别语言的角度

句型和句子

如果 $S \Rightarrow^* \alpha, \alpha\in(V_T \cup V_N)^*$ , 则称 $\alpha$ 是 $G$ 的一个句型（sentential form）

• 一个句型中既可以包含终结符，又可以包含非终结符，也可能是空串

如果 $S \Rightarrow^* w, w\in V_T^*$，则称 $w$ 是 $G$ 的一个句子（sentence）

• 句子是不包含非终结符的句型
• e.g.