本项目经测试在以下环境下可以正常运行：

• macOS Mojave 10.14.2
• Python 3.7.1
• graphviz: stable 2.40.1 对应的Python包版本为0.13

主要参考：https://cn.charlee.li/parse-regex-with-dfa.html

• 输入: 字母表Σ上的正则表达式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)。

    1. 对于s|t，按照以下的方式生成NFA N(s|t)。

       

    2. 对于st，按照以下的方式生成NFA N(st)。

       

    3. 对于s*，按照以下的方式生成NFA N(s*)。

       

    4. 对于(s)，使用s本身的NFA N(s)。

• 代码实现则使用递归的方法，将N(S)看做一个函数或者说子正则式，向下递归。对于返回的值再根据规则3连接在一起即可

• 输入: 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

算法1生成的NFA能够正确地识别正则表达式，并且具有如下的性质：

1. N(r)的状态数最多为r中出现的记号和运算符的个数的2倍。
2. N(r)的开始状态和结束状态有且只有一个。
3. N(r)的各个状态对于Σ中的一个符号，或者拥有一个状态迁移，或者拥有最多两个ε迁移。

这里我们利用：https://cyberzhg.github.io/toolbox/nfa2dfa，来检验产生的dfa是否正确

• 测试abc*

• 测试 ((ab)*|b)*

• 测试abcdefghijk