1

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

在此处输入图像描述

我的解决方案是:

阿坝_

我对么?

4

2 回答 2

2

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

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

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

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

  • 一旦达到最终状态(q 1或 q 2)。字符串中不可能有其他(从 q 1和 q 2b没有出边)。b

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

而 RE 是a*ba*

此外,它的DFA如下:

 DFA: 
======

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

    a*    b      a*    :RE  
                       ==== 
  • 任意数量的asq0是: a*

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

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

它是最小化的 DFA!

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

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

这个答案是正确的,因为以下两个都是正确的:

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

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

于 2013-01-11T22:02:24.463 回答