Give a finite state diagram for a DFA that accepts any word in the language $L = \{w \mid w \in \{a, b\}^* \text{ and }w \text{ alternates } a\text{'s and }b\text{’s and has an even number of }b\text{’s}\}$.

My attempt: I am having problem on how to deal with the even part of b.

  • $\begingroup$ Just to clarify, does a string in the language have to start with $a$, or would you consider the string $bab$ to be in the language (since the $a$s and $b$s alternate and it has an even number of $b$s)? $\endgroup$ – Rick Decker Nov 30 '15 at 1:21
  • $\begingroup$ It can start with either one of them. $\endgroup$ – max Nov 30 '15 at 1:31

Since the strings must be of the form $ababab\dotsm$, and also there must be 0, 2, 4, 6, ... $b$s, begin with four states, each of which "remembers" the input so far:

  • $q_0$: just saw an $a$ and have seen an even number of $b$s so far,
  • $r_0$: just saw a $b$ and have seen an odd number of $b$s so far,
  • $q_1$: just saw an $a$ and have seen an odd number of $b$s so far,
  • $r_1$: just saw a $b$ and have seen an even number of $b$s so far.

Then, it's clear that these states will have transitions in a cycle, with transitions:

  • $\delta(q_0, b) = r_0$
  • $\delta(r_0, a) = q_1$
  • $\delta(q_1, b) = r_1$
  • $\delta(r_1, a) = q_0$

and the other possibilities will either be undefined or lead to a trap state, depending on what model of a DFA you're accustomed to using. Now make a new start state $s$, with $\delta(s, a) = q_0$ (since you've just seen an $a$ and have no $b$s yet), and, for similar reasons, define $\delta(s, b) = r_0$. I'll leave it to you to decide which (two) of the states in the cycle of four states should be final.

There are systematic ways to do this kind of product DFA, but in this case, it's no simpler than this ad hoc construction.


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.