编译原理复习提纲整理 - 图文

再用正规式表达出来，才能继续做后面的步骤。

ε所对应的正规集为{ε}

6.简述有限自动机NFA和DFA的定义与区别

NFA代表非确定的有限自动机；DFA代表确定的有限自动机

所谓的有限自动机，其实他并不代表任何实体的机器，只是一种数学模型而已。就像函数、数列是一种数学模型一样。函数通过函数表达式实现他的功能：你给他一个自变量，他能根据表达式求出因变量的值。而有限自动机是通过状态转换图来实现功能，你给他一个初始状态和一个输入符号，他能根据你输入的这个符号将原状态转换到另一个状态，用他来模拟计算机的识别功能。

下面简单介绍一下DFA（确定的有限自动机）的五元式表示法：(重要)

定义：一个确定有限自动机（DFA）M是一个五元式： M = (S, ∑, f, s0, F)，其中

1) S是一个有限的状态集合，它的每个元素我们称为一个状态 2) ∑是一个有穷的输入符号的字母表，它的每个元素我们称为一个输入字符

3) f是从 S×∑ →S的单值部分映射

4) s0是S的一个元素，为初始状态，它是唯一的 5) 状态集合F是终止状态的集合，它是S的子集(可空)

一个非确定有限自动机（NFA）M是一个五元式 M = (S, ∑, f, S0, F)，其中

⑴S是一个有限的状态集合，它的每个元素我们称为一个状态

⑵∑是一个有限的输入符号的字母表，它的每个元素我们称为一个输入字符

⑶f是从S×∑*→2S 的部分映射，其中，2S表示S的幂集合（所有S的子集组成的集合）（f是非单值的?M是非确定）

⑷状态集合S0是初始状态集合，它是S的子集 ⑸状态集合F是终止状态的集合，它是S的子集

注：DFA和NFA的区别在于（3）和（4），其他几点都差不多，这是有可能出简答题的，大家要记住他们的区别和联系

7.DFA的识别功能

对于∑*中任何字α，如果存在一条从初态结点到某个终态结点的道路，这条路上所有的标识符连成的字等于α ，则α可被DFA M所识别(接受，读出)

若M的某些结点既是初态结点又是终态结点，或者存在一条从某初态结点到某个终态结点的ε通路，那么空字ε可为M所识别

8.状态转换图的分裂规则（大题步骤）

例子：(这里Y有两个圈圈代表他是最终状态的点)

划到最后要求每条弧上都只有一个字母或者数字

9.ε_CLOSURE(I) 和Ia =ε_CLOSURE(J)的构造方法（大题步骤）

这里先需要了解几个定义

我们假设有某个状态集I，这个集合中含有不同的状态。 定义1 状态集I的a弧转换：move( I, a )

? 是一个状态集，是从I中的状态出发经过一条a弧到达的状态的全体。 定义2 状态集I的ε(空字)闭包：ε_CLOSURE( I ) 是一个状态集，由两部分组成:

? 状态集I中的所有原状态。

? 从I中的状态出发经过任意条ε弧，所能到达的状态的全体。

定义3 Ia =ε_CLOSURE( move( I, a ) ) ? 是一个状态集。 下面给出一个实例：

例：有如下一个状态转换图假定 I={1, 2}，求Ia = ？

J=move(I,a)={5,4,3}

Ia=ε_CLOSURE(J) = {5,4,3,6,2,7,8}

（即先做a弧转换，将求得的状态再求空字闭包）

本知识点旨在让大家掌握在知道了I这个状态集合后，怎样求Ia

10.如何用子集法将非确定的有限自动机确定化（大题步骤）

方法：先画一张表

I Ia Ib … ε_CLOSURE(S0) A B C B D E … C 1.这张表的首行上首列上固定是大写字母I

F G 2.表格后面有几列，取决于这个有限自动机的输入符号数量，有几个输入符号就有几列，这里假设Ia Ib 的下标a b代表这个有限自动机的输入符号

3.第二行的第一列也是固定的，S0代表的是这个有限自动机的初始状态,即求S0的空字闭包，我们假设求出来的状态集合是A

4.将A所对应的Ia Ib 分别求出来，我们假设是B和C

5.如果B和C都分别于A不同，需要将B，C作为新的状态集合加入到第一列中