GATE CSE 2020 | Question: 51

Question

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 _________

Comments

similar question

https://gateoverflow.in/2280/gate1997-20

Answer 1

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 :

Comments

@Arjun 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

Answer 2

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

Comments

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 ?

---

@Shivateja MST
Yes, you are correct.

---

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

Answer 3

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

Comments

Thank you, these are very much required.

Answer 4

 

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.

Comments

But in this method we need to check it is minimized or not.