Below I wrote an answer for n equal to 5, but you can use the same approach for drawing DFA for any value of n and "any positional number system", for example binary, triple ...
First leave the term βFull DFAβ, the DFA defined in the full domain in the format Ξ΄: Q Γ Ξ£ β Q is called βFull DFAβ. In other words, we can say; in the transition diagram of the full DFA there is no missing edge (for example, from each state in Q there is one outgoing edge present for each language symbol in Ξ£). Note: Once we define a partial DFA as Ξ΄ β Q Γ Ξ£ β Q (Read: How βΞ΄: Q Γ Ξ£ β Qβ is read in the definition of DFA ).
A DFA construct that takes binary numbers divisible by the number "n":
Step 1 When you divide the number Ο by n , then the reminder can be either 0, 1, ..., (n - 2) or (n - 1). If the remainder 0 means that Ο is divisible by n otherwise. Thus, in my DFA there will be a state q r , which will correspond to the residual value of r , where 0 <= r <= (n - 1) , and the total number of states in the DFA is n .
After processing the number string Ο over Ξ£, the final state q r means that Ο% n => r (% reminder operator).
In any state machine, state assignment is similar to a memory element. The state in the atom stores some information, such as a fan switch, that can determine if the fan is in the off state or in the 'on' state. For n = 5, five states in the DFA correspond to five reminders as follows:
- The state q 0 is reached if the reminder is 0. The state q 0 is the final state (receiving state). This is also an initial condition.
- State q 1 reaches, if the reminder is 1, an undefined state.
- State q 2 , if the reminder is 2, the state is not final.
- State q 3 , if the reminder is 3, the state is not final.
- State q 4 , if the reminder is 4, the state is not final.
Using the above information, we can begin to draw a transition diagram of five states as follows:
Rice-1
So, 5 states for 5 residual values. After processing the string Ο, if the final state becomes q 0 , this means that the decimal equivalent of the input string is divided by 5. In the above figure, q 0 marks the final state as two concentric circles.
In addition, I defined the transition rule Ξ΄: (q 0 , 0) β q 0 as a self cycle for the character '0' in the state q 0 , this is because the decimal equivalent of any string consists only of '0' is 0, and 0 is divisible by n .
Step 2 : TD above incomplete; and can only process strings '0' s. Now add a few more edges so that it can handle subsequent lines of numbers. The table below shows the new transition rules that you can add as the next step:
ββββββββ¬ββββββββββββββββββββββββββββββ
β Number β Binary β Remainder (% 5) β End-state β
ββββββββΌββββββββββββββββββββββββββββββ
βOne β1 β1 βq 1 β
ββββββββΌββββββββββββββββββββββββββββββ
βTwo β10 β2 βq 2 β
ββββββββΌββββββββββββββββββββββββββββββ
βThree β11 β3 βq 3 β
ββββββββΌββββββββββββββββββββββββββββββ
βFour β100 β4 βq 4 β
ββββββββ΄ββββββββββββββββββββββββββββββ
- To process the binary string
'1' , there must be a transition rule Ξ΄: (q 0 , 1) β q 1 - Two: - the binary representation is
'10' , the final state should be q 2 , and for processing '10' we just need to add another transition rule Ξ΄: (q 1 , 0) β q 2
Way : β (q 0 ) β1 β (q 1 ) β0 β (q 2 ) - Three: - in binary format, this is
'11' , the final state is q 3 , and we need to add the transition rule Ξ΄: (q 1 , 1) β d <yug> 3sub>
Way : β (q 0 ) β1 β (q 1 ) β1 β (q 3 ) - Four: - in binary
'100' , the final state is q 4 . TD already processes the prefix line '10' , and we just need to add a new transition rule: (q 2 , 0) β q 4
Way : β (q 0 ) β1 β (q 1 ) β0 β (q 2 ) β 0 β (q 4 )
Rice-2
Step 3 : Five = 101
Above the transition diagram in Figure-2, it is still incomplete and there are many missing edges; for example, the transition for Ξ΄ is not defined: (q 2 , 1) - ? . And a rule must be present to handle strings such as '101' .
Since '101' = 5 is divisible by 5 and takes '101' , I will add Ξ΄: (q 2 , 1) β q 0 in the above figure-2.
Path: β (q 0 ) β1 β (d <sub> 1sub>) β0 β (d <sub> 2sub>) β1 β (d <sub> 0sub>)
with this new rule, the transition diagram becomes the following:
Rice 3
Below at each step, I select the next subsequent binary number to add the missing edge until I get the TD as "full DFA".
Step 4 : Six = 110.
We can process '11' in the current TD in Figure 3 as: β (q 0 ) β11 β (q 3 ) β0 β ( ) Since 6% 5 = 1, this means adding one rule: (q 3 , 0) β q 1 .
Figure 4
Step 5 : Seven = 111
β β β β β β¬ β¬ β β β β β β β β β β β β β β β β β β β β β β β β β β ββ¬ββββββββββββ
β Number β Binary β Remainder (% 5) β End-state β Path β Add β
β β β β β βΌ βΌ β β β β β β β β β β β β β β β β β β β β β β β β β β ββΌββββββββββββ€
βSeven β111 β7% 5 = 2 βq 2 β q 0 β11 βββ q 3 β q 3 β1 β q 2 β
β β β β β β΄ β΄ β β β β β β β β β β β β β β β β β β β β β β β β β β ββ΄ββββββββββββ
Figure 5
Step 6 : Eight = 1000
β β β β β β¬ β¬ β β β β β β β β β β β β β β β β β β β β β β β β ββββββββββ
β Number β Binary β Remainder (% 5) β End-state β Path β Add β
β β β β β βΌ βΌ β β β β β β β β β β β β β β β β β β β β β β β β ββββββββββ€
βEight β1000 β8% 5 = 3 βq 3 βq 0 β100 β q 4 β q 4 β0 β q 3 β
β β β β β β΄ β΄ β β β β β β β β β β β β β β β β β β β β β β β β ββββββββββ
Figure 6
Step-7 : Nine = 1001
β β β β β β¬ β¬ β β β β β β β β β β β β β β β β β β β β β β β ββββββββββ
β Number β Binary β Remainder (% 5) β End-state β Path β Add β
β β β β β βΌ βΌ β β β β β β β β β β β β β β β β β β β β β β β ββββββββββ€
βNine β1001 β9% 5 = 4 βq 4 βq 0 β100 β q 4 β q 4 β1 β q 4 β
β β β β β β΄ β΄ β β β β β β β β β β β β β β β β β β β β β β β ββββββββββ
Figure 7
In TD-7, the total number of edges is 10 == Q Γ Ξ£ = 5 Γ 2. And this is a complete DFA that can take all possible binary strings, then the decimal equivalent is divided by 5.
DFA construct accepting ternary numbers divisible by n:
Step-1 In the same way as for binary code, use the number-1.
Step-2 Add Zero, One, Two
β β β β β¬ β¬ β β¬ β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β other ββββββ
β Decimal β Ternary β Remainder (% 5) β End-state β Add β
β β β β βΌ βΌ β βΌ β β β β β β β β β β β β β β β β β β β β β β β β ββββββ€
βZero β0 β0 βq0 β Ξ΄: (q0,0) β q0 β
β β β β βΌ βΌ β βΌ β β β β β β β β β β β β β β β β β β β β β β β β ββββββ€
β One β1 β1 βq1 β Ξ΄: (q0,1) β q1 β
β β β β βΌ βΌ β βΌ β β β β β β β β β β β β β β β β β β β β β β β β ββββββ€
βTwo β2 β2 βq2 β Ξ΄: (q0,2) β q3 β
β β β β β΄ β΄ β β΄ β β β β β β β β β β β β β β β β β β β β β β β β ββββββ
Fig-8
Step-3 Add Three, Four, Five
β β β β β¬ β¬ β β¬ β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β other βββββ
β Decimal β Ternary β Remainder (% 5) β End-state β Add β
β β β β βΌ βΌ β βΌ β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β other βββββ€
βThree β10 β3 βq3 β Ξ΄: (q1,0) β q3 β
β β β β βΌ βΌ β βΌ β β β β β β β β β β β β β β β β β β β β β β β β βββββ€
βFour β11 β4 βq4 β Ξ΄: (q1,1) β q4 β
β β β β βΌ βΌ β βΌ β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β other βββββ€
βFive β12 β0 βq0 β Ξ΄: (q1,2) β q0 β
β β β β β΄ β΄ β β΄ β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β other βββββ
Rice-9
Step 4 Add Six, Seven, Eight
β β β β β¬ β¬ β β¬ β β β β β β β β β β β β β β β β β β β β β β β β βββββ
β Decimal β Ternary β Remainder (% 5) β End-state β Add β
β β β β βΌ βΌ β βΌ β β β β β β β β β β β β β β β β β β β β β β β β βββββ€
βSix β20 β1 βq1 β Ξ΄: (q2,0) β q1 β
β β β β βΌ βΌ β βΌ β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β other βββββ€
β Seven β21 β2 βq2 β Ξ΄: (q2,1) β q2 β
β β β β βΌ βΌ β βΌ β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β other βββββ€
βEight β22 β3 βq3 β Ξ΄: (q2,2) β q3 β
β β β β β΄ β΄ β β΄ β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β βββββ
Figure 10
Step 5 Add nine, ten, eleven
β β β β β¬ β¬ β β¬ β β β β β β β β β β β β β β β β β β β β β β β β βββββ
β Decimal β Ternary β Remainder (% 5) β End-state β Add β
β β β β βΌ βΌ β βΌ β β β β β β β β β β β β β β β β β β β β β β β β βββββ€
βNine β100 β4 βq4 β Ξ΄: (q3,0) β q4 β
β β β β βΌ βΌ β βΌ β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β other βββββ€
βTen β101 β0 βq0 β Ξ΄: (q3,1) β q0 β
β β β β βΌ βΌ β βΌ β β β β β β β β β β β β β β β β β β β β β β β β βββββ€
βEleven β102 β1 βq1 β Ξ΄: (q3,2) β q1 β
β β β β β΄ β΄ β β΄ β β β β β β β β β β β β β β β β β β β β β β β β βββββ
Figure 11
Step-6 Add Twelve, Thirteen, Fourteen
ββ β β β β¬ β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β ββββββ
β Decimal β Ternary β Remainder (% 5) β End-state β Add β
ββ β β β βΌ β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β ββββββ€
β Twelve β110 β2 βq2 β Ξ΄: (q4,0) β q2 β
ββ β β β βΌ β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β ββββββ€
βThirteenβ111 β3 βq3 β Ξ΄: (q4,1) β q3 β
β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β ββββββ€
βFourteenβ112 β4 βq4 β Ξ΄: (q4,2) β q4 β
β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β β ββββββ
<T411>
Rice-12
The total number of edges in the -12 transition diagram is 15 = Q Γ Ξ£ = 5 * 3 (full DFA). And this DFA can accept all strings consisting of {0, 1, 2}, these decimal equivalents are divided by 5.
If you noticed at each step, there are three entries in the table, because at each step I add all possible outgoing edges from the state to make a full DFA (and add an edge to get the state q r for the remainder r )!
To add further, remember that combining two regular languages ββis also regular. If you need to create a DFA that accepts binary strings, then the decimal equivalent is divisible by 3 or 5, then draw two separate DFAs divisible by 3 and 5, then combine both DFAs to build the target DFA (for 1 <= n <= 10 for you have a union of 10 DFAs).
If you are asked to draw a DFA that accepts binary strings in such a way that the decimal equivalent is divisible by 5 and 3, then you are looking for DFAs divisible by 15 (but what about 6 and 8?).
Note: DFAs drawn using this technique will minimize DFAs only when there is no common coefficient between the number n and the base, for example. in the first example, there are no 5 to 2 or 5 to 3 in the second example, so both DFAs built above are minimized DFAs. If you are interested in learning about the possible mini-states for the number n and base b , read the document: Divisibility and State Complexity .
below I added a Python script, I wrote it for fun while learning the Python library pygraphviz. I add it, I hope that it can be useful to someone in something.
DFA design for base numbers 'b' divisible by number 'n':
So we can apply the above trick to draw a DFA to recognize numeric strings in any base 'b' that are divisible by a given number 'n' . In this DFA, the total number of states will be n (for n residues), and the number of edges should be equal to 'b' * 'n' - that is, the full DFA: 'b' = the number of characters in the DFA language and 'n' = the number of states.
Using the trick above, below I wrote Python Script to draw a DFA to enter base and number . In the script, the divided_by_N function populates the DFA transition rules in the base * number steps. In each num step, I convert num to the num_s number string using the baseN() function. To avoid processing each numeric string, I used the lookup_table temporary data lookup_table . At each step, the final state for the num_s numeric string is evaluated and stored in lookup_table for use in the next step.
For the DFA transition graph, I wrote the draw_transition_graph function using the Pygraphviz library (very easy to use). To use this script, you need to install graphviz . To add colorful edges to the transition diagram, I randomly generate color codes for each function of the get_color_dict symbol.
Run 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 numeric strings in base 4 is divided by 5
In the same way, enter base = 4 and number = 7 to generate - dfa, taking a number string in the base "4", which are divided by "7"
Btw, try changing filename to .png or .jpeg .
<sub> The links that I use to write this script are:
β baseN function from "convert integer to string in given numeric base in python"
β To install "pygraphviz": "Python does not see pygraphviz"
β To learn about using Pygraphviz: "Python-FSM"
β To generate random hexadecimal color codes for each character in the language: "How to create a random hexdigit code generator using .join and for loops?" Sub>