in Theory of Computation retagged ago by
8,616 views
13 votes
13 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 ago by
by
8.6k views

1 comment

0
0

5 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.
Answer:

Related questions