② 正规式转换为正规文法
将正规式 r 转换为正规文法 G,核心是将正规式拆分为正规文法的多个产生式,这是一个由一到多的过程。...正规文法最终必须有一个开始符号,于是我们选定 S 作为开始符号,令 S → r,然后逐步对 r 进行拆分,生成多个产生式。...ab|a)S,S → ε
S → AS,A → (ab|a),S → ε
S → AS,A → ab,A → a,S → ε
S → AS,A → aB,B → b,A → a,S → ε
这种写法是错误的...⑤ 等价状态的合并
在同一个集合中的状态都是等价的,要考虑将它们进行合并。还是来看这张图:
image.png
首先,6 和 7 是等价的,考虑去掉 7 与它的各条线。...但是为什么一开始会觉得 3 和 4 应该在一起呢?是因为我们当时先检查的是非终态集合,没有检查终态集合,终态集合在那个时候只有 {5,6,7} ,是暂时还没有划分的。