How to convert an NFA to the corresponding Regular

问题:

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

My solution was:

aba

Am I correct?

回答1:

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:

• 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*.

• 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.

• 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₂).

• 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* ).

And RE is a*ba*.

Also, its DFA is as follows:

 DFA: 
======

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

    a*    b      a*    :RE  
                       ==== 

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

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

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

And its a Minimized DFA!

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

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*?

回答2:

That answer is correct, in that both of the following are true:

• Any string matching the regular expression causes the NFA to end in an accepting state (double circled state)
• Any string causing the NFA to end in an accepting state also matches the regular expression

However, I can't check your work because you haven't posted any.