将非确定性有限自动机转换为正则表达式

Question

我在这个转换问题上遇到了非常困难的时期。我已经阅读、重新阅读和观看视频，但我很确定我得出的答案是不正确的。

我有一种感觉，我错过了一些步骤。 这就是我最终的表达方式：

(ab*(aUb)a*)Ua*

我在这张图片中分享了我的步骤。 ()

Answer 1

我认为这篇论文非常清楚地解释了如何将 NFA 转换为正则表达式。

逐步创建一个 NFA，其边缘用正则表达式而不是标记进行标记，然后删除状态，直到只有一条从输入状态到输出状态的边缘。

1. 创建一个新的唯一初始状态，其标记为 ε 的边将转到原始初始状态。
2. 创建一个新的唯一最终状态，其边缘标记为 ε，从所有最终状态到这个新的最终状态。
3. 逐一删除内部状态：选择一个状态 q。查看有边缘进入 q、in1、in2、in3 的状态...查看有边缘从 q、out1、out2、out3 出来的状态。令状态q有一个Rq的自循环（可以为空）。对于每对 ini 和 outj，将 ini -> q -> outj 替换为 Rini(Rq*)Routj。重复。

https://courses.engr.illinois.edu/cs374/fa2017/extra_notes/01_nfa_to_reg.pdf有一个很好的例子。