概念记号有字母表中符号组成有限长度序列记号s长度记为.doc

概念 记号 有字母表中的符号组成的有限长度的序列。记号s的长度记为
概念
记号
有字母表中的符号组成的有限长度的序列。记号s的长度记为|s|。长度
为0的记号称为空记号，记为ε。
有限自动机(Finite State Automaton)
为研究某种计算过程而抽象出的计算模型。拥有有限个状态，根据不同的
输入每个状态可以迁移到其他的状态。
非确定有限自动机(Nondeterministic Finite Automaton)
简称NFA，由以下元素组成:
1. 有限状态集合S;
2. 有限输入符号的字母表Σ;
3. 状态转移函数move;
4. 开始状态 sSUB{0};
5. 结束状态集合F，F ? S。
自动机初始状态为sSUB{0}，逐一读入输入字符串中的每一个字母，根据
当前状态、读入的字母，由状态转移函数move控制进入下一个状态。如
果输入字符串读入结束时自动机的状态属于结束状态集合F，则说明该自
动机接受该字符串，否则为不接受。
确定有限自动机(Deterministic Finite Automaton)
简称DFA，是NFA的一种特例，有以下两条限制:
1. 对于空输入ε，状态不发生迁移;
2. 某个状态对于每一种输入最多只有一种状态转移。
将正则表达式转换为NFA(Thompson构造法) 算法
算法1 将正则表达式转换为NFA(Thompson构造法)
输入 字母表Σ上的正则表达式r
输出 能够接受L(r)的NFA N
方法 首先将构成r的各个元素分解，对于每一个元素，按照下述规则1和规则2生成NFA。 注意:如果r中记号a出现了多次，那么对于a的每次出现都需要生成一个单独的NFA。
之后依照正规表达式r的文法规则，将生成的NFA按照下述规则3组合在一起。 规则1 对于空记号ε，生成下面的NFA。
规则2 对于Σ的字母表中的元素a，生成下面的NFA。
规则3 令正规表达式s和t的NFA分别为N(s)和N(t)。 a) 对于s|t，按照以下的方式生成NFA N(s|t)。
b) 对于st，按照以下的方式生成NFA N(st)。
c) 对于s*，按照以下的方式生成NFA N(s*)。
d) 对于(s)，使用s本身的NFA N(s)。
性质
算法1生成的NFA能够正确地识别正则表达式，并且具有如下的性质: 1. N(r)的状态数最多为r中出现的记号和运算符的个数的2倍。
2. N(r)的开始状态和结束状态有且只有一个。 3. N(r)的各个状态对于Σ中的一个符号，或者拥有一个状态迁移，或者拥有
最多两个ε迁移。
示例
利用算法1，根据正则表达式 r=(a|b)*abb 可以生成以下的NFA。
将NFA转化为DFA
算法
使用以下的算法可以将NFA转换成等价的DFA。 算法2 将NFA转化为DFA
输入 NFA N
输出 能够接受与N相同语言的DFA D
方法 本算法生成D对应的状态迁移表Dtran。DFA的各个状态为NFA的状态集合，
对于每一个输入符号，D模拟N中可能的状态迁移。 定义以下的操作。
操作 说明
s出发，仅通过