设计接受可被数字“n"整除的二进制字符串的 DFA [英] Design DFA accepting binary strings divisible by a number 'n'
问题描述
我需要学习如何设计一个 DFA，以便给定任何数字n"，它接受二进制字符串 {0, 1}，其十进制等效数可被n"整除.
对于不同的n"会有不同的 DFA，但是有人可以给出一个我应该遵循的基本方法来处理任何数字 0 <≤10.
下面，我已经写了一个 n 等于 5 的答案，但是你可以应用相同的方法来绘制任何值的 DFAn 和任何位置数字系统"，例如二进制、三进制...
首先使用术语完整 DFA"，在完整域上定义的 DFA .
下面我添加了一个 Python 脚本，我在学习 Python 库 pygraphviz 时为了好玩而写的.我正在添加它，希望它可以在某种程度上对某人有所帮助.
为可被数字n"整除的基数b"数字字符串设计 DFA:
所以我们可以应用上面的技巧来绘制 DFA 来识别任何基本 'b' 中的数字字符串，这些字符串可以被给定的数字 'n' 整除.在该 DFA 中，状态总数将为 n(对于 n 余数)并且边数应等于 'b' * 'n' —即完整的 DFA:'b' = DFA 语言中的符号数，'n' = 状态数.
使用上述技巧，下面我编写了一个 Python 脚本来为输入 base 和 number 绘制 DFA.在脚本中，函数 divided_by_N 在 base * number 步骤中填充 DFA 的转换规则.在每个 step-num 中，我使用函数
顺便说一句，尝试将 filename 更改为 .png 或 .jpeg.
<子>参考我用来编写此脚本的那些:
➊ 函数 baseN 来自 将整数转换为 Python 中给定数字基数的字符串"
➋ 要安装pygraphviz":Python 看不到 pygraphviz"
➌ 学习 Pygraphviz 的使用:"Python-FSM"
➍ 为每个语言符号生成随机十六进制颜色代码:"我将如何使用 .join 和 for 循环制作随机十六进制数字代码生成器?"
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 .
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 δ:Q × Σ→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 Σ). Note: Sometime we define partial DFA as δ ⊆ Q × Σ→Q (Read: How does "δ:Q × Σ→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 <= r <= (n - 1), and total number of states in DFA is n.
After processing a number string ω over Σ, 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 δ:(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 δ:(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 δ:(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 δ:(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 δ:(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 δ:(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 δ:(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 δ:(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 × Σ = 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 │ δ:(q0,0)→q0 │ ├───────┼───────┼─────────────┼─────────┼──────────────┤ │One │1 │1 │q1 │ δ:(q0,1)→q1 │ ├───────┼───────┼─────────────┼─────────┼──────────────┤ │Two │2 │2 │q2 │ δ:(q0,2)→q3 │ └───────┴───────┴─────────────┴─────────┴──────────────┘
Figure-8
Step-3 Add Three, Four, Five
┌───────┬───────┬─────────────┬─────────┬─────────────┐ │Decimal│Ternary│Remainder(%5)│End-state│ Add │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Three │10 │3 │q3 │ δ:(q1,0)→q3 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Four │11 │4 │q4 │ δ:(q1,1)→q4 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Five │12 │0 │q0 │ δ:(q1,2)→q0 │ └───────┴───────┴─────────────┴─────────┴─────────────┘
Figure-9
Step-4 Add Six, Seven, Eight
┌───────┬───────┬─────────────┬─────────┬─────────────┐ │Decimal│Ternary│Remainder(%5)│End-state│ Add │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Six │20 │1 │q1 │ δ:(q2,0)→q1 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Seven │21 │2 │q2 │ δ:(q2,1)→q2 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │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 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │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 │ └────────┴───────┴─────────────┴─────────┴─────────────┘
Figure-12
Total number of edges in transition diagram figure-12 are 15 = Q × Σ = 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 <= n <= 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' — 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' -->[dfa]--> '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:
➊ Function baseN from "convert integer to a string in a given numeric base in python"
➋ To install "pygraphviz": "Python does not see pygraphviz"
➌ To learn use of Pygraphviz: "Python-FSM"
➍ To generate random hex color codes for each language symbol: "How would I make a random hexdigit code generator using .join and for loops?"
这篇关于设计接受可被数字“n"整除的二进制字符串的 DFA的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
