I am trying to find the regular expression that defines this DFA, I am finding this particular case difficult since it has multiple accepting states.

If I understand this DFA correctly, it recognises:

empty strings or strings with any number of b => b*


a followed by any number of b => ab* or aa followed by any number of b => aa(b*)

So the closest I have got is b*+(a+aa)+(a+aa)b* but I know this is not correct, since it doesn't recognise strings such aabaabab.

enter image description here

I have been using http://ivanzuzak.info/noam/webapps/fsm_simulator/ so I can see I don't know how to make the transition back to Q0 from Q1 or Q2 when there is a b.

I took a look to How to convert finite automata to regular expressions? but the explanations are way above my current level of understanding.

Could anybody help me finding where I'm going wrong and how could I fix it?

Many thanks in advance.

  • 1
    $\begingroup$ If all else fails, you can always construct three separate regular expressions $R_1$, $R_2$, $R_3$ that correspond respectively to the automata where just the first, second and third state is accepting. And then take $R_1+R_2+R_3$. $\endgroup$ – David Richerby May 5 '19 at 14:14
  • $\begingroup$ Note that you can have arbitrarily long blocks of bs alternating with blocks of one or two as. $\endgroup$ – Marcus Ritt May 5 '19 at 14:25

Your DFA accepts all words not containing $aaa$. Such words are built of the following "building blocks": $b,ab,aab$. Additionally, a word may end with $a,aa$. In total, we get the regular expression $$ (b+ab+aab)^*(\epsilon+a+aa). $$

  • $\begingroup$ Many many thanks! When discussing it with a colleague I was told I shouldn't use the 𝜖, only * to indicate a string of any length (including the empty string) however, I am not sure it is possible to do it in this particular case. In any case I really appreciate your help! $\endgroup$ – Sergi May 5 '19 at 15:37
  • $\begingroup$ You can use the distributive rule to get rid of $\epsilon$, but I don't really see the point of it. I'm not sure you understood your colleague correctly. $\endgroup$ – Yuval Filmus May 5 '19 at 15:39
  • $\begingroup$ I guess the point she made was that (b + 𝜖)* is equivalent to (b)* and that I shouldn't use 𝜖, but as you said, there's no point as long as the regex works. $\endgroup$ – Sergi May 5 '19 at 15:43
  • $\begingroup$ This point doesn’t seem relevant here. $\endgroup$ – Yuval Filmus May 5 '19 at 15:44
  • $\begingroup$ Agreed, many thanks again Yuval. $\endgroup$ – Sergi May 5 '19 at 15:46

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.