正规式,有穷自动机 正规式一正规集的描述机制 字母表∑上的正规表达式R的文法终结 符是{|,*,a∈Σ} 0)R→>82)R→>RR4)R→>a 1)R→>R|R3)R→>R* 有穷自动机一正规集的识别机制
正规式，有穷自动机 • 正规式－正规集的描述机制 字母表上的正规表达式R的文法,终结 符是{ | ， * ， a }. 0) R –> 2) R –> RR 4) R –> a 1）R –> R | R 3) R –> R* • 有穷自动机－正规集的识别机制
程序设计语言的单词都能用正规式来定义. 例3.1 令2={,d}),则∑上的正规式r1(1d)“定义的正 规集为 dldd 其中代表字母d代表 数字,规式即是字母(字母数字)*它表示的 正规集中的每个元素的模式是“字母打头的字 母数字串”,就是 Pasca和多数程序设计语言允 许的的标识符的词法规则 例32 ∑={d,·,e,+,-}, 则Σ上的正规式dd*|e(+|-|e)d+|e) 表示的是无符号数的集合。其中d为0~9的数字
程序设计语言的单词都能用正规式 来定义. 例3.1 令={l，d}，则上的正规式 r=l(l d) 定义的正 规集为: {l,ll,ld,ldd,……},其中l代表字母,d代表 数字,正规式 即是 字母(字母|数字) ,它表示的 正规集中的每个元素的模式是“字母打头的字 母数字串” ,就是Pascal和 多数程序设计语言允 许的的标识符的词法规则. 例3.2 ={d，•，e，+，-}, 则上的正规式 d (•dd )(e(+- )dd ) 表示的是无符号数的集合。其中d为0~9的数字
有穷自动机 确定的有穷自动机DFA 不确定的有穷自动机NFA NFA的确定化 DA的最小化
有穷自动机 确定的有穷自动机DFA 不确定的有穷自动机NFA NFA的确定化 DFA的最小化
文法和语言 如何来描述一种语言? 如果语言是有穷的(只含有有穷多个句子),可以 将句子逐一列出来表示 如果语言是无穷的,找出语言的有穷表示。语言的 有穷表示有两个途经: 生成方式(文法):语言中的每个句子可以用严 格定义的规则来构造。 识别方式(自动机):用一个过程,当输入的一任 意串属于语言时,该过程经有限次计算后就会停止 并回答“是”,若不属于,要麽能停止并回答“不 是”,(要麽永远继续下去。)
文法和语言 如何来描述一种语言？ 如果语言是有穷的（只含有有穷多个句子），可以 将句子逐一列出来表示 如果语言是无穷的，找出语言的有穷表示。语言的 有穷表示有两个途经： 生成方式 （文法）：语言中的每个句子可以用严 格定义的规则来构造。 识别方式（自动机）：用一个过程，当输入的一任 意串属于语言时，该过程经有限次计算后就会停止 并回答“是”，若不属于，要麽能停止并回答“不 是”，（要麽永远继续下去。）
定义 文法G定义为四元组(VN,Vr,P,S)其中 V:非终结符号(或语法实体,或变量)集; VT终结符号集; P:产生式(也称规则)的集合; Vτ和P是非空有穷集 S:称作识别符号或开始符号的一个非终结符,它至 少要在一条产生式中作为左部出现 V和Ⅴr不含公共的元素,即Vx∩Vr=中 用Ⅴ表示VN∪Vr,称为文法G的字母表或字汇表 规则,也称重写规则、产生式或生成式,是形如 α→B或∷=β的(a,β)有序对,其中α是字母表V 的正闭包V中的一个符号,β是V*中的一个符号 α称为规则的左部,β称作规则的右部
定义 文法G定义为四元组(VN，VT，P，S )其中 VN:非终结符号(或语法实体，或变量)集； VT:终结符号集； P:产生式(也称规则)的集合； VN，VT和P是 非空有穷集。 S:称作识别符号或开始符号的一个非终结符，它至 少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN ∩ VT = φ 用V表示VN ∪ VT ，称为文法G的字母表或字汇表 规则，也称重写规则、产生式或生成式，是形如 →或 ∷=的( ，)有序对，其中是字母表V 的正闭包V+中的一个符号，是V*中的一个符号。 称为规则的左部， 称作规则的右部