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

Best answer
23 votes
23 votes

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 :

edited by
31 votes
31 votes

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

edited by
2 votes
2 votes

 

Answer) 6 States.

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.

edited by
Answer:

Related questions

17 votes
17 votes
3 answers
1
28 votes
28 votes
8 answers
2
Arjun asked Feb 12, 2020
16,304 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 ______.