3
$\begingroup$

Design a minimal DFA for the language which contains numbers in the form of binary strings starting with $101_2$ and is divisible by $100_{10}$?

I think the numbers will be 700,1400,2100 ... in the form of binary strings which are starting with $101_2$ and are even divisible by $100_{10}$.

100 is divisible by 25 and 4.

For divisible by 4 - Minimum 3 state DFA is possible For divisible by 25 - Min 25 state DFA is possible.

Hence, for divisible by $100_{10}$ - Minimum 100 states DFA is possible .

So, for starting with $101_2$, I have to add 3 extra states along with one dead state.

So, total states in minimal DFA = 100 + 3 + 1 = 104

Is my approach correct or am I missing something?

$\endgroup$
  • $\begingroup$ So, i thought to post it here, as maybe it is not a field for automata. $\endgroup$ – Garrick Oct 1 '16 at 19:32
  • $\begingroup$ divisible by $100_{10}$ or $100_2$? $\endgroup$ – Jasper Oct 1 '16 at 20:25
  • 1
    $\begingroup$ Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. Thank you! $\endgroup$ – D.W. Oct 2 '16 at 0:20
  • $\begingroup$ In your list of numbers, you appear to have missed 1300, 1500. By my reckoning, the list begins 700, 1300, 1400, 1500, 2600, 2700, 2800, 2900, 3000, 5200, 5300, 5400, ... $\endgroup$ – Rick Decker Oct 2 '16 at 23:44
1
$\begingroup$

Your approach towards estimating the number of states is just fine. however the number of states looks quite intimidating and it may be cumbersome to minimize the DFA later.

In such cases constructing the automaton through intersection is easier. for example as we know the regular languages are closed under the intersection operation we can devise 3 different automata to accept :

1. String divisible by 25
2. String divisible by 4
3. Strings beginning with 101

And then arrive at the final automaton by taking intersections of the 3 machines.

How this helps?

Many of the states originally present in the different machines gradually become unreachable from the initial state in the final automaton and thus the number of states reduce or the DFA is minimized.

$\endgroup$
  • $\begingroup$ Before going any further with a question i would like to make sure the machine you require tests divisibility with 100 in base 10 or 100 in base 2 $\endgroup$ – Shubham Singh rawat Oct 2 '16 at 16:10
  • 1
    $\begingroup$ "Many of the states originally present in the different machines gradually become unreachable from the initial state in the final automaton" - Are you sure? How do you know? I'm quite skeptical: I don't think any of the states become unreachable. $\endgroup$ – D.W. Oct 2 '16 at 23:21
0
$\begingroup$

Your initial approach is right but can be improved.

First, a binary number is a multiple of $4$ if and only if it ends with $00$. Thus the conditions "starting with $101$" and "multiple of $4$" together define the language $L = 101\{0,1\}^*00$. The minimal DFA of $L$ is the following: enter image description here You now have to compute the intersection of $L$ with the language $K = \{ \text{binary strings representing the multiples of $25$}\}$. As you observed, the minimal DNA of $K$ has $25$ states, say $0, \ldots, 24$, corresponding to the possible values modulo $25$ of a natural number. A DFA accepting $L \cap K$ is obtained by taking the accessible states in the product of the previous automata. The initial state is $(1, 0)$ and the first 4 transitions are the following (since, for instance $101_2 = 5_{10}$). enter image description here Starting from state $4$, you may have to consider all states $(4,n)$, $(5,n)$ and $(6,n)$, where $0 \leqslant n \leqslant 24$. This gives an upperbound of $3 \times 25 + 3 = 78$ for the minimal DFA of $L \cap K$ (plus one if you want to add the sink state).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.