形式语言与自动机.

形式语言与自动机理论FormalLanguagesandAutomataTheory朱保平南京理工大学计算机学院形式语言形式语言•形式语言是研究自然语言和人工语言的数学工具，只研究组成规则，不研究语义。-将语言看做句子的集合-将句子看做字母按照一定规则组成的字符串-根据规则的形式区分语言类;-大部分问题都可转化为判定某个句子是否属于某个语言的问题•发展过程–克林(Kleene)在1951-1956年间，在研究神经细胞中建立了自动机来识别语言。–1956年，乔姆斯基(Chomsky)从产生语言的角度研究语言。L⊆Σ*，文法(grammar)。–1959年，乔姆斯基证明了文法与自动机的等价性。自动机自动机理论自动机理论研究抽象计算装置或“机器”。–以状态自动机为基础，建立抽象机器模型；–研究机器能做什么，不能做什么，从而定义划分可计算问题和不可计算问题。•发展过程–1930s，图灵提出图灵机模型；–1940~1950s，有限状态自动机方面的研究；–1969年，库克分离出了能有效解决的问题和难解问题。形式语言与自动机理论的应用有限状态自动机是描述许多重要硬件和软件的有用模型。只有有限个状态，使得可以用有限的资源来实现。–字符串匹配算法(KMP)–词法分析器–设计和检验数字电路行为的软件–其它一些软件，如通信协议验证•与有限自动机有关的两种符号表示–文法：设计处理递归结构数据的软件的模型–正规表达式：与自动机描述的字符串模式等价•自动机是研究计算复杂性的必要基础–可判定性问题：可判定问题和不可判定问题–可处理性问题：一般问题和难解问题计算机与人脑观点一：计算机的能力不如人脑的能力–计算机无法解决不可判定问题；–人脑能够部分解决不可判定问题；例如：判定任意一个程序是否输出“helloworld”。•观点二：计算机的能力与人脑的能力相当–人脑由神经元细胞构成，每个神经元相当于一个有限状态自动机，神经元之间的连接是不断变化的，所以人脑相当于一个极其复杂的不断变化的有限状态自动机；–计算机能够模拟所有图灵机，也就能够模拟所有有限状态自动机。第一章语言1.1语言的定义语言学家chomsky,最初从定义语言的角度研究语言.1956年,他将语言L定义为字母表∑中的字符组成的一些串的集合:字母表上按一定规则定义一个文法,该文法所能产生的所有的句子组成的集合就是该文法定义的语言.*L1.2基本概念1.语言研究的三个方面（1）表示representation：无穷语言的表示（2）有穷描述finitedescription：研究的语言要么是有穷的，要么是可数无穷的，这里主要研究可数无穷语言的有穷描述。（3）结构structure：语言的结构特征2.字母表alphabet字母表是一个非空有穷集合，字母表中的元素称为该字母表中的符号。例：＝｛0,1｝等。3.字母表的积运算12＝｛aba1,b2}例：1＝｛0,1｝，2＝｛a,b,c}12={0a,0b,0c,1a,1b,1c}4.字母表的n次幂0＝｛｝为空串n＝n-1的正闭包：＋＝234的克林闭包：＊＝0＋＝0123例：＝｛0,1｝+＝｛0,1,00,01,10,11,000,001，｝*＝｛,0,1,00,01,10,11,000,001，｝直观定义：*＝｛x|x是中的若干字符连接而成的字符串｝＋＝｛x|x是中至少一个字符连接而成的字符串｝5.句子sentence是一个字母表，对于＊上的任何元素x，x叫做上的一个句子。6.句子的长度x∈＊,句子x中字符出现的总个数,记为|x|,长度为零的字符串称为空句子.用表示.7.语言:对于任意的,L称为字母表∑上的一个语言.对于任意一个x∈L,x叫做L的一个句子.例:={0,1}上不同的语言:{00,11}{0,1}{0,1,00,11}{001,01,0001,10}{00,11}*{0}{0,1}*{1}{0,1}*{111}{0,1}**L1.3语言的有限描述递归定义是解决无穷语言的有穷描述的最好方法.递归定义的三要素:(1)基本条款(2)归纳条款(3)最小性条款1.3语言的有限描述例1：｛a,b}上的所有以a打头，长度为偶数的句子。设L是满足以上条件的语言，L中元素满足如下条件：（1）aa,abL（2）若uL,则uaa,uab,uba,ubbL（3）L中的每个句子是有限使用（1）（2）所得。例2：｛a,b}上没有两个连续b的所有句子。设L是满足以上条件的语言，L中元素满足如下条件：（1）,bL（2）若uL,则ua,uabL（3）L中的每个句子均是有限次使用（1）（2）所得。1.3语言的有限描述例3：L＝｛a,b}＊{bb}{a,b}＊L表示所有含有bb的a,b的字符串。例4：L＝{aa,bb,ab,ba}＊L表示所有长度为偶数的字符串。1.4正规语言及其表示（1）定义：上的正规语言，满足下列定义：（1）{}和为上的正规语言。（2）对于a,{a}为上的正规语言。（3）若X，Y为上的正规语言，则X｜Y，XY，X＊也是上的正规语言。（4）所有上的正规语言均是有限次使用（1）（2）（3）而得。定义：设为一字母表，上的正规式由如下定义：（1）和都是上的正规式。（2）任何a，a是上的正规式。（3）u和v是是上的正规式，则u|v,uv,u＊为上的正规式。（4）所有上的正规式均是有限次使用（1）（2）（3）而得。正规语言和正规式一一对应1.4正规语言及其表示（2）设={a，b}，上的正规式和相应的正规集有：正规式正规集a{a}ab{a，b}ab{ab}a*{，a，aa，aaa，…}a*b{b，ab，aab，aaab，…}（ab）*{，a，b，aa，bb，ab，ba，a和b的任意符号串}1.4正规语言及其表示（3）已知字母表｛a,b}，试构造其上的正规式（1）以aa打头的所有符号串的集合。aa(a|b)*（2）以aa结尾的所有串的集合。(a|b)*aa（3）每个a有一个也仅有一个b紧跟其后的所有串的集合。b*(ab)*（4）每个a有一个至少有一个b紧跟其后的所有串的集合。b*(abb*)*（5）至少包含一个a且每个a都有b紧跟其后的所有串的集合。b*ab(b|ab)*1.4正规式的性质（1）rs=sr（2）r（st）=（rs）t（3）（rs）t=r（st）（4）r（st）=rsrt（st）r=srtr（5）r=rr=r2文法与语言例1：已知语言L＝｛｛a,b}*且中a的个数为偶数｝SaA（A中a的个数为奇数，b任意）SbS(S中a的个数为奇数，b任意）AaSbA例2：已知语言L＝｛｛a,b}*且中a，b的个数为相同｝SaAbBAbSaAABaSbBB例3：L（G（S））={|{0,1}*其中中0的个数为偶数且如果存在1的话必须至少有两个连续的1}S0A（0奇，1符合题意）S11B（0偶，1任意）A0SA1C（0奇，1打头）B0D（0奇，1任意）B1B（0偶，1任意）C1D（0奇，1任意）D0B（0偶，1任意）D1D（0奇，1任意）例4：L（G（S））={|{0,1}*其中中至少包含一个1且每个1都有0紧跟其后}S1A（A为0打头，1符合题意）S0SA0B（B为0任意，1符合题意）B0BB1A（A为0打头，1符合题意）例5：L＝｛aR{a,b}＊，其中R为的逆｝SaaSabSbExample6:Constructagrammarover{a,b,c}whoselanguageis{anb2ncm|n,m0}Example7:Constructagrammarover{a,b,c}whoselanguageis{anbmc2n+m|n,m0}SaSccaBccBbBbbbExample8:Constructagrammarover{a,b,c}whoselanguageis{anbmci|0≤n+m≤i}SaSbccBAAaAcCBbBcCCaCExample9:Constructagrammarover{a,b}whoselanguageis{anbm|0≤n≤m≤2n}SaSbaSbb右线性文法：文法中每条规则形如Aa或AaB，其中a为终结符或，A，B为非终结符。左线性文法：文法中每条规则形如Aa或ABa，其中a为终结符，A，B为非终结符。例：给出语言L＝｛anbmckn,m,k=0}的左线性和右线性文法。左线性文法为：SScBBBbAAAa右线性文法为：SaSBBbBCCcC第3章上下文无关语言3.1上下文无关文法一、定义:文法G=(V,T,P,S)称为上下文无关文法,如果P中的每一条规则具有形式:其中A∈V,x∈(V∪T)*例：文法G=（{S}，{A，B}，S，P），产生式这个文法是上下文无关的，它的推导是：SaSaaaSaaaabSbaaaabbaa其定义的语言为xA||bSbaSaS*},{|{)(baGLR试证明语言是上下文无关的。证明：当nm时：nm时该文法是上下文无关的，所以该语言是上下文无关语言。*}|{mnbaLmnaAaAbaSSASS||111bbBBaAaAbaSSBSASS||||1111二、最左推导和最右推导如果每次都替换句型中最左边的变量，那么称这种推导这最左的（leftmost).如果每次都替换句型中最右边的变量，那么称这种推导这最右的（rightmost).三、推导树：推导过程的图解表示称为该句型的推导树。例：已知文法G为：SSABAaAaBbB(1)给出abbaab的最左推导（2）给出abbaab的最右推导（3）给出（2）中的派生树解（1）SSABSABABABABaBABabBABabbBABabbABabbaABabbaaBabbaab(2)SSABSAbSaAbSaabSABaabSAbBaabSAbbBaabSAbbaabSabbaababbaabEXAMPLE1:LetGbethegrammarSSABAaAaBbB(a)Givealeftmostderivationofabbaab(b)Givetwoleftmostderivationsofaa(c)Buildthederivationtreeforthederivationsinpart(b)(d)GiveaergularexpressionforL(G).EXAMPLE2:Arightgarmmarisacontext-freegrammareachofwhoseruleshasoneofthefollowingforms:i)Aωii)AωBiii)AWhereω∈∑*.provethatalanguageLisgeneratedbyaright-lineargrammarif,andif,Lisgeneratedbyaregulargrammar.二义性二义性的解决办法:(1)修改文法SSS|β(2)修改编译算法3.2上下文无关文法的化简3.2.1无用符号3.2.2去ε产生式构造无产生式的算法：已知G=（VN，VT，P，S）为含的文法，构造无文法G’=（V’N，V’T，P’，S‘）(1)由文法G推出满足如下定义的非终结符号集合V0={AAVN且A+}(2)再按下列方法构造G’产生式集合P’：(A)若产生式B0B11B2…BKK属于P，其中jV*（0jk），BiV0，那么将这些Bi以或Bi本身的两种形式替代，然后将有关B的所有产生式扣除产生式后加入P’中；