第三章 正则语言.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)一台只有一个变量的计算机。变量的取值范围有限,变量的一个值称为该计算机的状态。计算机从初始状态开始运行,从坐向右读入输入的字符。每读一个字符,根据一定规则修改状态值。如果输入结束,当前状态为接受状态,则接受输入的串;否则拒绝输入串。---状态图:状态:用圆圈表示,圆圈中符号标识状态迁移:用连接两个状态的箭头表示,箭头上的符号为迁移的激活符号初始状态:无源的箭头标识初始状态接受状态:---迁移表:a101111FA的语法一台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都是图中自动机的运行。