0

NFA to regular expression

Above is a try of converting a NFA to a regular expression (can a moderator rotate it please). There must be somewhere along the process where I do something wrong because if you compare the end result (union between the last two transitions) compared to the expected one, it is very off.

Appreciate any help!

Fredrik Andersson
  • 151
  • I haven't read your work carefully, but you should simplify $\varepsilon\varepsilon$ to $\varepsilon$ and $\varepsilon 0 \varepsilon$ to $0$. – Fabio Somenzi Dec 02 '18 at 14:53
  • Next, it's important to realize that there are regular expressions that look very different, but describe the same language. Redundancies like the ones I pointed out in my first comment do not help, but in general, the final regular expression you get depends on the order of elimination and the simplifications you apply. On a detailed level, you lack a pair of parentheses in your last diagram. – Fabio Somenzi Dec 02 '18 at 15:29
  • @FabioSomenzi modified the picture again. I understand that the regular expressions can have many shapes but it just feels like I'm not doing some obvious translations because it's much more complicated than the actual answer. – Fredrik Andersson Dec 02 '18 at 15:57
  • Try the elimination order 3-1-2. (I believe your answer is correct now, even though you still have some redundancies, like $10\varepsilon$ instead of $10$.) – Fabio Somenzi Dec 02 '18 at 16:03
  • @FabioSomenzi thanks for the help. Is there any trick to see which elimination is preferred to start with? I know the end result is the same but mine got very complex. – Fredrik Andersson Dec 02 '18 at 16:10
  • In this case, if you eliminate $3$ first, you get a simpler residual structure, but there is no obvious rule I know of to decide the elimination order. – Fabio Somenzi Dec 02 '18 at 17:01

0 Answers0