8,646 views
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 _________

### 1 comment

Number of $a’s$ in $x$ are divisible by $2$ but not divisible by $3$ means number of $a's$ can be $2,4,8,10,14,16,20,22,26,\ldots$

Terms which are divisible by both $2$ and $3$ like $6,12,18,24,\ldots$ are dropped from the above sequence at finite interval in $*$ position from above sequence $2,4,*,8,10,*,14,16,*,20,22,*,26,28,*,32,34,\ldots$

Here, sequence $\{6,12,18,24,\ldots\}$ is in AP. Now, to drop this sequence from our original sequence which represent the number of $a's$, we have to go through at least total $7$ states which says total $6$ $a's$ have seen so far and since terms of this sequence come at regular interval, So, we will make a cycle in the DFA as :

Now, observe that states $0$ and $6$ are equivalent because by definition, $2$ states $p$ and $q$ are equivalent i.e.

$p \approx q \overset{\textit{def}}\Leftrightarrow \forall x \in \Sigma^{*}(\hat{\delta}(p,x) \in F \Leftrightarrow \hat{\delta}(q,x) \in F)$

It says $2$ states are equivalent if for all strings, they both either go to final state or both go to non-final state means they have the same nature.

So, here, we can merge states $0$ and $6$. Other states can't be merged because they are in cycle and if we merge states which are in cycle, machine will not accept the desired number of $a's$ and reject $6,12,18,\ldots$ $a's.$

So, our final collapsing $\textsf{DFA}$ is :

@ Sir,

Do e(empty string, so number of a’s = 0) is divisible by 2 and not divisible by 3?

slpp95prashanth no it won't be the case

Number of $a$'s is divisible by $2$

 $a$ $b$ $A^*$ $B$ $A^*$ $B$ $A^*$ $B$

Number of $a$'s  is not divisible by $3$

 $a$ $b$ $D$ $E^*$ $D$ $E^*$ $F^*$ $E^*$ $F^*$ $D$ $F^*$

Now we can combine both these table to get the desired DFA

Number of $a$'s is divisible by $2$ but not divisible by $3$

 $a$ $b$ $AD$ $BE$ $AD$ $AE^*$ $BF$ $AE^*$ $AF^*$ $BD$ $AF^*$ $BD$ $AE^*$ $BD$ $BE$ $AF^*$ $BE$ $BF$ $AD$ $BF$

now we can use minimization technique to check whether we can merge states in DFA or not

$\{\ AD,\ BD\ ,BE\ ,BF\ \}$ $\{AE^*\ ,AF^*\ \}$

$\{\ AD, BF\ \}$ $\{BD\ ,BE\ \}$ $\{AE^*\ ,AF^*\ \}$

$\{\ AD\ \} \{ \ BF\ \}$ $\{BD\ ,BE\ \}$ $\{AE^*\ \} \{\ AF^*\ \}$

$\{\ AD\ \} \{ \ BF\ \}$ $\{BD\ \} \{\ BE\ \}$ $\{AE^*\ \} \{\ AF^*\ \}$

$\{\ AD\ \} \{ \ BF\ \}$ $\{BD\ \} \{\ BE\ \}$ $\{AE^*\ \} \{\ AF^*\ \}$

$\therefore$ There will be $6$ states in the given DFA

by

edited

In the same manner if given as “number of a’s divisible by 6 but not divisible by 12” , then minimal states would be 12 and if “number of a’s divisible by 2 or divisible by 3 ” would be 6 states right ?

@
Yes, you are correct.

## State A was final in divisible by 2 DFA, but in combined DFA it was not considered as final?

neither 2 is divisible by 3 nor 3 is divisible by 2.

So, Minimal DFA. contains LCM(2,3) = 6 states

### 1 comment

Thank you, these are very much required.

This is a question of product automata.

DFA for number of a’s in x divisible by 2:                                     DFA for number of a’s not divisible by 3:

Now applying product automata:

Therefore 6 states. 15 and 14 are final states.