-2
$\begingroup$

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

$\endgroup$
5
  • 5
    $\begingroup$ "i feel like I am missing something..?" - What do you feel that you're missing? $\endgroup$ Oct 1, 2014 at 8:30
  • $\begingroup$ thhis wont accept the string baabbabbab for example, even though it has a run of 2a's $\endgroup$ Oct 1, 2014 at 8:42
  • $\begingroup$ Does every run of $a$s in the empty string have length two or three? $\endgroup$ Oct 1, 2014 at 8:50
  • $\begingroup$ Did the answer help you? $\endgroup$
    – d'alar'cop
    Oct 2, 2014 at 23:20
  • $\begingroup$ It does accept abaa which is not in the language. Or aaaabaa. Once you have a run of a single or more than three a's, the remaining input doesn't matter. $\endgroup$
    – gnasher729
    Jul 23, 2020 at 21:07

3 Answers 3

0
$\begingroup$

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

HINT

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

$\endgroup$
3
  • $\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$ Oct 31, 2014 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, 2014 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$ Oct 31, 2014 at 13:59
0
$\begingroup$

I came across this question in Peter Linz' Introduction to Formal Languages and Automata. There it is mentioned that "a run in a string is a substring of length atleast 2". Hence a single $a$ is not a run of $a$. Moreover, every run of $a$'s is either of length two or three can be read as "if there exists a run of $a$'s , then it should be either of length two or three". Hence 0 or 1 $a$ should also be accepted. Your DFA is right except for the fact that $q_0$ and $q_1$ will also be accepting states. $baabbabbab \in L$ because it has run of $a$'s of length two.

$\endgroup$
1
  • 1
    $\begingroup$ I would always assume that a single a is a run of length 1. $\endgroup$
    – gnasher729
    Jul 23, 2020 at 21:08
0
$\begingroup$

5 states: E = Error detected, and S0 to S3 = No error detected, input ends in 0, 1, 2, or 3 a’s. S0, S2 and S3 are accepting.

An a moves from S0, S1, S2 to S1, S2, S3, and from S3 or E To E. b moves from S0, S2 or S3 to S0, and from S1 or E to E.

Close to yours, but S0 is accepting, and b in state S1 goes to the error state.

$\endgroup$

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.