唉，不想学习，老是想起别的事情
这篇博客讲的是正规式和有限自动机的等价性，为NFA写出等价的正规式，为一个正规式构造等价的NFA
有了NFA与正规式的关系，就把正规式和前面所述串接起来了总而言之，状态图，正规式/正规集，有限自动机都是同种东西的不同形式正规集是实在存在的编程语言的单词集合，正规式是单词集合的抽象描述，计算机难以理解正规式，或者说正规式的概念难以映射到计算机上，所以借助有限自动机实现正规式，而有限自动机又可以用状态转移图形象地描述出来go
正规式 r 与有限自动机 M 等价：L(r） = L(M)，正规式对应的正规集与FA识别的字的全体是相等的
定理：对任何FA M，都存在一个正规式 r，使得L(r）= L(M)定理：对于任何正规式 r，都存在一个FA M，使得L(M)=L(r）
广义的状态转换图，弧上可以是正规式对待任何NFA M，在状态转换图上加进新的初态X，用 ε弧 连接原先的初态；添加新的终态结点Y，用 ε弧 将原先的终态与Y连接
（改造后的NFA只有一个初态和一个终态，最后构造出的正规式也会合并为一个）
使用一下三条规则，逐步消去结点，直到只剩下X、Y结点
不难看出，以上变换都是等价变换最后，X到Y的弧上的正规式就是与该FA等价的正规式
为什么FA弧上可以是正规式？因为正规式和FA（NFA（DFA））是等价概念，弧上的正规式即是一个FA，作为整个FA的一个子状态机（像是一种简写）
这里有一个更严格的定理对于 Σ 上的正规式 r，都存在一个NFA M，使L(M)=L(r），并且 M 只有一个初态和一个终态，且没有从终态出发的弧
这个定理更加严苛，证明了这个定理，即证明了前述定理
下面给出一个严格的数学证明
对给定正规式r中的运算符数目进行归纳
假设结论对于运算符数目少于 k(k>=1) 的正规式成立，证明结论对于运算符数目为 k 的正规式成立证明：当 r 中含有 k 个运算符时，r 有三种情况
分别对这三种情况进行证明
这样构造的NFA M 就把 M1 和 M2 并联起来，L(M) = L(M1) ∪ L(M2) = L(r1) ∪ L(r2) = L(r1|r2) = L(r）
这样构造的NFA M 就把 M1 和 M2 串联起来，L(M) = L(M1)L(M2) = L(r1)L(r2) = L(r1·r2) = L(r）
这样构造的NFA M 就实现了 M1 的任意次重复L(M) = L(M1)* = L(r1)* = L(r1*) = L(r）