in Theory of Computation retagged by
9,526 views
16 votes
16 votes
Consider the following language.

$L = \{{ x\in \{a,b\}^*\mid}$number of $a$’s in $x$ divisible by $2$ but not divisible by $3\}$

The minimum number of states in DFA that accepts $L$ is _________
in Theory of Computation retagged by
by
9.5k views

1 comment

0
0

6 Answers

0 votes
0 votes
Number of a is divisible by 2 but not by 3.

So from all the multiples of 2 we have to exclude the multiples of 3.

Note that common multiplier of 2 & 3 can be found in the table of 6 bcz LCM(2,3)=6.

SO THE NUMBER DIVIDED BY 6 WE HAVE TO EXCLUDE LIKE 6,12,18,24,... FROM TABLE OF 2.

now the problem reduce to

Complement of ( min. DFA which accepts number of "a" which is divisible by 6)

Now to design this DFA we need 6 states minimum.

After designing the DFA inside the bracket have to complement it by changing the final states.
0 votes
0 votes
There is a simple logical approach to solve this question: any number divisible by 2 and 3 is divisible by 6. Let us prepare a DFA for mod 6. Now the final states would be the states where n mod 6=2 and n mod 6 = 4. And in any case, the max number of states in min DFA for mod 6 will be = 6.
Answer:

Related questions