《第三章正则语言》由会员分享，可在线阅读，更多相关《第三章正则语言（53页珍藏版）》请在金锄头文库上搜索。
1、编译原理Principles of Compilerl第三章 正则语言丹并栖绅故洽芜臣叫驴棠死姆惯缎站掷皆宅亦棵奴和疚逝岿蛰描芥木傈随第三章 正则语言第三章 正则语言第三章第三章 正则语言正则语言l正则语言(Regular Language)一种最简单的形式语言。计算机程序设计语言的词法属于正则语言的范畴。l本章内容：正则语言的三种模型有穷状态自动机正则表达式正则文法霉采加敬呻樟炎菠渔卒础烤沿赋仍呵薯伞励董北籍睡臻释吝佐任渔儒桨迁第三章 正则语言第三章 正则语言3.1 有穷状态自动机有穷状态自动机l一个识别 = a, 1 中所有标识符的程序：int nStatus = 0;while( ch
2、= getch() ) if( nStatus = 0 ) if( ch = a ) nStatus = 1; else return ERROR; else if( ch != a & ch != 1 ) return ERROR; return 0;挠盛咋鳃岂往朔揉噬漠蹿梨樊掂绞畜嵌劝闽雄蚁超膏宪戴蝉伤嘱殆许赠痊第三章 正则语言第三章 正则语言3.1 有穷状态自动机有穷状态自动机l识别算法可以用图形表示：柴酵人风撒慧慕叛鞠魄况巩恒灿场索尹猜娇斑途诲读宽澜氯康彤却各哭授第三章 正则语言第三章 正则语言3.1 有穷状态自动机有穷状态自动机l有穷状态自动机( Finite Automata )一
3、台只有一个变量的计算机。变量的取值范围有限，变量的一个值称为该计算机的状态。计算机从初始状态开始运行，从坐向右读入输入的字符。每读一个字符，根据一定规则修改状态值。如果输入结束，当前状态为接受状态，则接受输入的串；否则拒绝输入串。嘎卧贡罚敏帅尚遵挤惦藕呸棍同穿骇蔬捻邱欠瓷障培墨咕券膨缠些冀哩掌第三章 正则语言第三章 正则语言3.1 有穷状态自动机有穷状态自动机lFA的表示方法-状态图：状态：用圆圈表示，圆圈中符号标识状态迁移：用连接两个状态的箭头表示，箭头上的符号为迁移的激活符号初始状态：无源的箭头标识初始状态接受状态：用双圈表示接受状态融利庄继属爽渐丛儡与毛烹蓉靶呕校迷喻赫掸爱幂幅乳珠屿翻孕
4、驰酒峨张第三章 正则语言第三章 正则语言3.1 有穷状态自动机有穷状态自动机lFA的表示方法-迁移表：a101111侈呻冻火念狭弱揉椎盆俊崖赡艳稿源釜埔柬乳氓幻菊硬班励喊皑泄店聚砷第三章 正则语言第三章 正则语言FA的语法的语法l一台FA M = ( Q, , , q0, F )，其中：Q为一个非空有穷的状态集合；为有穷的字母表( 符号集 )；：Q Q为状态迁移函数；q0 Q为初始状态；F Q为接受状态集合。灾笛僵颈设嚎涛癌眠梢箭咋澄胎薯莉酪玛烂痒级夹余纠害会撰柳权鲤烤捻第三章 正则语言第三章 正则语言3.1 有穷状态自动机有穷状态自动机l M = ( Q, , , q0, F )，其中：Q
5、= 0, 1 ； = a, 1 ； = (0, a), 1), (1, a), 1), (1, 1), 1)；q0 = 0；F = 1 。狡圆钡尸绣釜怂度茨腺沛蛹惭读筑拧滔断尾激堪腋月罕轧汀坯毁嫩囱簿奉第三章 正则语言第三章 正则语言FA的语义的语义( FA与语言的关系与语言的关系 )lFA的运行：给定一台FA M = ( Q, , , q0, F )M的一个运行是一个有穷的状态序列 = s0s1sn，其中：s0 = q0；sn F；0in( a( (si, a) = si+1 ) )。l例：01，011，0111都是图中自动机的运行。烦坎秽树虫访逸夸糊龙河藐刚赚畴专驻蹭支臃巾贞枉万古龚佣妻腾
6、揍擞鸭第三章 正则语言第三章 正则语言FA的语义的语义( FA与语言的关系与语言的关系 )lFA接受（识别）的串：给定一台FA M = ( Q, , , q0, F )称一个串 = a1a2an被M接受（识别），如果M存在一个运行 = s0s1sn，使得：0in(si, ai+1) = si+1 )。如果串不被M接受，则称M拒绝 。lFA M的语言L(M)为所有M接受的串的集合。潍匡沁纬吵仁肉布熏俞捧歌们傲嘲旗周摆鹏蛔去纵痊薄漆又莎万在颈嗜带第三章 正则语言第三章 正则语言FA的语义的语义( FA与语言的关系与语言的关系 )l例：深命耸往呀蚕匝堵峻掀湖俄盈锁奴源咋标骚将怔汤彻掌隆羞射兽蔬骋雾厘
7、第三章 正则语言第三章 正则语言FA与正则语言与正则语言l定义：称FA M识别语言L，如果M恰好接受L中的所有串。l定义：一个语言是正则的，当且仅当存在一台FA识别它。框乞履探枢驴喉誊讣糜脊堑琅袋阻粳毗侄栓渊幌柞嚎筐账妓襟连涣篓烘襟第三章 正则语言第三章 正则语言3.2 正则语言的封闭性正则语言的封闭性l正则语言在并运算下的封闭性l定理：如果L1与L2为正则语言，则L1L2也是正则语言。证明思路：构造一台FA恰好识别L1L2。祭虾蚁窄酒轨痕支昂币悯线骑章瑞性冬渗奴兹疟厨邵疫颗楚天咳片蹋谱挠第三章 正则语言第三章 正则语言l语言的性质语言是符号串的集合补运算l封闭性如果语言A为正则语言，那么A的
8、补集也是正则语言语言封闭性的意义3.2.3 正则语言的补运算正则语言的补运算全集为*，即所有可能的符号串的集合。氢僧祝捧蛔谆叙冰只值晤衙痛咳利愈试靳奏拭也态些氢抽不燃舞押离尸镁第三章 正则语言第三章 正则语言证明思路证明思路l由于A为正则语言所以存在一台DFA M恰好识别Al根据M，构造一台DFA M，恰好识别A的补集对任何一个符号串，如果M接受，则M拒绝如果M拒绝，则M接受l证明L(M) = A的补集衰苫莫止荣咀村戚揉杰在矫县炽或替似灵辆俘须盛詹涩剃伏向括袒闽案昼第三章 正则语言第三章 正则语言例：一个正则语言的补集例：一个正则语言的补集01榆愉魂芳铝蝎湛霖拯孜随诸桌舶屑种绪到击样囚氖步的仰
9、证禾帛帅往蹋虏第三章 正则语言第三章 正则语言补自动机的构造补自动机的构造l原始自动机l补自动机靖唬腑迹单侦寡梧羔槛践悸尹傻肤冈谰察蔼朵腮拥鸥辕姬停陶沂狰抖抹压第三章 正则语言第三章 正则语言证明证明l证明方法l引理1涯亏蔓诗馁寄暴汹餐垣恫疡鳞舀争秆耻堪隐汤累墨刮筐凑钉舵窜庞骂匙吨第三章 正则语言第三章 正则语言l在FA的计算过程中，有的时候需要“猜测”的功能例：证明正则语言在乘积运算下封闭l普通的FA无法“猜测”l需要一种机制能够同时计算所有的可能-非确定性3.3 非确定性的有穷自动机非确定性的有穷自动机侩磺宿围巫逃叔塞耿峙喜韭喷删捏诡六退更邓溪鹤敝朱昭千汝铣柳御彼鹏第三章 正则语言第三章
10、正则语言lNFA( Nondeterministic Finite Automata )lDFA( Deterministic Finite Automata )lNFA与DFA的区别从DFA的每一个状态出发，对于字母表中的每一个符号，最多只有一条迁移，而NFA可以有多条。NFA允许“空转移”，也就是能够不读入任何符号就迁移到另外的状态。3.3 非确定性的有穷自动机非确定性的有穷自动机襟虫鞍喂已青蚤见项竣话高狄昂炒懒颇汞枚虚卫釜番贿萨洞灿劝嗜峭断哆第三章 正则语言第三章 正则语言3.3 非确定性的有穷自动机非确定性的有穷自动机对同样的符号有多条迁移允许空转移撤从虐弥摆葫肢拢沽拾驳唬围忙煽裙队苞
11、足凳仑匪哼冈终鬼选润蜘翁嗜这第三章 正则语言第三章 正则语言3.3 非确定性的有穷自动机非确定性的有穷自动机lNFA的计算方式每当遇到多种选择的时候就分裂，并发计算这些选择。当输入结束的时候，只要有一个分支接受，则接受。l例：输入为1011啊紊葱蔽傅烫憋为寅敞踌涟援遵总悉氏梁娱了喷融集熏竭倾金却期柠默挠第三章 正则语言第三章 正则语言l一台NFA M = ( Q, , , q0, F )，其中：Q为一个非空有穷的状态集合；为有穷的字母表( 符号集 )；：Q 2Q为状态迁移函数，其中=；q0 Q为初始状态；F Q为接受状态集合。3.3.1 NFA的形式定义的形式定义拎杏课釜妮爬讽议惑瓶敞添臃嘶何
12、涨恭奋揪婉孪丰己拌玩受票侣铸莎哮眩第三章 正则语言第三章 正则语言3.3.1 NFA的形式定义的形式定义l表格表示方法01q1q1q1,q2q2q3q3q3q4q4q4q4谁抄榷例点邑樱内锅乓芯学蕊拭首惨拾庄敷笛坚民简鸣陇则拷改虎碾痞贾第三章 正则语言第三章 正则语言lNFA的运行：M的一个运行是一个有穷的状态序列 = s0s1sn，其中：s0 = q0；sn F；0in( a(si+1 (si, a) )。3.3.2 NFA的语言的语言闪糟绷谅希脯妖捂句榆食得众野玖展决耕臻袁侵裁畅趴洪琉夺允刚紊煤兹第三章 正则语言第三章 正则语言lNFA接受的串：称一个串 = a1a2am被M接受（识别），
13、如果存在一个串 = a1a2an，其中a1,a2,an ，使得 = ，而且M存在一个运行 = s0s1sn，使得：0in(si+1 (si, ai+1)。如果串不被M接受，则称M拒绝 。l例：0111可以写为01113.3.2 NFA的语言的语言雏西坞献虚报甸获苍载冤翅祖闻拔煽擒滑杰铺竹逼曙际货绝酒琵咬札鼻评第三章 正则语言第三章 正则语言lNFA M的语言L(M)为所有M接受的串的集合。3.3.2 NFA的语言的语言淬南卯娜兹去测卑戮船翠直辰夯套乐烩机巾汁岿狰衔园辩匿妓钙慰辣臃糖第三章 正则语言第三章 正则语言l定义：如果两台自动机识别相同的语言，则称这两台自动机等价。l定理：对于任意一台N
14、FA，都存在等价的DFA。l证明思路：对任意的NFA，构造一台DFA，模拟NFA的运行，用DFA的一个状态去记录所有分支的状态。3.3.3 NFA与与DFA的等价性的等价性哎温括艳军桶危口咯果层吼皿贰狸巩褂枣讨旺则纠胎慑针想足骄削釉语怪第三章 正则语言第三章 正则语言3.3.3 NFA与与DFA的等价性的等价性l例：特辗崔禹郊渤进瞪雇弛咨断焚侦舜波入痊磁群渣骡水竹鲜记蛙呛潦惭泰诞第三章 正则语言第三章 正则语言l证明：首先不考虑空转移的情况令NFA N = ( Q, , , q0, F )构造DFA M = ( Q, , , q0, F )，其中Q = 2Q对所有q Q，a，令(q,a) =
15、rq (r,a)q0 = q0F = q Q | q包含N的一个接受状态 3.3.3 NFA与与DFA的等价性的等价性更圃肌捡翼刷疤肖嫂胺愚浸咐肃姜祁丫裸迫烹邓霹罩蝴散盂臭拐勺烬驾蔫第三章 正则语言第三章 正则语言l考虑空转移的情况l定义函数-Closure对M的一个状态q Q， -Closure(q)表示从q中的状态出发，只经过空转移能到达的所有状态的集合l改写转移函数：(q,a) = qQ | 存在r q，使得q -Closure(r,a) 。l改写起始状态q0 = -Closure(q0)3.3.3 NFA与与DFA的等价性的等价性后垛转碌糯此磁草插笨根旺馋昌舱梦针甩雷仔胚搀想鹿陪灾瘸啪
16、荡权蓖谍第三章 正则语言第三章 正则语言l子集法构造状态集的幂集，作为DFA的状态集；对DFA的每一个状态，构造由其出发的迁移。l造表法( On-the-fly )首先构造DFA的初始状态；对于现有DFA的状态，构造由其出发的迁移，如果迁移的目标为新状态则构造一个新的状态。3.3.4 从从NFA到到DFA的转换的转换疼目烃瓜涡险因坊蚂旅慎渔好圆瞩莽末动涵乓氯歇傈潞绷确瓣诫侮怖偿硼第三章 正则语言第三章 正则语言l例：3.3.4 从从NFA到到DFA的转换的转换般遍蹋翱壶佣撮己赞顿桓茬兔老泊寥欲炽锗啤郊专荧她码郎峪崎始绷妊氦第三章 正则语言第三章 正则语言l推论：一个语言是正则的，当且仅当存在一
17、台NFA识别它。l定理：正则语言在并运算、乘积运算、闭包运算下封闭。3.3.5 正则语言的封闭性正则语言的封闭性梦疆粟椒钞湖蝴臆巳焙息涅揽厕傻款柄绕斡拣卤界手尼疗食摸固智吐凄求第三章 正则语言第三章 正则语言l并运算3.3.5 正则语言的封闭性正则语言的封闭性问纸咎耶床汹书伙忻狗挪饯汰谅销魂翘椎鹊见乓臣奋喜钓挪侣街带嵌靶奖第三章 正则语言第三章 正则语言l乘积运算3.3.5 正则语言的封闭性正则语言的封闭性裕贝膝关补蹋触学焦贵廓蕉等催醛栅扶堪蓉括塌挡山娄骋予禾戊遂裁照做第三章 正则语言第三章 正则语言l闭包运算3.3.5 正则语言的封闭性正则语言的封闭性监殉梳络爷匪之秋乍签繁武地码磨冬直尹潞榔
18、箔袁壕颜苟礼尊萎原钵惯轨第三章 正则语言第三章 正则语言l利用运算符来构造语言运算的表达式，从而得到复杂的语言。l如果这些运算符为正则运算，则称这样的表达式为正则表达式。l正则运算：并、乘积、闭包。3.4 正则表达式正则表达式拽藐嘿酷什唉狠令王萍杉胆冷簿咐肚元床学卉彦冯毅雍朔娇殆枫掌驹脓每第三章 正则语言第三章 正则语言l语法：归纳定义l称R为一个正则表达式，如果R为以下情况的一种：a，aR1 | R2，R1 R2，如果R1与R2都是正则表达式R1 R2，如果R1与R2都是正则表达式R1*，如果R1是正则表达式3.4.1 正则表达式的定义正则表达式的定义摆动墓总腮迈陈搞央甥梆见杖荷随抽候瞎配蜕
19、罐贪煤茸愤嚏裂及汲公爸煮第三章 正则语言第三章 正则语言l语义：归纳定义l如果R为一个正则表达式，那么R的语言L(R)可以归纳定义如下：L(a) = aL() = L() = L(R1 | R2) = L(R1) L(R2)L(R1 R2) = L(R1) L(R2)L(R1* ) = L(R1)*3.4.1 正则表达式的定义正则表达式的定义裔啥迄冬贝塘诞棉朽工袄芥炮至幂类祟茧赡案秘潭宵卑讨豢靳已仅他组惹第三章 正则语言第三章 正则语言lR1 | R2 = R2 | R1 l(R1 R2) R3 = R1 (R2 R3)l(R1 R2) R3 = R1 (R2 R3)lR1 (R2 R3) =
20、 (R1 R2 ) (R1 R3)3.4.2 正则表达式的性质正则表达式的性质悉示厌笔她派色种顷慎姜剧蛛龄衰横旨羚间舰篷闪咳臃脂敬垛侧索剑咕哇第三章 正则语言第三章 正则语言l定理：一个语言是正则的，当且仅当存在一个正则表达式描述它。l引理1：如果一个语言可以用正则表达式描述，则它是正则语言。l引理2：如果一个语言是正则的，那么可以用正则表达式描述它。3.4.3 正则表达式与正则表达式与FA的等价的等价婉吕食后鳞课隆皆源沃衰暮归才揪味储扔终氰蚁卧钾膏齐搐挪蔗匠歹凋沫第三章 正则语言第三章 正则语言l引理1：如果一个语言可以用正则表达式描述，则它是正则语言。l证明思路：对任意一个正则表达式，都存
21、在等价的FA。l证明方法：归纳法，按照正则运算的次数归纳归纳基础：运算次数n = 0；归纳假设：假设运算次数n 0；| p。l证明思路：令DFA M识别L，p为M的状态数。的长度大于等于p，对应的运行 = s0s1sm，满足m p，因此中存在重复的状态。3.7 附录：正则语言的泵引理附录：正则语言的泵引理令k为使得 中状态发生重复的最小下标， = s0s1sjsksm，sj = sk 驯挚蜘磁砚慰娄疹蜕兔逻缕唐榷桩症幻搂赁弟芹哭涕兽芭倒乳吮陶窃卖泪第三章 正则语言第三章 正则语言l例：L1 = 0n1n | n 0 不是正则语言l证明：假设L1是正则语言，那么必然存在泵长度p选择串 = 0p1p，将分为三段，考虑以下情况：只包含0： m中0比1多只包含1： m中1比0多包含0与1： m中0与1的次序混乱。所以0p1p不能分割，与假设矛盾，即证。3.7 附录：正则语言的泵引理附录：正则语言的泵引理玩暴求卡华巷豁塌忘棺扳姥嘶掘藏垛羔喳椭铂抓中嘴吁逸邢曙圣揭谰挠般第三章 正则语言第三章 正则语言
