-1
$\begingroup$

I have to draw a finite automaton of a language over $\{a,b\}$ of all strings having odd length and has an even number of $b$s.

I already came up with following regular expression $(a+b)((a+b)(a+b))^*$ which satisfies the condition that a string must have odd length.

What should it look like so that a string has even number of $b$s as well?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Hint: Use four states, depending on what the input so far has been: (odd length, even b's), (odd length, odd b's), (even length, even b's), (even length, odd b's).

Then answer these questions:

  1. Which of the states should be the start state?
  2. Which of the states should be final states?
  3. What should the transitions be between the states? For example, from (odd length, even b's), on seeing an $a$ you should then be in (even length, even b's).
$\endgroup$

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