regex - 如何将 NFA 转换为相应的正则表达式？

Question

我正在为明天的考试而学习，我已经检查了许多教程，告诉我如何将 NFA 转换为正则表达式，但我似乎无法确认我的答案。按照教程，我解决了 NFA

我的解决方案是：

阿坝_

我对么？

Answer 1

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

你的答案a*ba*是正确的。我可以从给定的图像中得出您的答案，NFA如下所示：

• 在带有标签的开始状态 q ₀a上有一个自循环。因此a，初始（前缀）可以有任意数量的 s，包括^RE 中的 null。所以正则表达式（RE）以a*.

• 您只需要一个b即可达到最终状态。实际上是一个接受字符串；和b的字符串中必须至少有一个。所以 RE要达到 q ₁或 q ₂。两者都是最终状态。 aba*b

• 一旦达到最终状态（q ₁或 q ₂）。字符串中不可能有其他（从 q ₁和 q ₂b没有出边）。b

• _{在 q 1}和 q ₂处只有符号是a可能的。同样对于，在 q ₁或在 q ₂移动切换 q ₁， q ₂并且两者都是最终的。所以在符号之后可以有任意数量的s 后缀。（所以字符串以 结尾）。 abaa*

而 RE 是a*ba*。

此外，它的DFA如下：

 DFA: 
======

    a-          a-  
    ||          ||
    ▼|          ▼|
--►(q0)---b---►((q1))      

    a*    b      a*    :RE  
                       ==== 

• 任意数量的asq0是： a*

• 一旦你得到b你可以切换到最终状态q1： b

• 在最终状态下，任何数量的a都是可能的： a*

它是最小化的 DFA！

这是我在FAs和上的一些更有趣的答案REs，我相信对您有用：

1. 如何为 DFA 编写正则表达式
2. 回复 DFA
3. 正则表达式到 DFA
4. 从正则表达式构造等效的正则语法
5. 如何消除上下文无关语法中的左递归
6. a* 和 (a*)* 一样吗？
7. 在正则表达式的情况下：是(AB)* = A*B*?

Answer 2

这个答案是正确的，因为以下两个都是正确的：

• 任何匹配正则表达式的字符串都会导致 NFA 以接受状态结束（双圈状态）
• 任何导致 NFA 以接受状态结束的字符串也与正则表达式匹配

但是，我无法检查您的工作，因为您还没有发布任何内容。