其实很早之前就已经写了，没来得及更新。。。
- 更新了PDA（下推自动机）的实现，见
src/automata/PDA.py - 更新了CFG（上下文无关文法的实现）和LL1解析器，见
src/automata/CFG.py - 修补和优化了一些DFA,NFA实现的bug，为
NFA正则添加了正则语法[] . * +，见automata/NFA.py - 为了实现上述两个自动机，新实现了数据结构“多键字典”，可见
container/multi_key_dict.py。
- 实现了一个基于DFA的简单词法解析器，见
lexer/lexer.py。 - 在
lexer/cmm_define.py中定义了一系列词法规则，可以按需进行修改。 - 直接运行
lexer/lexer.py可对example.cmm中的文件进行词法解析。
- 基于已经实现的自动机实现语法分析器。
- 优化、重构已实现的代码。
- 补全README中对PDA、CFG、Lexer等的介绍。
最近可能没时间。。。先鸽为敬。
项目地址： https://github.com/HuiyuanYan/automaton_simulation
本项目基于《编译原理》第二版和《自动机理论、语言和计算导论》第三版，以及网络资料，实现包括DFA、NFA在内的多种自动机，使用python语言进行编程，以期加深对自动机的理解。
├─picture # 存放生成的DFA/NFA图片
├─src #存放源代码
│ ├─automata #自动机实现代码
│ └─container #使用到的其他容器实现代码
└─test #测试文件
- Python 3.9.7
- graphviz version 6.0.1
进入test文件夹执行test_all.py可运行全部测试样例。
一个确定型有穷自动机包括：
- 一个有穷的状态集合，通常记作$Q$。
- 一个有穷的输入符号集合，通常记作$\Sigma$。
- 一个转移函数，以一个状态和一个输入符号作为变量，返回一个状态。转移函数通常记作$\delta$。
- 一个初始状态，是$Q$中状态之一。
- 一个终结状态或接受状态的集合$F$。集合$F$是$Q$的子集合。
通常用五元组来讨论和表示$DFA$: $$ A=(Q,\Sigma,\delta,q_0,F)。 $$
在src\automata\DFA.py中，定义了DFA类，定义了它的各个组成：
self.__Q = [] # states
self.__alphabet = []
self.__deltas = {}
self.__q0 = '' # start state
self.__finish_states = [] # finish state可以通过接口函数add_state/add_states, set_alphabet, set_deltas/add_delta, set_q0, set_finish_states对它们分别进行设置。
DFA是通过接受状态来接受语言的，即定义$\text{DFA A}$的语言。这个语言记作$L(A)$，定义为： $$ L(A) = {w|\hat{\delta}(q_0,w) \in F} $$ 也就是说，语言$A$是让初始状态$q_0$通向接受状态之一的串$w$的集合。如果对某个$\text{DFA A}$来说$L$是$L(A)$，那么就说$L$是正则语言。
s = s0;
c = nextChar();
while(c! = eof){
s = move(s,c);
c = nxtChar();
}
if (s in F) return true;
else return false;算法实现见函数DFA.run(str)。可以通过设置参数verbose = True来打印每一步的过程。
- Example:
d = DFA()
d.add_states(['q0','q1','q2','q3'])
d.set_alphabet({'0','1'})
d.set_q0('q0')
d.set_finish_states({'q3'})
d.set_deltas({'q0':[('0','q1')],
'q1':[('1','q2')],
'q2':[('0','q3')],
})
assert d.run('010') == TrueDFA最小化对于每个DFA，求出在接受相同语言的任意DFA中具有最少状态数的等价DFA，且该最小DFA是唯一的。
算法的大致思路为：
1. 排除所有不能从初始状态到达的状态
2. 把剩下的状态划分为块，同一块中的状态都是等价的，并且不同块中的两个状态一定不等价。
排除不可达状态，可以使用深度优先遍历，从初始状态开始，找到所有可达节点，并删除不可达节点及其转移（transition）。
等价块划分采取“填表算法”（见《自动机理论、语言和计算导论》第二版P107），具体步骤为：
1. 新建一张"n*n"的表，其中n为消除不可达状态后的状态数。实际上，由于对称性，只需要使用对角线下半部分的表即可。
2.将所有状态按顺序编号0，1，2...，并对应于表的下标。
3.标记结束状态与其他状态不等价（即可区分，填对应表项为1）。
4.对表进行迭代操作，每次迭代遍历每个表项t[i][j](i<j)，若存在一个字母表中的字符c，可以将状态i，j区分，即状态i和状态j在c上转移的下一个状态被标记为不等价，那么标记t[i][j]可区分。
5.进行4中的迭代操作，直至表再无更新。
6.将表中未被标记的状态分别合并为一个状态（这里用到了并查集），重新设置状态，并根据原来的转移函数设置新转移函数。
代码见src\automata\DFA.py中DFA.minimize()函数。
通过归纳构造的方式从$\text{DFA}$构造正则表达式。
将DFA A中的每个状态编号（0，1，2，...，n）用$R_{ij}^{k}$作为正则表达式的名字，属于该正则的串$w$满足：$w$是从$A$中从状态$i$到状态$j$的路径的标记，且这条路径没有经过编号大于$k$的中间节点。
graph LR
n1((1))
n2((2,finish))
start-->n1
n1--1-->n1
n1--0-->n2
n2--0,1-->n2
例如，对于上面的DFA，$R_{12}^{(0)}=0$，即$0$这个串满足能够从状态1到状态2，且中间没有编号大于0的节点（中间不经过任何节点）。
那么最终我们需要求的DFA的正则表达式则为$R_{start_state,all_end_states}^{(n)}$，$n$为状态数，表示满足可以从开始状态到所有结束状态，中间可以经过任意节点的正则表达式。
下面为具体步骤：
归纳的基础为，当$k=0$时，由于所有状态的编号都大于等于1，所以这时对路径的限制为：路径根本没有中间状态。只有两种路径满足这样的条件：
- 从状态$i$到$j$的一条弧。
- 只包含某个顶点$i$的长度为0的路径。
当$i\not=j$时，只有情形1是可能的。检查该DFA，找到所有满足的输入符号$a_i$，使得在$a_i$上存在从$i$到$j$的转移。
-
如果不存在这样的符号，$R_{ij}^{(0)}=\empty$。
-
如果恰好有一个这样的符号$a$，则$R_{ij}^{(0)}=a$。
-
如果同时有多个符号$a_1,a_2,...,a_n$满足，则$R_{ij}^{(0)}=a_1+a_2+...+a_n$。
当$i=j$时，合法路径为长度为0的路径（不进行转移）和从$i$到其自身的环。长度为0的路径正则表达式记为$\epsilon$，环的正则表达式则根据上述规则确定。最终$R_{ii}^{(0)}=\epsilon+a_1+a_2+...+a_n$。
当$k>0$时，从$i$到$j$的路径不经过比$k$高的状态，考虑如下两种情形：
- 该路径不经过状态$k$，此时$R_{ij}^{(k)}=R_{ij}^{(k-1)}$。
graph LR
ni((i))
nj((j))
nk((k))
ni --states-->nj
- 该路径至少经过状态$k$一次。此时可以把路径分为三段：$R_{ik}^{(k-1)}$、$(R_{kk}^{(k-1)})^*(\text{表示在k处自身转移了0到多次})$、$R_{kj}^{(k-1)}$。
graph LR
ni((i))
nj((j))
nk((k))
ni --states-->nk
nk --loop-->nk
nk --states-->nj
故而有$R_{ij}^{(k-1)}=R_{ij}^{(k-1)}+R_{ik}^{(k-1)}(R_{kk}^{(k-1)})^*R_{kj}^{(k-1)}$。
最终对于所有$i$和$j$，都可以得到$R_{ij}^{(n)}$。假设状态1为初始状态，接受状态集合为${{j_0,j_1,...j_n}}$，所有表达式之和$\sum R_{1j_i}^{(n)}$即为自动机的语言。
详细代码见src\automata\DFA.py\DFA.to_regex(re)。
例子：
d = DFA_SRC.DFA()
d.set_alphabet({'0','1'})
d.add_states(['q0','q1'])
d.set_q0('q0')
d.set_finish_states({'q1'})
d.set_deltas(
{
'q0':[('0','q1'),('1','q0')],
'q1':[('0','q1'),('1','q1')]
}
)
print(d.to_regex())对于该DFA：
graph LR
n1((q0))
n2((q1,finish))
start-->n1
n1--1-->n1
n1--0-->n2
n2--0,1-->n2
输出的结果为 $$ 0+(ε+1)(ε+1)^*0+(0+(ε+1)(ε+1)^0)(ε+0+1)^(ε+0+1) $$
化简后为$10(0+1)^*$。
本功能并未实现对得到正则表达式的化简，需要自己手动进行化简。
一个$\text{NFA A}$可形式化表述为：
其中：
-
$Q$ 是一个有穷的状态集合。 -
$\Sigma$ 是一个有穷的输入符号集合。 -
$q_0$ 是初始状态，属于$Q$。 -
$F$ 是终结（或接受）状态的集合，是Q的子集合。 - 转移函数$\delta$是一个以$Q$中状态和$\Sigma$中的一个输入符号作为变量，并返回$Q$的一个子集合的函数。
同样地，在NFA.py中也保留了与DFA.py中类似的成员和接口函数。
需要注意的是，NFA.set_deltas中的参数类型与DFA中有所不同。
NFA的模拟算法为：
S = ε-closure(s0);
c = nextChar();
while (!c = eof){
S = ε-closure(move(S,c));
c = nextChar();
}
if(S ∩ F != Empty) return true;
else return false;算法实现见函数NFA.run(str)。可以通过设置参数verbose = True来打印每一步的过程
从NFA到DFA的转换，使用子集构造法来实现。算法的描述为：
Dstates = [];
Dtran = {};
Dstates.append([ε-closure(s0),unmarked]);
while there is an unmarked state T in Dstates:
Mark T;
for every ch in alphabet:
U = ε-closure( move(T,ch) );
if U not in Dstates:
U.append([Dstates,unmarked]);
Dtran[T,ch] = U;然后根据Dstates和Dtrans重新设计DFA即可。
算法实现见函数NFA.to_DFA()。
本项目还实现了从基本正则表达式（包含的运算符号有 “ | ”（或）、“ * ”（闭包）、concat（连接））到NFA的转换。
采用的算法是汤普森构造法。
具体步骤为：
1. 将输入的正则表达式转换为后缀表达式，并添加相应的连接符。（见代码NFA.regex_to_NFA().infix_to_postfix(regex)）。
2. 根据获取的后缀表达式，利用汤普森构造法构造新NFA。（包含了对各个状态重新编号的过程）
实现见代码NFA.regex_to_NFA()。
采用pygraphviz包利用grpahviz软件画图。
使用自动机下的draw方法进行调用画图。
默认存储路径为picture文件夹，可以在config.py中进行修改。
https://deniskyashif.com/2019/02/17/implementing-a-regular-expression-engine/