第一章 第3节 语言的定义

推导（Derivations）和归约（Reductions）

给定文法 G = (Vt,Vn,P,S), 如果 α -> β ∈ P ，那么可以将符号串 γαC 中的 α 替换为β 重写为 γβC , 记做 γαC => γβC 。此时，称文法中的符号串 γαC 直接推导出 γβC

归约是推导的逆过程

句型和句子

如果 S => α ，α∈(Vt ∪ Vn) ,则称α是G 的一个句型 （sentential form）

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

如果 S=> w , w ∈ Vt ,则称 w是G 的一个句子
句子是不包含非终结符的句型

image.png

语言的形式化定义

由文法G的开始符号S 推导出的所有句子构成的集合称为文法G生成的语言，记为 L(G).
即
L(G) = {w | S => *w ,w ∈ Vt *}

image.png

语言上的运算

image.png