0
$\begingroup$

I am trying to find Regular expression for a FSM with more than one final state(in my case 2). problem statement FSM

In this I am getting two different RE for state q4 and q5. So my question is If we get more than one different RE for one FSM with more than one final state, is it correct??

$\endgroup$
4
$\begingroup$

If we get more than one different regular expression for the same finite state machine with more than one final state, is it correct?

Rather than push the buttons mechanically, you have to understand what you're doing. Your task is to find a regular expression equivalent to a given FSM. This means that the language accepted by your regular expression has to be the same as the language accepted by the given FSM.

For every state $\sigma$ in the FSM, you can computer a regular expression $r_\sigma$ for the language $L_\sigma$ of all words upon reading of which the FSM ends up at the state $\sigma$ (this definition is valid in the deterministic case; for non-deterministic automata, it has to be slightly modified). The language $L$ accepted by the FSM consists of all words upon reading of which the FSM ends up at an accepting state. Given this data, you should be able to come up with a regular expression for $L$ using the regular expressions $r_\sigma$ for all accepting states — you just have to combine them in the correct way.

$\endgroup$
  • $\begingroup$ Means I have to add all the individual RE to build a single RE such that the final RE can accept all final states with suitable input string, right?? $\endgroup$ – thepurpleowl Sep 30 '16 at 10:11
  • $\begingroup$ Yes, that's the idea. $\endgroup$ – Yuval Filmus Sep 30 '16 at 13:44
1
$\begingroup$

4 steps to convert FSM to RegEx:

  1. Make sure no inward arrows in Initial state ($q0$), if there is then add a new state ($q00$) which goes to initial state ($q0$) on encountering $\epsilon$. Now treat this new state ($q00$) as your new initial state.
  2. If there is an outward arrow from a final state (like $q5$ to $q6$) then add a new state ($fq5$). And make the final state ($q5$) point to this new state ($fq5$) on encountering $\epsilon$. Treat this new state ($fq5$) as the new final state.
  3. If there are multiple final states (like $q5$ and $q4$) then add a new state ($q54$). And make all the final states to point to this new state ($q54$) on encountering $\epsilon$. Treat this new state ($q54$) as the only final state.
  4. Now start eliminating states one by one and substitute a correct RegEx in their place*. Goal is to reach with only 1 initial state and 1 final state, connected by the RegEx.

Now if you ask, can there be more than 1 RegEx for a FSM, then the answer is Yes. It depends on what order you eliminated the states.

Consider a NFA:

  • $q00$ to $q0$ on $\epsilon$
  • $q0$ to $q1$ on $b$
  • $q1$ to $q0$ on $a$
  • $q1$ to $q1$ on $c$ and
  • $q1$ to $q2$ (final state) on $d$

Now if you remove $q0$ first you'll get different RegEx $[b(ab)^*(c+(ab)^*)^*d]$ and if you eliminate $q1$ first you'll get a different RegEx $[(bc^*a)^*bc^*d]$.

*To eliminate states one by one enter image description here

$\endgroup$
  • $\begingroup$ Is it fine now? $\endgroup$ – Ritwik Oct 20 '16 at 8:09
  • $\begingroup$ Much better -- thanks! (And thanks for commenting. That was the only way I noticed you'd edited.) $\endgroup$ – David Richerby Oct 20 '16 at 8:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.