##### 形式语法 - 形式语法 - **形式语法**是描述[[形式语言]]的规则系统, 它定义了如何从[[字符集]]生成有效的[[字符串]], 或者说它指定了哪些符号串是该语言的成员. 形式语法由一组非终结符号, 终结符号, 产生式规则和指定的起始符号组成, 可以表示为四元组 $G = (V, \Sigma, P, S)$. 其中产生规则通常具有[[递归]]性, 意味着可以产生无限的字符串. **乔姆斯基层次结构**是形式语法类别的包含层次结构, 存在四种不同类型的形式语法, 它们可以生成越来越复杂的语言, 每类形式语法都能完全生成所有下级类别的语言 - $V$ 是非终结符集合, 表示语法中的变量或中间符号, 可以进一步推导为终结符或其他非终结符 - $\Sigma$ 是终结符集合, 表示语法推导的终点, 不能再被替换 - $P$ 是产生规则的集合, 定义了如何从非终结符生成字符串 - $S$ 是开始符号, 是从哪个非终结符开始推导的起点 - 乔姆斯基层次结构 - [[正则语言]] [[正则语法]] - [[上下文无关语言]] [[上下文无关语法]] - [[上下文相关语言]] [[上下文相关语法]] - [[递归可枚举语言]] 非限制语法