1
$\begingroup$

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*

or

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.

Improve this question
$\endgroup$
2
  • 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
    Commented May 5, 2019 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
    Commented May 5, 2019 at 14:25

1 Answer 1

Reset to default
1
$\begingroup$

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). $$

Improve this answer
$\endgroup$
5
  • $\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
    Commented May 5, 2019 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
    Commented May 5, 2019 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
    Commented May 5, 2019 at 15:43
  • $\begingroup$ This point doesn’t seem relevant here. $\endgroup$
    – Yuval Filmus
    Commented May 5, 2019 at 15:44
  • $\begingroup$ Agreed, many thanks again Yuval. $\endgroup$
    – Sergi
    Commented May 5, 2019 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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