in Theory of Computation retagged ago by
8,646 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

17 votes
17 votes
Best answer

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

2 Comments

@ Sir,

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

 

0
0
slpp95prashanth no it won't be the case
1
1
27 votes
27 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

4 Comments

edited by

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 ?

1
1

@
Yes, you are correct.

1
1

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

0
0
17 votes
17 votes

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

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

 

for reason https://gateoverflow.in/blog/8795/minimal-deterministic-finite-automata

1 comment

Thank you, these are very much required.
0
0
1 vote
1 vote

 

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