第二章形式语言与自动机理论基础2.32.3.1正规文法与有限自动机(FA)正规文法与有限自动机(FA)的等价性对于每一个正规文法都存在一个FAm，L(m)=L(G)每一个DFAm，都存在一个正规文法G，使L(G)=L(m)仅讨论右线性文法和有穷自动机的等价性问题22.3.1正规文法与有限自动机(FA)1、由NFANFA构造等价的正规文法正规文法有穷自动机的字母表为文法的终结符号集有穷自动机的状态集为文法的非终结符号集字母表终结符号集有穷自动机的初态对应于文法的开始符号状态集非终结符号集对有穷自动机的转换函数初态f(A,t)=B,开始符号可写成文法的一个产生式A→tB对有穷自动机的终态f(A,t)=BZ，增加一个产生式A→tBZ→终态ZZ→3NFA的状态图如图所是，求其等价的正规文法（右线性）aabSAaZbG[S]:S→aS|bSS→aAA→aZ|bZZ→42.3.1正规文法与有限自动机(FA)2、由正规文法构造等价的NFA文法的终结符号集为有穷自动机的字母表文法的非终结符号集为有穷自动机的状态集文法的开始符号作为有穷自动机的初态对文法中形如A→tB的产生式，构造有穷自动机的一个转换函数f(A,t)=B,对文法中形如A→t的产生式，构造有穷自动机的一个转换函数f(A,t)=Z5NFA的状态图如图所是，求其等价的正规文法（右线性）G[S]:S→aS|bSS→aAA→a|baabSAaZb62.3.2正规式与正规集定义2.31(正规式与正规集)设Σ为有限字母表，在Σ上的正规式与正规集可递归定义如下：1.ε和Ф是Σ上的正规式，它们表示的正规集分别为{ε}和Ф；2.对任何a∈Σ,a是Σ上的正规式,它的正规集为{a}；3.若r,s都是正规式,它们的正规集分别为R和S,则(r|s)、(r·s)、(r)*也是正规式，它们分别表示的正规集是：R∪S，RS，R*。4.有限次使用上述三条规则构成的表达式，称为Σ上的正规式，仅由这些正规式表示的集合为正规集。72、有关正规式及正规集的说明说明：1.正规式与相应的正规集是等价的，正规集给出了相应正规式所描述的全部单词（句子）；2.正规式的运算结果是正规集；3.正规式不是集合，其运算结果正规集是集合。Ф是特例。8正规表达式及正规集正规表达式的定义是字母表正规表达式正规表达式表达的语言1.，{}，{}2.a,a{a}3.若r,sL(r),L(s)则(1)(r)(s)L(r)L(s)(2)(r)(s)L(r)L(s)(3)(r)*(L(r))*(4)(r)L(r)92、有关正规式及正规集的说明注意：定义中的括号主要用于规定运算顺序。一般规定优先级从高到低依次为*,•,|，可省略某些括号例(r)•((s)*)|(r)——可简写：r•s*|r。•常常可省略不写，可写成rs*|r。10例题=a,b,上的正规式和对应的正规集是：正规式正规集(a)aba,b(b)(ab)(ab)aa,ab,ba,bb(c)a*,a,aa,aaa,aaaa,…(d)(ab)*{,a,b,aa,ab,ba,bb,aaa,...(e)aab*{a,ab,abb,abbb,……11例2：令Σ={A,B,0,1},则：(A|B)(A|B|0|1)*={A,B,AA,AB,A0,A1,BA,BB,B0,B1,…}——Σ上的“标识符”的全体(0|1)(0|1)*={0,1,00,01,10,11,…}——Σ上“数”的全体12等价正规集注意：正规式和正规集间不是一一对应关系若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如：e1=ab，e2=ba又如：e1=b(ab),e2=(ba)b,e1=(ab)e2=(ab)例：设PASCAL语言子集有如下单词①BEGIN②END③IF④THEN⑤ELSE⑥标识符⑧无符号整常数⑨>⑩>=⑾<⑿<=⒀=⒁<>14正规表达式的等价关系说明恒等式rs=sr“”是可交换的r(st)=(rs)t“”是可结合的r(st)=(rs)t连接是可结合的r(st)=rsrt分配律(st)r=sr