形式语言与自动机理论.ppt

《形式语言与自动机理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第2章有穷状态自动机康慕宁西北工业大学计算机学院语言的识别给定一个正规文法G，相应的正则语言L(G)就给定了。任给一个字符串w，w是不是语言L(G)的句子。即S⇒*w能否成立。例：S→aA

2、aB,A→aA

3、c,B→aB

4、d，字符串aaad是该文法所定义语言的句子吗？问题：推导和归约中的回溯问题给系统的效率产生极大的影响。解决方法：从识别的角度去考虑问题，设计有穷自动机系统来识别语言。有穷状态自动机有穷状态自动机是具有离散输入和输出的系统的一种数学模型。其主要特点有以下几个方面：(1)系统具有有穷个状态，不同的状态代

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

6、有状态，并在第一列中标出开始状态和终止状态，上边第一行列出所有的输入字符，中间的方格内是该行所对应状态下输入该列所对应字符后转换到的新状态。扩展转换函数有限自动机接受的语言构造DFA实例（1）DFA实例3几点注意本例中有以下几点值得注意：(1)当FA一旦进入状态qt，它就无法离开此状态。所以qt相当于一个陷阱状态。(2)在构造一个识别给定语言的FA时，用画图的方式比较方便、直观。可以先画出“主体框架”，然后再去考虑一些细节要求。(3)FA的状态具有一定的记忆功能，不同的状态对应于不同的情况。如果有无穷种情况需要记忆

7、，则无法构造出相应的FA。如{0n1n

8、n≥1}。DFA应用：文本匹配DFA应用：文本匹配非确定的有限自动机FA与DFA的比较NFA的形式定义扩展转换函数NFA接受的语言NFA与DFA的等价性NFA与DFA等价是指两种模型识别相同的语言类（正则语言）。对于任意给定的DFA，存在一个NFA与之等价；对于任意给定的NFA，存在一个DFA与之等价。DFA本身就是一种NFA，所以，要证明DFA与NFA等价，只需证明对于任意给定的NFA，存在一个DFA与之等价。证明的方法是，先根据给定的NFA构造一个DFA，然后证明两者等价

9、。NFA与DFA等价的证明(1)NFA与DFA的差异：NFA可以进入若干个状态（状态集合），而DFA只能进入一个唯一的状态。证明思路：将NFA进入的状态集合看作DFA的一个“综合状态”，从而在NFA和DFA的状态之间建立联系。NFA与DFA等价的证明(2)带空移动的有穷状态自动机问题：1、构造一个NFAM，使得L(M)={0n1m2k

10、n,m,k≥1}。2、构造一个NFAM，使得L(M)={0n1m2k

11、n,m,k≥0}。ε-NFA的形式定义扩展转换函数转换函数之间的区别ε-NFA接受的语言ε-NFA与DFA等价ε

12、-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包含空移动；除了ε句子之外，空移

13、动不会影响句子本身。证明思路：用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)，而且，除空产生式外，每个产生式的右部有且仅有一个终极符号。

14、正则文法产生句子的过程—举例RGG：S→0

15、0A

16、1B，A→0

17、0A

18、1B，B→1

19、0C

20、1A，C→0B

21、1C。G产生句子101010的过程如下：S⇒1B使用产生式S→1B⇒10C使用产生式B→0C⇒101C使用产生式C→1C⇒1010B使用产生式C→0B⇒10101A使用产生式B→1A⇒101010使用产生式A→0正则文法产生句子的过程—分析L中的任意一个