I am trying to create a dfa for L={w: every run of a's has length either two or three}

this is my attempt at the solution..i feel like I am missing something..?

enter image description here

  • 4
    $\begingroup$ "i feel like I am missing something..?" - What do you feel that you're missing? $\endgroup$ – Guildenstern Oct 1 '14 at 8:30
  • $\begingroup$ thhis wont accept the string baabbabbab for example, even though it has a run of 2a's $\endgroup$ – matt mowris Oct 1 '14 at 8:42
  • $\begingroup$ Does every run of $a$s in the empty string have length two or three? $\endgroup$ – David Richerby Oct 1 '14 at 8:50
  • $\begingroup$ Did the answer help you? $\endgroup$ – d'alar'cop Oct 2 '14 at 23:20

Yes, there is something wrong. In your comment you stated that you feel that it should be accepting $baabbabbab$. You are wrong about this.

The language you want is $L=\{w \in \{a,b\}^* | w = ((aa|aaa|\epsilon)b)^*(aa|aaa|\epsilon)\}$

Clearly, $baabbabbab \not\in L$.

Regarding your DFA, I have some excellent news but you'll quiesce in your pants about it. In fact, your DFA accepts any string that ends in a run of a's of length 2 or 3 and contains no runs of length 4 i.e. $L(<your\ DFA>) = \{w \in \{a,b\}^* | w= (ab|aab|aaab|b)^*(aa|aaa)\}$.


State $q_1$ in your proposed DFA, on $b$, should go to a halting state.

  • $\begingroup$ Personally, I find it much easier to see that $baabbabbab$ is not a string in which every run of $a$s has length two or three than to see that the regular expression $((aa|aaa|\epsilon)b)^*(aa|aaa|\epsilon)$ describes exactly that language and that $baabbabbab$ doesn't match the regular expression! So "Clearly, $baabbabbab\notin L$" doesn't seem to be a very helpful thing to say. $\endgroup$ – David Richerby Oct 31 '14 at 13:14
  • $\begingroup$ @DavidRickerby Perhaps you are correct sir. But I'd say that it depends on your background. A programmer may be happy with the regex. $\endgroup$ – d'alar'cop Oct 31 '14 at 13:21
  • 1
    $\begingroup$ I don't think it really depends on background. Here's my proof that $baabbabbab$ is not a string in which every run of $a$s has length two or three: the third $a$ is in a run of length one. I'm perfectly happy with regular expressions but the argument via the regular expression involves more complicated concepts (regular expressions versus counting to three) and any argument via that regular expression necessarily includes the argument "... and $baabbabbab$ contains runs of $a$s that don't have length two or three..." $\endgroup$ – David Richerby Oct 31 '14 at 13:59

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.