Design DFA accepting binary strings divisible by a number n

Question

I need to learn how to design a DFA such that given any number 'n', it accepts binary strings {0, 1} whose decimal equivalent number is divisible by 'n'.

There will be different DFAs for different 'n', but can somebody give a basic approach that I should follow to proceed with any number 0 < n < 10 .

User · Answer

I know I am quite late  but I just wanted to add a few things to the already correct answer provided by  Grijesh  I d like to just point out that the answer provided by  Grijesh does not produce the minimal DFA  While the answer surely is the right way to get a DFA  if you need the minimal DFA you will have to look into your divisor   Like for example in binary numbers  if the divisor is a power of 2  i e  2 n  then the minimum number of states required will be n 1  How would you design such an automaton  Just see the properties of binary numbers  For a number  say 8  which is 2 3   all its multiples will have the last 3 bits as 0  For example  40 in binary is 101000  Therefore for a language to accept any number divisible by 8 we just need an automaton which sees if the last 3 bits are 0  which we can do in just 4 states instead of 8 states  That s half the complexity of the machine   In fact  this can be extended to any base  For a ternary base number system  if for example we need to design an automaton for divisibility with 9  we just need to see if the last 2 numbers of the input are 0  Which can again be done in just 3 states   Although if the divisor isn t so special  then we need to go through with  Grijesh s answer only  Like for example  in a binary system if we take the divisors of 3 or 7 or maybe 21  we will need to have that many number of states only  So for any odd number n in a binary system  we need n states to define the language which accepts all multiples of n  On the other hand  if the number is even but not a power of 2  only in case of binary numbers  then we need to divide the number by 2 till we get an odd number and then we can find the minimum number of states by adding the odd number produced and the number of times we divided by 2   For example  if we need to find the minimum number of states of a DFA which accepts all binary numbers divisible by 20  we do    20 2   10  10 2   5   Hence our answer is 5   1   1   7    The 1   1 because we divided the number 20 twice

User · Answer

Below  I have written an answer for n equals to 5  but you can apply same approach to draw DFAs for any value of n and  any positional number system  e g binary  ternary      First lean the term  Complete DFA   A DFA  defined on complete domain in d Q    S Q is called  Complete DFA   In other words  we can say  in transition diagram of complete DFA there is no missing edge  e g  from each state in Q there is one outgoing edge present for every language symbol in S   Note  Sometime we define partial DFA  as d   Q    S Q  Read  How does    d Q    S Q    read in the definition of a DFA    Design DFA accepting Binary numbers divisible by number  n    Step-1  When you divide a number   by n then reminder can be either 0  1        n - 2  or  n - 1   If remainder is 0 that means   is divisible by n otherwise not  So  in my DFA there will be a state qr that would be corresponding to a remainder value r  where 0  lt   r  lt    n - 1   and total number of states in DFA  is n  After processing a number string   over S  the end state is qr implies that     n    r    reminder operator    In any automata  the purpose of a state is like memory element  A state in an atomata stores some information like fan s switch that can tell whether the fan is in  off  or in  on  state  For n   5  five states in DFA corresponding to five reminder information as follows      State  q0 reached if reminder is 0  State q0  is the final state accepting state   It is also an initial state    State q1 reaches  if reminder is 1  a non-final state    State q2 if reminder is 2  a non-final state    State q3 if reminder is 3  a non-final state    State q4 if reminder is 4  a non-final state      Using above information  we can start drawing transition diagram TD of five states as follows                 Figure-1      So  5 states for 5 remainder values  After processing a string   if end-state becomes q0 that means decimal equivalent of input string is divisible by 5  In above figure q0 is marked final state as two concentric circle  Additionally  I have defined a transition rule d  q0  0  q0 as a self loop for symbol  0  at state q0  this is because decimal equivalent of any string consist of only  0  is 0 and 0 is a divisible by n   Step-2  TD above is incomplete  and can only process strings of  0 s  Now add some more edges so that it can process subsequent number s strings  Check table below  shows new transition rules those can be added next step     -------------------------------------    Number  Binary  Remainder  5   End-state    ------ ------ ------------- ---------     One     1       1              q1           ------ ------ ------------- ---------     Two     10      2              q2           ------ ------ ------------- ---------     Three   11      3              q3           ------ ------ ------------- ---------     Four    100     4              q4           -------------------------------------     To process binary string  1  there should be a transition rule d  q0  1  q1      Two - binary representation is  10   end-state should be q2  and to process  10   we just need to add one more transition rule d  q1  0  q2 Path    q0 -1  q1 -0  q2    Three - in binary it is  11   end-state is q3  and we need to add a transition rule d  q1  1  q3 Path    q0 -1  q1 -1  q3      Four - in binary  100   end-state is q4  TD already processes prefix string  10  and we just need to add a new transition rule d  q2  0  q4 Path    q0 -1  q1 -0  q2 -0  q4                     Figure-2      Step-3  Five   101 Above transition diagram in figure-2 is still incomplete and there are many missing edges  for an example no transition is defined for d  q2  1 -   And the rule should be present to process strings like  101   Because  101    5 is divisible by 5  and to accept  101  I will add  d  q2  1  q0 in above figure-2  Path    q0 -1  q1 -0  q2 -1  q0  with this new rule  transition diagram becomes as follows                    Figure-3      Below in each step I pick next subsequent binary number to add a missing edge until I get TD as a  complete DFA     Step-4  Six   110   We can process  11  in present TD in figure-3 as    q0 -11  q3  -0      Because 6   5   1 this means to add one rule d  q3  0  q1                Figure-4      Step-5  Seven   111    --------------------------------------------------------------    Number  Binary  Remainder  5   End-state   Path          Add           ------ ------ ------------- --------- ------------ -----------     Seven   111     7   5   2      q2          q0-11 q3      q3-1 q2        --------------------------------------------------------------                 Figure-5      Step-6  Eight   1000    ----------------------------------------------------------    Number  Binary  Remainder  5   End-state   Path        Add         ------ ------ ------------- --------- ---------- ---------     Eight   1000    8   5   3      q3         q0-100 q4    q4-0 q3      ----------------------------------------------------------                 Figure-6      Step-7  Nine   1001       ----------------------------------------------------------    Number  Binary  Remainder  5   End-state   Path        Add         ------ ------ ------------- --------- ---------- ---------     Nine    1001    9   5   4      q4         q0-100 q4    q4-1 q4      ----------------------------------------------------------                 Figure-7      In TD-7  total number of edges are 10    Q    S   5    2  And it is a complete DFA that can accept all possible binary strings those decimal equivalent is divisible by 5   Design DFA accepting Ternary numbers divisible by number n   Step-1 Exactly same as for binary  use figure-1     Step-2 Add Zero  One  Two    ------------------------------------------------------    Decimal  Ternary  Remainder  5   End-state     Add            ------- ------- ------------- --------- --------------     Zero     0        0              q0          d  q0 0  q0      ------- ------- ------------- --------- --------------     One      1        1              q1          d  q0 1  q1      ------- ------- ------------- --------- --------------     Two      2        2              q2          d  q0 2  q3      ------------------------------------------------------                 Figure-8      Step-3 Add Three  Four  Five      -----------------------------------------------------    Decimal  Ternary  Remainder  5   End-state    Add            ------- ------- ------------- --------- -------------     Three    10       3              q3          d  q1 0  q3     ------- ------- ------------- --------- -------------     Four     11       4              q4          d  q1 1  q4     ------- ------- ------------- --------- -------------     Five     12       0              q0          d  q1 2  q0     -----------------------------------------------------                 Figure-9      Step-4 Add Six  Seven  Eight    -----------------------------------------------------    Decimal  Ternary  Remainder  5   End-state    Add            ------- ------- ------------- --------- -------------     Six      20       1              q1          d  q2 0  q1     ------- ------- ------------- --------- -------------     Seven    21       2              q2          d  q2 1  q2     ------- ------- ------------- --------- -------------     Eight    22       3              q3          d  q2 2  q3     -----------------------------------------------------                 Figure-10      Step-5 Add Nine  Ten  Eleven    -----------------------------------------------------    Decimal  Ternary  Remainder  5   End-state    Add            ------- ------- ------------- --------- -------------     Nine     100      4              q4          d  q3 0  q4     ------- ------- ------------- --------- -------------     Ten      101      0              q0          d  q3 1  q0     ------- ------- ------------- --------- -------------     Eleven   102      1              q1          d  q3 2  q1     -----------------------------------------------------                 Figure-11      Step-6 Add Twelve  Thirteen  Fourteen    ------------------------------------------------------    Decimal   Ternary  Remainder  5   End-state    Add            -------- ------- ------------- --------- -------------     Twelve    110      2              q2          d  q4 0  q2     -------- ------- ------------- --------- -------------     Thirteen  111      3              q3          d  q4 1  q3     -------- ------- ------------- --------- -------------     Fourteen  112      4              q4          d  q4 2  q4     ------------------------------------------------------                 Figure-12      Total number of edges in transition diagram figure-12 are 15    Q    S   5   3  a complete DFA   And this DFA can accept all strings consist over  0  1  2  those decimal equivalent is divisible by 5  If you notice at each step  in table there are three entries because at each step I add all possible outgoing edge from a state to make a complete DFA  and I add an edge so that qr state gets for remainder is r      To add further  remember union of two regular languages are also a regular  If you need to design a DFA that accepts binary strings those decimal equivalent is either divisible by 3 or 5  then draw two separate DFAs for divisible by 3 and 5 then union both DFAs to construct target DFA  for 1  lt   n  lt   10 your have to union 10 DFAs       If you are asked to draw DFA that accepts binary strings such that decimal equivalent is divisible by 5 and 3 both then you are looking for DFA of divisible by 15   but what about 6 and 8     Note  DFAs drawn with this technique will be minimized DFA only when there is no common factor between number n and base e g  there is no between 5 and 2 in first example  or between 5 and 3 in second example  hence both DFAs constructed above are minimized DFAs  If you are interested to read further about possible mini states for number n and base b read paper  Divisibility and State Complexity    below I have added a Python script  I written it for fun while learning Python library pygraphviz  I am adding it I hope it can be helpful for someone in someway   Design DFA for base  b  number strings divisible by number  n    So we can apply above trick to draw DFA to recognize number strings in any base  b  those are divisible a given number  n   In that DFA total number of states will be n  for n remainders  and number of edges should be equal to  b     n   mdash  that is complete DFA   b    number of symbols in language of DFA and  n    number of states   Using above trick  below I have written a Python Script to Draw DFA for input base and number  In script  function divided by N populates DFA s transition rules in base   number steps  In each step-num  I convert num into number string num s using function baseN    To avoid processing each number string  I have used a temporary data-structure lookup table  In each step  end-state for number string num s is evaluated and stored in lookup table to use in next step   For transition graph of DFA  I have written a function draw transition graph using Pygraphviz library  very easy to use   To use this script you need to install graphviz  To add colorful edges in transition diagram  I randomly generates color codes for each symbol get color dict function      usr bin env python import pygraphviz as pgv from pprint import pprint from random import choice as rchoice  def baseN n  b  syms  0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ            converts a number  n  into base  b  string         return   n    0  and syms 0   or           baseN n  b  b  syms  lstrip syms 0     syms n   b    def divided by N number  base               constructs DFA that accepts given  base  number strings     those are divisible by a given  number              ACCEPTING STATE   START STATE    0      SYMBOL 0    0      dfa             str from state                 str symbol    to state  for symbol in range base                    for from state in range number            dfa START STATE  SYMBOL 0    ACCEPTING STATE        lookup table  keeps track   number string  -- gt  dfa -- gt   end state      lookup table     SYMBOL 0  ACCEPTING STATE   setdefault     for num in range number   base           end state   str num   number          num s   baseN num  base          before end state   lookup table num s  -1   START STATE          dfa before end state  num s -1     end state         lookup table num s  end state      return dfa  def symcolrhexcodes symbols               returns dict of color codes mapped with alphabets symbol in symbols             return           symbol         join               rchoice  8A6C2B590D1F4E37   for   in  FFFFFF                     for symbol in symbols        def draw transition graph dfa  filename  filename        ACCEPTING STATE   START STATE    0      colors   symcolrhexcodes dfa START STATE  keys          draw transition graph     tg   pgv AGraph strict False  directed True  decorate True      for from state in dfa          for symbol  to state in dfa from state  iteritems                tg add edge  Q s  from state   Q s  to state                          label symbol  color colors symbol                           fontcolor colors symbol          add intial edge from an invisible node      tg add node  null   shape  plaintext   label  start       tg add edge  null    Q s  START STATE          make end acception state as  doublecircle      tg get node  Q s  ACCEPTING STATE  attr  shape      doublecircle      tg draw filename  prog  circo       tg close    def print transition table dfa       print  DFA accepting number string in base    base s                 those are divisible by    number s                         base   len dfa  0                      number   len dfa         pprint dfa   if   name         main         number   input   Enter NUMBER         base   input   Enter BASE of number system         dfa   divided by N number  base       print transition table dfa      draw transition graph dfa    Execute it     study divide-5 script  python script py  Enter NUMBER  5 Enter BASE of number system  4 DFA accepting number string in base  4  those are divisible by  5     0     0    0    1    1    2    2    3    3      1     0    4    1    0    2    1    3    2      2     0    3    1    4    2    0    3    1      3     0    2    1    3    2    4    3    0      4     0    1    1    2    2    3    3    4      study divide-5 script  ls script py filename png   study divide-5 script  display filename   Output         DFA accepting number strings in base 4 those are divisible by 5   Similarly  enter base   4 and number   7 to generate - dfa accepting number string in base  4  those are divisible by  7  Btw  try changing filename to  png or  jpeg     References those I use to write this script    10122  Function baseN from  convert integer to a string in a given numeric base in python    10123  To install  pygraphviz    Python does not see pygraphviz    10124  To learn use of Pygraphviz   Python-FSM    10125  To generate random hex color codes for each language symbol   How would I make a random hexdigit code generator using  join and for loops

User · Answer

You can build DFA using simple modular arithmetics. We can interpret w which is a string of k-ary numbers using a following rule

V[0] = 0
V[i] = (S[i-1] * k) + to_number(str[i])

V[|w|] is a number that w is representing. If modify this rule to find w mod N, the rule becomes this.

V[0] = 0
V[i] = ((S[i-1] * k) + to_number(str[i])) mod N

and each V[i] is one of a number from 0 to N-1, which corresponds to each state in DFA. We can use this as the state transition.

See an example.

k = 2, N = 5

| V | (V*2 + 0) mod 5     | (V*2 + 1) mod 5     |
+---+---------------------+---------------------+
| 0 | (0*2 + 0) mod 5 = 0 | (0*2 + 1) mod 5 = 1 |
| 1 | (1*2 + 0) mod 5 = 2 | (1*2 + 1) mod 5 = 3 |
| 2 | (2*2 + 0) mod 5 = 4 | (2*2 + 1) mod 5 = 0 |
| 3 | (3*2 + 0) mod 5 = 1 | (3*2 + 1) mod 5 = 2 |
| 4 | (4*2 + 0) mod 5 = 3 | (4*2 + 1) mod 5 = 4 |

k = 3, N = 5

| V | 0 | 1 | 2 |
+---+---+---+---+
| 0 | 0 | 1 | 2 |
| 1 | 3 | 4 | 0 |
| 2 | 1 | 2 | 3 |
| 3 | 4 | 0 | 1 |
| 4 | 2 | 3 | 4 |

Now you can see a very simple pattern. You can actually build a DFA transition just write repeating numbers from left to right, from top to bottom, from 0 to N-1.

[regex] Design DFA accepting binary strings divisible by a number 'n'

The answer is

Examples related to regex

Examples related to automata

Examples related to dfa

Tags