如何将NFA转换为相应的正则表达式？(How to convert an NFA to the co

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

我的解决办法是：

学士学位

我对么？

Answer 1:

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

你的回答a*ba*是正确的。 我可以从驾驶你的答案NFA给出相关图片如下：

• 有在启动状态q ₀自我循环与标签的a 。 这样可以有任何数量的a s为初始（前缀）可以包括null ^在RE。 所以，正则表达式（RE）开始与a* 。

• 你只需要一个b ，以达到最终状态。 实际上用于接受串; 必须有-至少一个b中的串a和b 。 所以RE a*b到达要么，Q ₁或Q _2。 两者都是最终状态 。

• 一旦你达到最终状态（Q ₁或Q _2）。 没有其他的b是可能的字符串（不存在用于传出边缘b从Q ₁和Q _2）。

• 只有符号是a可以在Q ₁和Q ₂是可能的。 还为， a以Q ₁或Q _{1，Q 2}和二者之间Q ₂移动开关是最终的。 因此，符号后面b任意数量的a S可在后缀。 （因此字符串结尾a* ）。

RE是a*ba* 。

此外，它的DFA如下：

 DFA: 
======

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

    a*    b      a*    :RE  
                       ==== 

• 任何数量的a在s q0那就是： a*

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

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

而其最小化DFA！

下面是我的一些更有趣的答案上FAs和REs ，我相信将是您有用：

1. 如何写好的正则表达式是为DFA
2. RE到DFA
3. 正则表达式DFA
4. 从正则表达式构建等效正规文法
5. 如何消除左递归的上下文无关文法
6. 是*同为（a *）*？
7. 在上下文中的正则表达式：是(AB)* = A*B*?

Answer 2:

这个答案是正确的，在以下两个条件为真：

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

然而，我无法检查你的工作，因为你没有发布任何。

文章来源: How to convert an NFA to the corresponding Regular Expression?