RE描述了一个定义在某个字母表Σ上的字符串集合L,并且空字符串ε也属于L集合.形式化的定义并不好理解,但是相对其他非形式化的定义来说更加简洁和准确.这里的正则表达式和平常所用的处理字符串的正则表达式是同一个,但是这里更加简单.这里的RE只有三个基本的操作:
(1)选择 取并集.符号:|. 比如两个字符串集合R和S的选择操作,记作R|S.
(2)连接 字符串之间的拼接.两个字符串集合R和S的连接为RS.
(3)闭包 符号:* 字符串集合R的闭包R*是指把R与自身连接零次或者多次形成的所有集合的并集.
由这几个简单的操作可以得到我们平常接触的正则表达式的所有扩展.
我说的时候喜欢加上状态两个字,因为FA的关键动作就是状态间的转移.FA有一个状态集S,对于每一个输入都会让FA的状态进行转移.如果能够从起始状态转移到接受状态,那么输入序列就被识别了.不存在空字符串ε的状态转移.
非确定性有限状态自动机(Non-deterministic Finite Automaton,NFA).对于同一输入转移到多个不同的状态或者存在空字符串ε的状态转移的FA.
确定性有限状态自动机(Deterministic Finite Automaton,DFA).对于任何确定的输入都只有唯一确定的转移且不存在空字符串ε的状态转移的FA.
上面描述的RE的基本操作的简单NFA:
NFA到DFA 是对NFA的简化过程.
NFA到DFA的子集构造算法(The Subset Construction):从将初始状态划分为一个初始状态子集开始,构造状态子集(经过零个或多个空字符串ε转移到的状态和已在子集中的状态都是构造的新的状态子集),存在c属于字母表Σ,经过一个c的转移(必须有c的转移),能够使得从状态子集ni转移到状态子集nj,则在DFA中有在c的输入下从状态子集ni转移到状态子集nj的转移.最后不再有新的状态子集出现.根据状态子集的转移依次构造DFA.
最小化DFA用到的是等价状态集合的划分来构建.一开始只有两个状态集,一个接受状态集合,一个非接受状态集合.对于每一个状态集合Sp,如果存在c属于字母表Σ,使得Sp中的状态转移到不同的状态集合(包括没有转移的空状态集合),则拆分Sp,使得拆分后的状态集合中的每一个状态不可能转移到不同的状态集合.其中状态集合之间的转移构成最小化DFA中的转移.
构造正规式1(0|1)*101相应的DFA。
先构造NFA
确定化 0 1 X A A A AB AB AC AB AC A ABY ABY AC AB
重新命名，令AB为B。
DFA最小化
首先得到两个子集K1 = {1,2,3} 和 K2 = {4}。
考察K1：由于{1,2,3}a = {1,2，4} K1，也 K2，所以K1可需要被分割。
又因为{1,3}a = {2}，{1,3}b = {3}，
所以将原状态集合分割成以下子集：K11={2}，K12={1，3}。
目前划分得到的子集为：K11={2}，K12={1，3}，K2 = {4}。
考察K12：{1,3}a = {2} K1，{1,3}b = {3}K1，所以K1不可再分割
扩展资料
词汇分析法的条件
1、输入缓冲区
成对且对半互补的输入缓冲区模式。
n: 取2的整次幂；每个半区的末尾设置标志“ eof ” 表示读入该半区的源程序的结束；
B：单词w开始指针； F：扫描w的指针；
两个缓冲区的输入模式
2、预处理程序： （作用）
1） 减少内存空间占用；
2） 减轻扫描器实质性处理的负担；
3、预处理程序主要任务：
1） 滤掉源程序中的非单词成分(如无用空格；换行符等)；
2） 其他的预处理工作:滤掉注释；宏替换；文件包含的嵌入；条件编译的嵌入。
