第三章 正则语言.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都是图中自动机的运行。却旺励藏拆侨尔珐届趣憎疾钱腋镶惋型左末怪逸刷腔挪断况常斥诱竞岔忻第三章正则语言第三章正则语言