形式语言与自动机理论

1、第2章 有穷状态自动机,康慕宁 西北工业大学计算机学院,语言的识别,给定一个正规文法G，相应的正则语言L(G)就给定了。任给一个字符串w，w是不是语言L(G)的句子。即S* w能否成立。 例：SaA|aB, AaA|c, BaB|d，字符串aaad是该文法所定义语言的句子吗？ 问题：推导和归约中的回溯问题给系统的效率产生极大的影响。 解决方法：从识别的角度去考虑问题，设计有穷自动机系统来识别语言。,有穷状态自动机,有穷状态自动机是具有离散输入和输出的系统的一种数学模型。其主要特点有以下几个方面： (1)系统具有有穷个状态，不同的状态代表不同的意义。按照实际的需要，系统可以在不同的状态下完成规定

2、的任务。 (2)我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。 (3)系统在任何一个状态下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。 (4)系统中有一个状态，它是系统的开始状态。 (5)系统中还有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子。,有限状态自动机的物理模型,形式定义,举例,状态转移（换）图,状态转换表,状态转换表是一个二维表，左边第二列列出有穷状态自动机的所有状态，并在第一列中标出开始状态和终止状态，上边第一行列出所有的输入字符，中间的方格内是该行所对应状态下输入该列所对应字

3、符后转换到的新状态。,扩展转换函数,有限自动机接受的语言,构造DFA实例（1）,DFA实例3,几点注意,本例中有以下几点值得注意： (1)当FA一旦进入状态qt，它就无法离开此状态。所以qt相当于一个陷阱状态。 (2)在构造一个识别给定语言的FA时，用画图的方式比 较方便、直观。可以先画出“主体框架”，然后再去考 虑一些细节要求。 (3)FA的状态具有一定的记忆功能，不同的状态对应于 不同的情况。如果有无穷种情况需要记忆，则无法构 造出相应的FA。如0n1n|n1。,DFA应用：文本匹配,DFA应用：文本匹配,非确定的有限自动机,FA与DFA的比较,NFA的形式定义,扩展转换函数,NFA接受的

4、语言,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的状态之间建立联系

5、。,NFA与DFA等价的证明(2),带空移动的有穷状态自动机,问题： 1、构造一个NFA M，使得L(M)=0n1m2k| n,m,k1。 2、构造一个NFA M，使得L(M)=0n1m2k| n,m,k0。,-NFA的形式定义,扩展转换函数,转换函数之间的区别,-NFA接受的语言,-NFA与DFA等价,-NFA与NFA更类似，而NFA与DFA等价，所以只需证明-NFA与NFA等价。 -NFA是在NFA中扩充了空移动，所以任意的NFA都可以看作是不带空移动的-NFA，即NFA接受的语言类-NFA也都能接受。所以，要证明-NFA与NFA等价，只需要再证明-NFA接受的语言类NFA也都能接受，即对

6、于任意给定的-NFA，存在一个NFA与之等价。 证明的方法是，先根据给定的NFA构造一个DFA，然后证明两者等价。,-NFA与NFA等价的证明（1）,-NFA与NFA的差异： -NFA包含空移动； 除了句子之外，空移动不会影响句子本身。 证明思路： 用NFA的非空移动去代替-NFA的一系列空移动和非空移动，从而在-NFA和NFA 之间建立联系。,-NFA与NFA等价的证明（2）,FA是正则语言的识别器,FA与正则文法具有等价性。 FA接受的语言是正则语言。即对于任意DFA M，存在正则文法G，使得L(G)=L(M)。 正则语言可以由FA接受。即对于任意RG G，存在FAM，使得L(M)=L(G

7、)。 定理1：对于任意正则语言L，都有一个右线性文法G=(V,T,P,S)，使得L=L(G)，而且，除空产生式外，每个产生式的右部有且仅有一个终极符号。,正则文法产生句子的过程举例,RG G： S0|0A|1B，A0|0A|1B，B1|0C|1A，C0B|1C。 G产生句子101010的过程如下： S1B 使用产生式S1B 10C 使用产生式B0C 101C 使用产生式C1C 1010B 使用产生式C0B 10101A 使用产生式B1A 101010 使用产生式A0,正则文法产生句子的过程分析,L中的任意一个句子a1a2an在推导中有如下特性： (1) 从G的开始符号S开始，除了空语句外，其他

8、每个句型中有且仅有一个语法变量，而且此语法变量总是句型的尾字符。因此，句型中的终极符号是依据它被推导出来的先后顺序依次排列的。 (2) G中的每步推导产生且仅能产生一个终极符号：第i步产生终极符号ai。 (3) 使用形如AaB的产生式的推导，相当于是变量A产生出aB，而B接下去实现后续字符的产生。 (4) 使用形如Aa的产生式的推导，相当于是变量A产生出a后，整个推导就结束了。,自动机识别句子的过程-举例,对比,FA接受的语言是正规语言证明,FA接受的语言是正则语言-举例,上面自动机等价的正则文法为： q00q1 | 1qt | 2qt q10q1 | 1q2 | 2qt q20qt | 1q

9、2 | 2q3 | 2 q30qt | 1qt | 2q3 | 2 qt0qt | 1qt | 2qt,qt一旦在句型中出现就永远无法消去，所以不可能产生句子，也就是qt对语言没有贡献，可以删除。那么，文法简化为： q00q1 q10q1 | 1q2 q21q2 | 2q3 | 2 q32q3 | 2,FA与左线性文法,左线性文法G： E A0|B1 A 1|C1 B 0|C0 C B0|A1 左线性文法的规约过程中，处理字符的顺序正好是字符在句子中出现的顺序。G对句子1101的规约过程如下： 1101A101 使用产生式A1 C01 使用产生式CA1 B1 使用产生式BC0 E 使用产生式E

10、B1 与FA的关系： G中形如ABa的产生式对应于FA的状态转移(B,a)=A； G中形如Aa的产生式对应于FA的状态转移(Z,a)=A，Z是新引入的开始状态； G的开始符号对应于FA的终止状态。,根据FA构造左线性文法,构造产生式。可依照下面两条规则进行： 如果(A,a)=B，则有产生式BAa。 如果(A,a)=B，且A是开始状态，则有产生式Ba。 开始符号。可依照下面的规则进行： 如果FA只有一个终止状态，那么该状态对应的变量就是开始符号。 如果FA有多个终止状态，那么需要添加一个新符号Z作为开始符号，并加入相应产生式，使S能完成所有终止符号的作用。例如，E为一个终止状态，且有产生式EAa，那么要加入产生式ZAa。 去掉无用的产生式。 预处理： (1)删除DFA的陷阱状态(包括与之相关的弧)。 (2)在图中添加一个识别状态(对应文法的开始状态)。 (3)“复制”所有原来到达终止状态的弧，使它从原来的起点出发，到达新添加的识别状态。,FA的一些变形,双向有穷状态自动机 确定的双向有穷状态自动