我需要通过将DFA（确定性有限自动机）转换为通用NFA（非确定性有限自动机）将此有限自动机转换为正则表达式。怎么应该去做呢？ NFA和DFA的状态图是否相同？
因此图中有两个DFA，因此我将展示如何依次获得每个DFA。首先，我们写下一些方程式：
(q1) = (q1)a + (q2)b + e
(q2) = (q1)b + (q2)a
现在我们可以在每个上使用规则(q) = (q)x + y <=> (q) = yx*：
(q1) = ((q2)b + e)a*
(q2) = (q1)ba*
现在我们可以替换，因为我们关心（q2）我们也可以直接得到它：
(q2) = ((q2)b + e)a*ba*
= (q2)ba*ba* + a*ba*
= a*ba*(ba*ba*)*
我们得到正则表达式a*ba*(ba*ba*)*，一目了然，似乎是正确的。我们是如何得到方程式的？对于每个州，我们写下了“到达”州的方式，并将它们与+（或，联合）相结合。我们在（q1）的等式中包括空字符串e，因为（q1）是初始状态，并且不需要消耗任何东西（最初）。
对于第二个，方程看起来像这样：
(q1) = (q3)a + e
(q2) = (q1)(a + b) + (q2)a + (q3)b
(q3) = (q2)b
我们可以使用我们的规则来消除（q2）的自引用：
(q1) = (q3)a + e
(q2) = ((q1)(a + b) + (q3)b)a*
(q3) = (q2)b
现在我们再次替换并使用规则：
(q1) = (q3)a + e
(q2) = ((q1)(a + b) + (q3)b)a*
(q3) = ((q1)(a + b) + (q3)b)a*b
= (q1)(a + b)a*b + (q3)ba*b
= (q1)(a + b)a*b(ba*b)*
现在我们再次替换并再次使用规则：
(q1) = (q1)(a + b)a*b(ba*b)*a + e
= e((a + b)a*b(ba*b)*a)*
= ((a + b)a*b(ba*b)*a)*
(q2) = ((q1)(a + b) + (q3)b)a*
(q3) = (q1)(a + b)a*b(ba*b)*
我们现在可以替换回来获取（q3）的表达式：
(q1) = ((a + b)a*b(ba*b)*a)*
(q2) = ((q1)(a + b) + (q3)b)a*
(q3) = ((a + b)a*b(ba*b)*a)*(a + b)a*b(ba*b)*
正则表达式将是（q1）和（q3）的表达式的并集，因为它们是接受状态：
r = ((a + b)a*b(ba*b)*a)* + ((a + b)a*b(ba*b)*a)*(a + b)a*b(ba*b)*
= ((a + b)a*b(ba*b)*a)*(e + (a + b)a*b(ba*b)*)
第一部分将以一切可能的方式将你从状态q1回到状态q1;第二部分说你可以留在q1或做另一件事，这会导致q3，否则。
维基百科参考了这个课程PDF：Second Part of Regular Expressions Equivalence with Finite Automata，根据这个文件，程序从这个初始步骤开始：
通过以下程序将DFA转换为特殊形式的GNFA：
- 使用\ epsilon箭头将新的开始状态添加到旧的开始状态，并使用来自所有旧接受状态的\ epsilon箭头添加新的接受状态。
（强调我的）
因此，NFA和DFA将不相同。这也解释了如何处理多个接受状态。
否则在转换过程中，NFA和DFA的状态图将不相同。
对于第二个FSM正则表达式将是 - εU（aUb）ab（bUa（aUb）ab）*（εUa）
你可以参考这些步骤 -
这是一个例子 - 这些是来自本书PDF版本的截图 - Michael Sipser的“计算理论导论”。