将 DFA 转换为 RE
Converting DFA to RE
我正在使用 JFLAP 将语言的 DFA 转换为 RE
"Even a and Odd b"
最后一步我不太清楚，如图所示，它是如何得到最终 RE
最后回复
((ab(bb)*ba+aa)*(ab(bb)*a+b)(a(bb)*a)*(a(bb)*ba+b))*(ab(bb)*ba+aa)*(ab(bb)*a+b)(a(bb)*a)*
我的困惑在于术语 a(bb)*ba+b (Q1 TO Q0)，为什么它在最后的表达式中有星号
我在你的图表中重新标记了 NFA 的转换，这样解释就更简单了。
这样做会给您留下正则表达式：
(R1* R2 R3* R4)* R1* R2 R3*
带括号的第一个部分实质上描述了使您从 q0 回到 q0 的一系列步骤。正则表达式说，想做多少就做多少，当你玩完之后，你可以跟随 R1 多次，只要你想仍然保持在状态 q0，当你真的玩完之后，按照 R2 进入最终状态，您可以在 R3 上循环播放任意次数。
这不是将状态消除为正则表达式的 NFA 的最巧妙或最直观的方法，但我认为它是正确的。希望解释是有道理的。如果没有，请在评论中提问！
作为参考，我写了我想出的正则表达式。注意我使用 |而不是像你那样的 +。
(aa|ab(bb)*ba)* (ab(bb)*a|b) ((a(bb)*a)* ((a(bb)*ba|b)(aa|ab(bb)*ba)*(ab(bb)*a|b))*)*
编辑：
您希望您的正则表达式捕获所有可能的模式，这些模式最终会引导您进入最终状态，从状态 q0 开始。现在想象你正站在状态 q0。你可以采取什么行动？您可以将您的一组操作拆分为使您处于状态 q0 的操作和使您进入状态 q1 的操作。
让您保持在 q0 的操作：
- 关注 R1
- 跟随R2，在q1中尽你所能，然后跟随R4回到q0。让我们称这个正则表达式为 R2_R4 ，其中空白需要用我们在 q1 中可以做的所有可能的事情来填充，除了通过 R4 返回。那么在 q1 中我们唯一能做的就是跟随 R3 多次，所以我们用 R2R3*R4 替换空白。
通过列举您可以留在 q0 中的所有方式，您基本上摆脱了从 q1 到 q0 (R4) 的过渡。换句话说，您是在我的正则表达式的这一部分之后说，如果您转到状态 q1，则应该没有办法返回到 q0（如果有的话，它会被正则表达式的第一部分捕获）。所以你的 NFA 现在看起来像这样：
所以你最终的正则表达式是，跟随留在 q0 中的过渡，然后通过 R2 转到 q1，并通过跟随 R3 留在 q2 中，只要你愿意。所以你的正则表达式看起来像：
(R1 + R2R3*R4)* R1* R2 R3*
实际上相当于你拥有的那个：
(R1* R2 R3* R4)* R1* R2 R3*
因为(R1+R2 R3* R4)*的or性质等价于(R1* R2 R3* R4)*。其实我觉得带 or (+) 的版本更清晰，但只要能用就无所谓了。
我正在使用 JFLAP 将语言的 DFA 转换为 RE
"Even a and Odd b"
最后一步我不太清楚，如图所示，它是如何得到最终 RE
最后回复
((ab(bb)*ba+aa)*(ab(bb)*a+b)(a(bb)*a)*(a(bb)*ba+b))*(ab(bb)*ba+aa)*(ab(bb)*a+b)(a(bb)*a)*
我的困惑在于术语 a(bb)*ba+b (Q1 TO Q0)，为什么它在最后的表达式中有星号
我在你的图表中重新标记了 NFA 的转换，这样解释就更简单了。
这样做会给您留下正则表达式：
(R1* R2 R3* R4)* R1* R2 R3*
带括号的第一个部分实质上描述了使您从 q0 回到 q0 的一系列步骤。正则表达式说，想做多少就做多少，当你玩完之后，你可以跟随 R1 多次，只要你想仍然保持在状态 q0，当你真的玩完之后，按照 R2 进入最终状态，您可以在 R3 上循环播放任意次数。
这不是将状态消除为正则表达式的 NFA 的最巧妙或最直观的方法，但我认为它是正确的。希望解释是有道理的。如果没有，请在评论中提问！
作为参考，我写了我想出的正则表达式。注意我使用 |而不是像你那样的 +。
(aa|ab(bb)*ba)* (ab(bb)*a|b) ((a(bb)*a)* ((a(bb)*ba|b)(aa|ab(bb)*ba)*(ab(bb)*a|b))*)*
编辑：
您希望您的正则表达式捕获所有可能的模式，这些模式最终会引导您进入最终状态，从状态 q0 开始。现在想象你正站在状态 q0。你可以采取什么行动？您可以将您的一组操作拆分为使您处于状态 q0 的操作和使您进入状态 q1 的操作。
让您保持在 q0 的操作：
- 关注 R1
- 跟随R2，在q1中尽你所能，然后跟随R4回到q0。让我们称这个正则表达式为 R2_R4 ，其中空白需要用我们在 q1 中可以做的所有可能的事情来填充，除了通过 R4 返回。那么在 q1 中我们唯一能做的就是跟随 R3 多次，所以我们用 R2R3*R4 替换空白。
通过列举您可以留在 q0 中的所有方式，您基本上摆脱了从 q1 到 q0 (R4) 的过渡。换句话说，您是在我的正则表达式的这一部分之后说，如果您转到状态 q1，则应该没有办法返回到 q0（如果有的话，它会被正则表达式的第一部分捕获）。所以你的 NFA 现在看起来像这样：
所以你最终的正则表达式是，跟随留在 q0 中的过渡，然后通过 R2 转到 q1，并通过跟随 R3 留在 q2 中，只要你愿意。所以你的正则表达式看起来像：
(R1 + R2R3*R4)* R1* R2 R3*
实际上相当于你拥有的那个：
(R1* R2 R3* R4)* R1* R2 R3*
因为(R1+R2 R3* R4)*的or性质等价于(R1* R2 R3* R4)*。其实我觉得带 or (+) 的版本更清晰，但只要能用就无所谓了。