retagged by
13,347 views
18 votes
18 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 _________
retagged by

7 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.
0 votes
0 votes

(A )number of states in dfa  that accepts string having number of a’s divisible 2 is = 3

(B)number of states in dfa  that accepts string having number of a’s divisible 3 is = 4 thens its complement also having same number of states.

number of states after (A and B)=(3-1)*(4-1)=6

 

Answer:

Related questions

17 votes
17 votes
3 answers
1
28 votes
28 votes
8 answers
2
Arjun asked Feb 12, 2020
16,306 views
The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L’s are indistinguishable, is ______.