编译原理学习笔记（三）
1、正则表达式是一种用来描述正则语言的更紧凑的表示方法
2、正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式r定义（表示）一个语言，记为L（r）。这个语言也是根据r的子表达式所表示的语言递归定义的
3、正则表达式的定义：
是一个RE，L(
)={
}
如果a属于，则a是一个RE，L(a)={a}
假设r和s都是RE，表示的语言分别是L(r)和L(s)，则
r|s是一个RE，L(r|s)=L(r)UL(s)
rs是一个RE，L(rs)=L(r)L(s)
r*是一个RE，L(r*)=(L(r))*
(r)是一个RE，L((r))=L(r)
运算的优先级：*、连接、|5
4、可以用RE定义的语言叫做正则语言或正则集合
5、RE的代数定律（略）
6、正则文法与正则表达式等价：
对于任何正则文法G，存在定义同意语言的正则表达式r
对任何正则表达式r，存在生成同一语言的正则文法G
（二）正则定义1、正则定义是具有如下形式的定义序列：
d1->r1
d2->r2
...
dn->rn
其中：
每一个di都是一个新符号，它们都不在字母表sigma中，而且各不相同
每个ri是字母表sigmaU{d1,d2,...,di-1}上的正则表达式
例子：略
（三）有穷自动机1、有穷自动机是对一类处理系统建立的数学模型。这类系统具有一系列离散的输入输出信息和有穷数目的内部状态（状态：概括了对过去输入信息处理的状况）。系统著需要根据当前所处的状态和当前勉励的输入信息就可以决定系统的后记行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变。
2、FA模型：输入带、读头、有穷控制器
3、FA的表示：转换图（结点（初始状态、终止状态）、带标记的有向边）
4、FA定义（接收）的语言
5、有一个有穷自动机M接收的所有串构成的集合称为是该FA定义（或接收）的语言，记为L(M)
6、最长子串匹配原则
（四）有穷自动机的分类1、确定的FA（DFA）、非确定的FA（NFA）
2、确定的有穷自动机（DFA）
M=(S,SIGMA,DELTA,s0,F)
S:有穷状态机
SIGMA:输入字母表
DELTA:转换函数，将SxSIGMA映射到S的转换函数
s0:开始状态
F:接收状态（终止状态）
一个有穷自动机可以用转换图或转换表来表示
3、非确定的有穷自动机（NFA）
和确定xxx的区别是，沿着标记为a的边所能到达的状态可能有多个
4、DFA和NFA的等价性
5、正则表达式和有穷自动机（FA）是等价的
6、正则文法和正则表达式是等价的
7、带有“空边”的NFA
8、带有空边的NFA和不带空边的NFA具有等价性
9、NFA直观，DFA计算机实现更容易
10、DFA的算法实现（略）
（五）正则表达式到有穷自动机1、RE->NFA->DFA
2、根据RE构造NFA（空 对应的NFA、字母表SIGMA中的符号a对应的NFA、r=r1r2对应的NFA、r=r1|r2、r的克林闭包）
（六）从NFA到DFA的转换1、DFA的每个状态都是由NF中的状态构成的集合，即NFA状态集合的一个子集
2、转换例子（略？）
3、子集构造法
（七）识别单词的DFA作者：乘风御浪
