DFA Even a's and b's or Odd a's and b's

250 Views Asked by At

Is it possible to make a DFA that accepts an even number of a’s and an even number of b’s or an odd number of a’s and an odd number of b’s just using two states such as (EE/OO) which would be the accepted state and (EO/OE) would be the second state where 'E' means Even and 'O' means odd?

I know it can be done with 4 states but not sure if it's possible with just two combined states.

1

There are 1 best solutions below

0
On

Yes, you can do it with two states just as you suggest, because a word is of the desired form if and only if its length is even. If $w$ is the input word, $|w|=|w|_a+|w|_b$ is even if and only if $|w|_a\equiv|w|_b\pmod2$.