利用有限自动机分析正则表达式
1、概念
(1)记号
有字母表中的符号组成的有限长度的序列。记号s的长度记为|s|。
长度为0的记号称为空记号，记为ε。
(2)FA
有限自动机(Finite State Automaton) 为研究某种计算过程而抽象出的计算模型。 拥有有限个状态，根据不同的输入每个状态可以迁移到其他的状态。
非确定有限自动机(Nondeterministic Finite Automaton) 简称NFA，由以下元素组成：
有限状态集合S；
有限输入符号的字母表Σ；
状态转移函数δ；
开始状态 s0；
结束状态集合F，F ∈ S。
自动机初始状态为s0，逐一读入输入字符串中的每一个字母，根据当前状态、读入的字母， 由状态转移函数δ控制进入下一个状态。如果输入字符串读入结束时自动机的状态属于结束状态集合F， 则说明该自动机接受该字符串，否则为不接受。
确定有限自动机(Deterministic Finite Automaton) 简称DFA，是NFA的一种特例，有以下两条限制：
对于空输入ε，状态不发生迁移；
某个状态对于每一种输入最多只有一种状态转移。
2、将正则表达式转换为NFA(Thompson构造法)
算法: 将正则表达式转换为NFA(Thompson构造法)
输入: 字母表Σ上的正则表达式r
输出: 能够接受L(r)的NFA
方法: 首先将构成r的各个元素分解，对于每一个元素，按照下述规则1和规则2生成NFA。
注意: 如果r中记号a出现了多次，那么对于a的每次出现都需要生成一个单独的NFA。 之后依照正则表达式r的文法规则，将生成的NFA按照下述规则3组合在一起。
规则1: 对于空记号ε，生成下面的NFA。
规则2: 对于Σ的字母表中的元素a，生成下面的NFA。
规则3: 令正则表达式s和t的NFA分别为N(s)和N(t)。
①对于s|t，按照以下的方式生成NFA  N(s|t)。
②对于st，按照以下的方式生成NFA  N(st)。
③对于s*，按照以下的方式生成NFA N(s*)。
④对于(s)，使用s本身的NFA  N(s)。
[例]根据正则表达式 r=(a|b)*abb 可以生成以下的NFA。
3、将NFA转化为DFA
算法
使用以下的算法可以将NFA转换成等价的DFA。
算法2: 将NFA转化为DFA
输入: NFA N
输出: 能够接受与N相同语言的DFA D
方法: 本算法生成D对应的状态迁移表Dtran。DFA的各个状态为NFA的状态集合， 对于每一个输入符号，D模拟N中可能的状态迁移。
定义以下的操作。
操作
说明
ε-closure(s)
从NFA的状态s出发，仅通过ε迁移能够到达的NFA的状态集合
ε-closure(T)
从T中包含的某个NFA的状态s出发，仅通过ε迁移能够到达的NFA的状态集合
正则化和泛化move(T, a)
从T中包含的某个NFA的状态s出发，通过输入符号a迁移能够到达的NFA的状态集合
令 Dstates 中仅包含ε-closure(s), 并设置状态为未标记;
while Dstates中包含未标记的状态T do
begin
  标记T;
  for 各输入记号a do
  begin
    U := ε-closure(move(T, a));
    if U不在Dstates中 then
      将 U 追加到 Dstates 中，设置状态为未标记;
    Dtrans[T, a] := U;
  end
end
ε-closure(T)的计算方法如下：
将T中的所有状态入栈;
设置ε-closure(T)的初始值为T;
while 栈非空 do
begin
  从栈顶取出元素t;
  for 从t出发以ε为边能够到达的各个状态u do
    if u不在ε-closure(T)中 then
    begin
      将u追加到ε-closure(T)中;
      将u入栈;
    end
end
示例
将上面生成的NFA转化为DFA。
最初，Dstates内仅有ε-closure(0) = A = {0, 1, 2, 4, 7}。然后对于状态A，对于输入记号a，计算 ε-closure(move(A, a)) =ε-closure(move({0, 1, 2, 4, 7}, a)) = ε-closure({3, 8}) = {1, 2, 3, 4, 6, 7, 8}， 即 B={1, 2, 3, 4, 6, 7, 8}, Dtran[A, a]=B。 对于状态A，由输入记号b能够到达的仅有4->5，因此 C = ε-closure({5}) = {1, 2, 4, 5, 6, 7}， 即 Dtran[A, b] = C。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。