文法和语言的形式定义 如何来描述一种语言? 如果语言是有穷的(只含有有穷多个句子),可以 将句子逐一列出来表示 如果语言是无穷的,找出语言的有穷表示。语言的 有穷表示有两个途经: 生成方式(文法):语言中的每个句子可以用严 格定义的规则来构造 识别方式(自动机):用一个过程,当输入的一任 意串属于语言时,该过程经有限次计算后就会停止 并回答“是”,若不属于,要麽能停止并回答“不 是”,(要麽永远继续下去。) 21
21 文法和语言的形式定义 如何来描述一种语言？ 如果语言是有穷的（只含有有穷多个句子），可以 将句子逐一列出来表示 如果语言是无穷的，找出语言的有穷表示。语言的 有穷表示有两个途经： 生成方式 （文法）：语言中的每个句子可以用严 格定义的规则来构造。 识别方式（自动机）：用一个过程，当输入的一任 意串属于语言时，该过程经有限次计算后就会停止 并回答“是”，若不属于，要麽能停止并回答“不 是”，（要麽永远继续下去。）
文法即是生成方式描述语言的:语言中的每 个句子可以用严格定义的规则来构造下面 给出文法的定义进而在文法的定义的基础 上给出推导的概念句型、句子和语言的定 义 22
22 文法即是生成方式描述语言的：语言中的每 个句子可以用严格定义的规则来构造.下面 给出文法的定义.进而在文法的定义的基础 上,给出推导的概念,句型、句子和语言的定 义
定义 文法G定义为四元组(vN,V,P,S)其中 V为非终结符号(或语法实体,或变量)集; V为终结符号集; P为产生式(也称规则)的集合;VN,Ⅵ和P是非 空有穷集。 S称作识别符号或开始符号,它是一个非终结符, 至少要在一条产生式中作为左部出现。 VN和V不含公共的元素,即VN∩V=中 用Ⅴ表示VN∪Ⅵ,称为文法G的字母表或字汇表 规则,也称重写规则、产生式或生成式,是形如 a→β或a:邛β的(α,β)有序对,其中α是字母表V 的正闭包V中的一个符号,β是ⅴ中的一个符号 α称为规则的左部,β称作规则的右部
23 定义 文法G定义为四元组(VN，VT，P，S )其中 VN为非终结符号(或语法实体，或变量)集； VT为终结符号集； P为产生式(也称规则)的集合； VN，VT和P是 非 空有穷集。 S称作识别符号或开始符号，它是一个非终结符， 至少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN ∩ VT = φ 用V表示VN ∪ VT ，称为文法G的字母表或字汇表 规则，也称重写规则、产生式或生成式，是形如 α→β或α∷=β的(α，β)有序对，其中α是字母表V 的正闭包V+中的一个符号，β是V*中的一个符号。 α称为规则的左部，β称作规则的右部
Define a grammar a grammar g is defined as a 4-tuple(vn, v, p, s) Vu is a set of nonterminals Vr is a set of terminals P is a set of productions, each production consists of a left side, an arrow(or :: =),and a right side S is a designation of one of the nonterminals as the start symbol VEVN U Vris the alphabet of 24
24 Define a grammar A grammar G is defined as a 4-tuple (VN，VT，P，S) VN is a set of nonterminals VT is a set of terminals P is a set of productions，each production consists of a left side,an arrow(or ‘::=‘),and a right side S is a designation of one of the nonterminals as the start symbol V =VN ∪ VT is the alphabet of G
文法的定义 例文法G=(VN,V,P,S) VN={s},v={01} P={S→0s1,S→01} s为开始符号 25
25 文法的定义 例 文法G=（VN，VT，P，S） VN = { S }, VT ={ 0, 1 } P={ S→0S1, S→01 } S为开始符号