如何将 NFA 图转换为正则表达式？

Question

我正在复习正则表达式，一直卡在以下问题上：

提供一个正则表达式来描述以下NFA的语言： NFA Diagram

我不知道如何回答以下问题，我不希望有人给我答案。如果可能的话，我将非常感谢有关如何解决此类问题或如何解决此特定问题的指导。谢谢！

非常感谢任何帮助！

Answer 1

基本的转换，你懂的。

{q0, x, q0} becomes x*
{q0, x, q1} becomes x
{q0, x, q1}, {q0, y, q1} becomes x+y

您的图表是 DFA。你最右边的状态不应该是 q1。你有双 q1。从现在起命名最正确的状态q3。

我认为最困难的部分是因为有从 q3 返回到 q1 和 q2 的传出过渡。

我们将从左边开始。

{q0, x, q0},{q0, y, q1} => x*y

q0是开始状态，q1是结束状态。那么 x*y 一定会发生。其余的可能发生也可能不发生，因为存在从 q3 返回到 q1 的过渡。所以，我们可以这样写：

RE = x*y( ... )*

我们现在在括号内工作。

{q1, x, q2}, {q1, y, q2} => (x+y)

因为有一个从q3回到q2的转换，我们可以写成：

RE = x*y((x+y)( ... ))*

因为只有一个转换到达最终状态，即{q3, y, q1}，所以我们把y放在最后。

RE = x*y((x+y)( ... )y)*

最后一部分也是比较混乱的部分是{q2, y, q2}, {q2, x, q3}, {q3, x, q2} => (y+xx)*x

解释：

我们在 q2，我们有 y* 或 (xx)* 一次或多次时间回到 q2。我们可以写 (y*+(xx)*)* 或简单地写 (y+xx)*。请记住，我们必须在 q3 上通过读取 y 进入最终状态，然后从 q2 我们需要读取 x，以便 (y+xx)*x .

所以完整的正则表达式：x*y((x+y)(y+xx)*xy)*

Answer 2

ipramusinto的回答不正确。 x*y((x+y)(y+xx)*xy)* 接受不是解决方案的字符串 yxxyxy。

查看有关如何完成的相关话题（评论）。

正则表达式是：x*y((x|y)y*x(xy*x)*y)*

How to Convert an NFA Diagram to a Regular Expression?