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 q0 with label
a
. So there can be any number ofa
s are possible at initial (prefix) including null^
in RE. So Regular Expression(RE) start witha*
.You need only one
b
to reach to final state. Actually for an accepting string; there must be at-least oneb
in string ofa
andb
. So REa*b
to reach to either q1 or q2. Both are final states.Once you reach to a final state (q1 or q2). No other
b
is possible in string (there is no outgoing edge forb
from q1 and q2).Only symbol is
a
can be possible at q1 and q2. Also for,a
at q1 or at q2 move switch between q1 , q2 and both are final. So after symbolb
any number ofa
s can be in suffix. (So string ends witha*
).
And RE is a*ba*
.
Also, its DFA is as follows:
DFA:
======
a- a-
|| ||
▼| ▼|
--►(q0)---b---►((q1))
a* b a* :RE
====
Any number of
a
s atq0
that is:a*
once you get
b
you can switch to final stateq1
: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: