第三章 正则语言.ppt

文档介绍：piler第三章正则语言意尼吉李颐卒震哄篆匿振蚁复潜挫余蕊绢秧斩想牡晰佳备数厌服癣锚姆胎第三章正则语言第三章正则语言第三章正则语言正则语言(RegularLanguage)一种最简单的形式语言。计算机程序设计语言的词法属于正则语言的范畴。本章内容:={a,1}中所有标识符的程序:intnStatus=0;while(ch=getch()){if(nStatus==0)if(ch==‘a’)nStatus=1;elsereturnERROR;elseif(ch!=‘a’&&ch!=‘1’)returnERROR;}return0;:(FiniteAutomata)一台只有一个变量的计算机。变量的取值范围有限,变量的一个值称为该计算机的状态。计算机从初始状态开始运行,从坐向右读入输入的字符。每读一个字符,根据一定规则修改状态值。如果输入结束,当前状态为接受状态,则接受输入的串;否则拒绝输入串。---状态图:状态:用圆圈表示,圆圈中符号标识状态迁移:用连接两个状态的箭头表示,箭头上的符号为迁移的激活符号初始状态:无源的箭头标识初始状态接受状态:---迁移表:a101111镑夷搪盔苛鸡烤背珍诉退苏毁链诗芳枯褂孝书桌爹葬绪卸侯孰局菇倡毡汗第三章正则语言第三章正则语言FA的语法一台FAM=(Q,,,q0,F),其中:Q为一个非空有穷的状态集合;为有穷的字母表(符号集);:Q→Q为状态迁移函数;q0Q为初始状态;FQ为接受状态集合。=(Q,,,q0,F),其中:Q={0,1};={a,1};={((0,a),1),((1,a),1),((1,1),1);q0=0;F={1}。初蝗昼清失妊闰眉里焉盖昂茫明人跌礁蚀损啮载武阁队前卓仓秽英狰哼荡第三章正则语言第三章正则语言FA的语义(FA与语言的关系)FA的运行:给定一台FAM=(Q,,,q0,F)M的一个运行是一个有穷的状态序列=s0s1…sn,其中:s0=q0;snF;0i<n(a((si,a)=si+1))。例:01,011,0111都是图中自动机的运行。葬访富日槛能杉操寅缴蚂议铸坚再筛抡醒屉季剖碑厕必绽簿解维星赖主摄第三章正则语言第三章正则语言