第2章有穷状态自动机康慕宁西北工业大学计算机学院语言的识别给定一个正规文法G,相应的正则语言L(G)就给定了。任给一个字符串w,w是不是语言L(G)的句子。即S⇒*w能否成立。例:S→aA|aB,A→aA|c,B→aB|d,字符串aaad是该文法所定义语言的句子吗?问题:推导和归约中的回溯问题给系统的效率产生极大的影响。解决方法:从识别的角度去考虑问题,设计有穷自动机系统来识别语言。有穷状态自动机有穷状态自动机是具有离散输入和输出的系统的一种数学模型。其主要特点有以下几个方面:(1)系统具有有穷个状态,不同的状态代表不同的意义。按照实际的需要,系统可以在不同的状态下完成规定的任务。(2)我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。(3)系统在任何一个状态下,从输入字符串中读入一个字符,根据当前状态和读入的这个字符转到新的状态。(4)系统中有一个状态,它是系统的开始状态。(5)系统中还有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子。有限状态自动机的物理模型形式定义举例状态转移(换)图状态转换表状态转换表是一个二维表,左边第二列列出有穷状态自动机的所有状态,并在第一列中标出开始状态和终止状态,上边第一行列出所有的输入字符,中间的方格内是该行所对应状态下输入该列所对应字符后转换到的新状态。扩展转换函数有限自动机接受的语言构造DFA实例(1)DFA实例3几点注意本例中有以下几点值得注意:(1)当FA一旦进入状态qt,它就无法离开此状态。所以qt相当于一个陷阱状态。(2)在构造一个识别给定语言的FA时,用画图的方式比较方便、直观。可以先画出“主体框架”,然后再去考虑一些细节要求。(3)FA的状态具有一定的记忆功能,不同的状态对应于不同的情况。如果有无穷种情况需要记忆,则无法构造出相应的FA。如{0n1n|n≥1}。DFA应用:文本匹配DFA应用:文本匹配非确定的有限自动机FA与DFA的比较NFA的形式定义扩展转换函数NFA接受的语言NFA与DFA的等价性NFA与DFA等价是指两种模型识别相同的语言类(正则语言)。对于任意给定的DFA,存在一个NFA与之等价;对于任意给定的NFA,存在一个DFA与之等价。DFA本身就是一种NFA,所以,要证明DFA与NFA等价,只需证明对于任意给定的NFA,存在一个DFA与之等价。证明的方法是,先根据给定的NFA构造一个DFA,然后证明两者等价。NFA与DFA等价的证明(1)NFA与DFA的差异:NFA可以进入若干个状态(状态集合),而DFA只能进入一个唯一的状态。证明思路:将NFA进入的状态集合看作DFA的一个“综合状态”,从而在NFA和DFA的状态之间建立联系。NFA与DFA等价的证明(2)带空移动的有穷状态自动机问题:1、构造一个NFAM,使得L(M)={0n1m2k|n,m,k≥1}。2、构造一个NFAM,使得L(M)={0n1m2k|n,m,k≥0}。ε-NFA的形式定义扩展转换函数转换函数之间的区别ε-NFA接受的语言ε-NFA与DFA等价ε-NFA与NFA更类似,而NFA与DFA等价,所以只需证明ε-NFA与NFA等价。ε-NFA是在NFA中扩充了空移动,所以任意的NFA都可以看作是不带空移动的ε-NFA,即NFA接受的语言类ε-NFA也都能接受。所以,要证明ε-NFA与NFA等价,只需要再证明ε-NFA接受的语言类NFA也都能接受,即对于任意给定的ε-NFA,存在一个NFA与之等价。证明的方法是,先根据给定的NFA构造一个DFA,然后证明两者等价。ε-NFA与NFA等价的证明(1)ε-NFA与NFA的差异:ε-NFA包含空移动;除了ε句子之外,空移动不会影响句子本身。证明思路:用NFA的非空移动去代替ε-NFA的一系列空移动和非空移动,从而在ε-NFA和NFA之间建立联系。ε-NFA与NFA等价的证明(2)FA是正则语言的识别器FA与正则文法具有等价性。FA接受的语言是正则语言。即对于任意DFAM,存在正则文法G,使得L(G)=L(M)。正则语言可以由FA接受。即对于任意RGG,存在FAM,使得L(M)=L(G)。定理1:对于任意正则语言L,都有一个右线性文法G=(V,T,P,S),使得L=L(G),而且,除空产生式外,每个产生式的右部有且仅有一个终极符号。正则文法产生句子的过程—举例RGG:S→0|0A|1B,A→0|0A|1B,B→1|0C|1A,C→0B|1C。G产生句子101010的过程如下:S⇒1B使用产生式S→1B⇒10C使用产生式B→0C⇒101C使用产生式C→1C⇒1010B使用产生式C→0B⇒10101A使用产生式B→1A⇒101010使用产生式A→0正则文法产生句子的过程—分析L中的任意一个句子a1a2…an在推导中有如下特性:(1)从G的开始符号S开始,除了空语句外,其他每个句型中有且仅有一个语法变量,而且此语法变量总是句型的尾字符。因此,句型中的终极符号是依据它被推导出来的先后顺序依次排列的。(2)G中的每步推导产生且仅能产生一个终极符号:第i步产生终极符号ai。(3)使用形如A→aB的产生式的推导,相当于是变量A产生出aB,而B接下去实现后续字符的产生。(4)使用形如A→a的产生式的推导,相当于是变量A产生出a后,整个推导就结束了。自动机识别句子的过程-举例对比FA接受的语言是正规语言-证明FA接受的语言是正则语言-举例上面自动机等价的正则文法为:q0→0q1|1qt|2qtq1→0q1|1q2|2qtq2→0qt|1q2|2q3|2q3→0qt|1qt|2q3|2qt→0qt|1qt|2qtqt一旦在句型中出现就永远无法消去,所以不可能产生句子,也就是qt对语言没有贡献,可以删除。那么,文法简化为:q0→0q1q1→0q1|1q2q2→1q2|2q3|2q3→2q3|2FA与左线性文法左线性文法G:E→A0|B1A→1|C1B→0|C0C→B0|A1左线性文法的规约过程中,处理字符的顺序正好是字符在句子中出现的顺序。G对句子1101的规约过程如下:1101⇐A101使用产生式A→1⇐C01使用产生式C→A1⇐B1使用产生式B→C0⇐E使用产生式E→B1与FA的关系:–G中形如A→Ba的产生式对应于FA的状态转移δ(B,a)=A;–G中形如A→a的产生式对应于FA的状态转移δ(Z,a)=A,Z是新引入的开始状态;–G的开始符号对应于FA的终止状态。根据FA构造左线性文法构造产生式。可依照下面两条规则进行:•如果δ(A,a)=B,则有产生式B→Aa。•如果δ(A,a)=B,且A是开始状态,则有产生式B→a。开始符号。可依照下面的规则进行:•如果FA只有一个终止状态,那么该状态对应的变量就是开始符号。•如果FA有多个终止状态,那么需要添加一个新符号Z作为开始符号,并加入相应产生式,使S能完成所有终止符号的作用。例如,E为一个终止状态,且有产生式E→Aa,那么要加入产生式Z→Aa。去掉无用的产生式。预处理:(1)删除DFA的陷阱状态(包括与之相关的弧)。(2)在图中添加一个识别状态(对应文法的开始状态)。(3)“复制”所有原来到达终止状态的弧,使它从原来的起点出发,到达新添加的识别状态。FA的一些变形双向有穷状态自动机–确定的双向有穷状态自动机(2DFA)–不确定的双向有穷状态自动机(2NFA)带输出的有穷状态自动机–Moore机:输出对应于状态–Mealy机:输出对应于移动确定的双向有穷状态自动机2DFA不确定的双向有穷状态自动机2DFAMoore机Mealy机注意:Moore机的输出只与当前状态有关,而Mealy机的输出则与状态及输入符号同时相关。