如何将NFA转换为相应的正则表达式? [英] How to convert an NFA to the corresponding Regular Expression?

问题描述

我正在为明天的考试而学习，并且我检查了许多教程，讲述了如何将NFA转换为Regex，但是我似乎无法确认我的答案.按照这些教程，我解决了NFA

I am studying for tomorrows exam and I have checked many tutorials telling how to convert NFA to Regex but I can't seem to confirm my answers. Following the tutorials, I solved that NFA

我的解决方法是:

a ba

aba

我正确吗?

推荐答案

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

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

How to convert NFA to Regular Expression?

Your answer a*ba* is Correct. I can drive your answer from NFA in given image as follows:

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

• There is a self loop on start state q₀ with label a. So there can be any number of as are possible at initial (prefix) including null ^ in RE. So Regular Expression(RE) start with a*.

您只需一个b即可达到最终状态.实际上是一个可接受的字符串； a和b的字符串中至少应有一个b.因此，RE a*b到达q ₁ 或q ₂ .两者都是最终状态.

You need only one b to reach to final state. Actually for an accepting string; there must be at-least one b in string of a and b. So RE a*b to reach to either q₁ or q₂. Both are final states.

一旦达到最终状态(q ₁ 或q ₂ ).字符串中不能有其他b(对于b，没有来自q ₁ 和q ₂ 的传出边).

Once you reach to a final state (q₁ or q₂). No other b is possible in string (there is no outgoing edge for b from q₁ and q₂).

在q ₁ 和q ₂ 处只能使用符号a.同样对于a在q ₁ 或q ₂ 处，在q ₁ ，q ₂ 和两者都是最终的.因此，在符号b之后可以有任意数量的a后缀. (因此字符串以a*结尾).

Only symbol is a can be possible at q₁ and q₂. Also for, a at q₁ or at q₂ move switch between q₁ , q₂ and both are final. So after symbol b any number of as can be in suffix. (So string ends with a* ).

且RE为a*ba*.

此外，其 DFA 如下:

 DFA: 
======

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

    a*    b      a*    :RE  
                       ==== 

• 在q0处的a的任意数量，即:a*

  • Any number of as at q0 that is: a*

    一旦获得b，就可以切换到最终状态q1:b

    once you get b you can switch to final state q1: b

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

    at final state any number of a is possible: a*

    及其最小化的DFA！

    这是我对FAs和REs的一些更有趣的回答，我相信这对您会有所帮助:

    Here is some more interesting answer by me on FAs and REs, I believe will be useful to you:

    1. 如何为A编写常规表达DFA
    2. RE到DFA
    3. 到DFA的正则表达式
    4. 从正则表达式构造等效的正则语法
    5. 如何在无上下文语法中消除左递归
    6. a *是否与(a *)*相同?
    7. 在常规表达方式中:(AB)* = A*B*?
    1. HOW TO WRITE REGULAR EXPRESSION FOR A DFA
    2. RE TO DFA
    3. Regular Expression to DFA
    4. Constructing an equivalent Regular Grammar from a Regular Expression
    5. How to Eliminate Left recursion in Context-Free-Grammar
    6. Is a* the same as (a*)*?
    7. IN CONTEXT OF REGULAR EXPRESSION: is (AB)* = A*B*?

    这篇关于如何将NFA转换为相应的正则表达式?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！