deviseDFA接受可被数字“n”整除的二进制string

我需要学习如何devise一个DFA，给定任意数字'n'，它接受二进制string{0,1}，其十进制等效数字可以被'n'整除。 不同的'n'会有不同的DFA，但是有人可以给我一个基本的方法，我应该遵循任何数字0 <n <10。

Answer 1

下面，我写了一个n等于5的答案，但是你可以应用相同的方法来绘制任意值的n和'任何位置数字系统'，例如二进制，三元…

首先是“完全DFA”这个术语， 定义在完整领域的 DFA：Q×Σ→Q称为“完全DFA”。 换句话说，我们可以说; 在完整DFA的转换图中，没有丢失边缘（例如，从Q中的每个状态出发，Σ中每个语言符号都有一个出边）。 注意：有时我们将部分 DFA定义为δ⊆Q×Σ→Q（阅读： 在DFA的定义中如何读取“δ：Q×Σ→Q” ）。

deviseDFA接受可被数字“n”整除的二进制数字：

第一步 ：当你用n除数n提醒可以是0,1，…，（n-2）或（n-1）。 如果余数为0 ，则意味着ω可以被n整除，否则不能。 因此，在我的DFA中，将有一个状态q _r ，它将对应于一个余数值r ，其中0 <= r <= (n - 1) ，DFA中的状态总数为n 。
在Σ上处理一个数字串ω后，结束状态为q _r意味着ω％n => r（％提醒算子）。

在任何自动机中，状态的目的就像记忆元素。 在一个atomata状态存储一些信息，如风扇的开关，可以判断风扇是处于“closures”还是处于“开启”状态。 对于n = 5，DFA中的五个状态对应五个提醒信息如下：

1. 如果提醒是0，则状态q ₀达到。状态q ₀是最终状态（接受状态）。 这也是一个初始状态。
2. 如果提醒为1，则状态q ₁达到非终止状态。
3. 状态q ₂如果提醒是2，一个非最终状态。
4. 状态q ₃如果提醒是3，一个非最终状态。
5. 状态q ₄如果提醒是4，非最终状态。

使用以上信息，我们可以开始绘制五种状态的转换图TD：

图1

所以，5个状态为5个余数值。 如果结束状态变为q ₀ ，则表示inputstring的十进制等价值可以被5整除。在上图中，q ₀标记为两个同心圆的最终状态。
此外，我已经定义了一个转移规则δ：（q _0，0 ）→q ₀作为状态q _0的符号'0'的自循环，这是因为任何只包含'0'string的十进制等价值为0， 0是可以被n整除的。

第二步 ：上面的TD不完整; 并且只能处理'0'string。 现在添加更多的边缘，以便它可以处理后续数字的string。 查看下面的表格，显示可以添加下一步的新过渡规则：

 ┌──────┬──────┬─────────────┬─────────┐
 │ 数字 │ 二进制 │ 剩余（％5） │ 结束状态 │
 ├──────┼──────┼─────────────┼─────────┤
 │一││││ 一 │
 ├──────┼──────┼─────────────┼─────────┤
 │Two│10│2│q2│
 ├──────┼──────┼─────────────┼─────────┤
 │Three│11│3│q3│
 ├──────┼──────┼─────────────┼─────────┤
 │Four│100│4│q4│
 └──────┴──────┴─────────────┴─────────┘

1. 为了处理二进制串'1' ，应该有一个转换规则δ：（q _0,1 ）→q ₁
2. 二：二进制表示为'10' ，结束状态为q ₂ ，为了处理'10' ，我们只需要增加一个转换规则δ：（q 1，0）→q ₂
   path ：→（q ₀ ）─1→（q ₁ ）─0→（q ₂ ）
3. 三：二进制是'11' ，最终状态是q ₃ ，我们需要添加一个转换规则δ：（q 1，1）→q ₃
   path ：→（q ₀ ）─1→（q ₁ ）─1→（q ₃ ）
4. 四： – 在二进制'100' ，最终状态是q ₄ 。 TD已经处理前缀string'10' ，我们只需要添加一个新的转换规则δ：（q 2，0）→q ₄
   path ：→（q ₀ ）─1→（q ₁ ）─0→（q ₂ ）─0→（q ₄ ）

图-2

第三步 ：五= 101
上面的图2中的转换图仍然是不完整的，并且存在许多丢失的边，例如，没有为δ定义转换：（q _2，1 ） – ？ 。 规则应该存在来处理像'101'这样'101'string。
因为'101' = 5可以被5整除，而接受'101'我会在上面的图2中加上δ：（q _2，1 ）→q ₀ 。
path： →（q ₀ ）─1→（q ₁ ）─0→（q ₂ ）─1→（q ₀ ）
用这个新规则，转换图变成如下：

图-3-

在下面的每个步骤中，我挑选下一个后续的二进制数来添加一个缺失的边，直到我将TD作为“完整的DFA”。

第四步 ：六= 110。

我们可以在图3中的TD中处理'11' ：→（q ₀ ）─11→（q ₃ ）─0→（ ？ ）。 因为6％5 = 1，这意味着增加一个规则δ：（q 3，0）→q ₁ 。

图-4-

步骤5 ：七= 111

 ┌──────┬──────┬─────────────┬─────────┬─────────── ─┬───────────┐
 │ 数字 │ 二进制 │ 剩余（％5） │ 结束状态 │ path │ 添加 │
 ├──────┼──────┼─────────────┼─────────┼─────────── ─┼───────────┤
 │Seven│111│7％5 = 2│q2│q 0──11→q 3│q 3─1→q 2│
 └──────┴──────┴─────────────┴─────────┴─────────── ─┴───────────┘

图-5

第六步 ：八= 1000

 ┌──────┬──────┬─────────────┬─────────┬──────────┬ ─────────┐
 │ 数字 │ 二进制 │ 剩余（％5） │ 结束状态 │ path │ 添加 │
 ├──────┼──────┼─────────────┼─────────┼──────────┼ ─────────┤
 │Eight│1000│8％5 = 3│q3│q0──100→q 4│q 4─0→q 3│
 └──────┴──────┴─────────────┴─────────┴──────────┴ ─────────┘

图-6

第七步 ：九= 1001

 ┌──────┬──────┬─────────────┬─────────┬──────────┬ ─────────┐
 │ 数字 │ 二进制 │ 剩余（％5） │ 结束状态 │ path │ 添加 │
 ├──────┼──────┼─────────────┼─────────┼──────────┼ ─────────┤
 │Nine│1001│9％5 = 4│q4│q0─100→q 4│q 4─1→q 4│
 └──────┴──────┴─────────────┴─────────┴──────────┴ ─────────┘

图-7

在TD-7中，边的总数是10 == Q×Σ= 5×2。它是一个完整的DFA，可以接受所有可能的二进制串，那些十进制等价的可以被5整除。

deviseDFA接受可被数字n整除的三元数字：

步骤1与二进制文件完全相同，使用figure-1。

步骤2添加零，一，二

 ┌───────┬───────┬─────────────┬─────────┬───────── ─────┐
 │ 小数 │ 三元 │ 剩余（％5） │ 结束状态 │ 添加 │
 ├───────┼───────┼─────────────┼─────────┼───────── ─────┤
 │Zero│0│0│q0│δ：（q0,0）→q0│
 ├───────┼───────┼─────────────┼─────────┼───────── ─────┤
 │1│1│q1│δ：（q0,1）→q1│
 ├───────┼───────┼─────────────┼─────────┼───────── ─────┤
 │Two│2│2│q2│δ：（q0,2）→q3│
 └───────┴───────┴─────────────┴─────────┴───────── ─────┘

图8

第三步添加三，四，五

 ┌───────┬───────┬─────────────┬─────────┬───────── ────┐
 │ 小数 │ 三元 │ 剩余（％5） │ 结束状态 │ 添加 │
 ├───────┼───────┼─────────────┼─────────┼───────── ────┤
 │3│10│3│q3│δ：（q1,0）→q3│
 ├───────┼───────┼─────────────┼─────────┼───────── ────┤
 │4│4│q4│δ：（q1,1）→q4│
 ├───────┼───────┼─────────────┼─────────┼───────── ────┤
 │Five│12│0│q0│δ：（q1,2）→q0│
 └───────┴───────┴─────────────┴─────────┴───────── ────┘

图9

第四步加六，七，八

 ┌───────┬───────┬─────────────┬─────────┬───────── ────┐
 │ 小数 │ 三元 │ 剩余（％5） │ 结束状态 │ 添加 │
 ├───────┼───────┼─────────────┼─────────┼───────── ────┤
 │six│20│1│q1│δ：（q2,0）→q1│
 ├───────┼───────┼─────────────┼─────────┼───────── ────┤
 │7：│21│2│q2│δ：（q2,1）→q2│
 ├───────┼───────┼─────────────┼─────────┼───────── ────┤
 │Eight│22│3│q3│δ：（q2,2）→q3│
 └───────┴───────┴─────────────┴─────────┴───────── ────┘

图-10

第五步加九，十，十一

 ┌───────┬───────┬─────────────┬─────────┬───────── ────┐
 │ 小数 │ 三元 │ 剩余（％5） │ 结束状态 │ 添加 │
 ├───────┼───────┼─────────────┼─────────┼───────── ────┤
 │Nine│100│4│q4│δ：（q3,0）→q4│
 ├───────┼───────┼─────────────┼─────────┼───────── ────┤
 │Ten│101│0│q0│δ：（q3,1）→q0│
 ├───────┼───────┼─────────────┼─────────┼───────── ────┤
 │Eleven│102│1│q1│δ：（q3,2）→q1│
 └───────┴───────┴─────────────┴─────────┴───────── ────┘

图11

第六步加十二，十三，十四

 ┌────────┬───────┬─────────────┬─────────┬──────── ─────┐
 │ 小数 │ 三元 │ 剩余（％5） │ 结束状态 │ 添加 │
 ├────────┼───────┼─────────────┼─────────┼──────── ─────┤
 │Twelve│110│2​​│q2│δ：（q4,0）→q2│
 ├────────┼───────┼─────────────┼─────────┼──────── ─────┤
 │Thirteen│111│3│q3│δ：（q4,1）→q3│
 ├────────┼───────┼─────────────┼─────────┼──────── ─────┤
 │14││112│4│q4│δ：（q4,2）→q4│
 └────────┴───────┴─────────────┴─────────┴──────── ─────┘

图-12

转换图图-12中的边的总数是15 = Q×Σ= 5 * 3（一个完整的DFA）。 而且这个DFA可以接受所有由{0,1,2}构成的string，这些十进制等价值可以被5整除。
如果你注意到在每一步，表中有三个条目，因为在每一步我添加一个状态的所有可能的传出边缘，使一个完整的DFA（我添加一个边缘，使q _r状态得到余数是r ）！

要进一步补充，记住两种常规语言的联合也是一个常规。 如果您需要devise一个接受二进制string的DFA，则这些十进制等价物可以被3或5整除，然后绘制两个单独的DAs，可以被3和5整除，然后将两个DFA结合起来构造目标DFA（1 <= n <= 10你必须联合10个DFA）。

如果要求您绘制接受二进制string的DFA，以使得十进制等值可以被5和3整除，那么您正在寻找可被15整除的DFA（但是6和8是多less？）。

注意：只有当数字n和基数之间没有公共因素时，用这种技术绘制的DFA才会被最小化DFA，例如在第一个例子中没有 5和2之间，或者在第二个例子中没有5和3之间，所以上面构build的两个DFA都是最小化了DFA。 如果您有兴趣进一步阅读有关可能的最小状态为n和b基准阅读文件： 可分性和状态的复杂性 。

^{下面我已经添加了一个Python脚本，我在学习Python库pygraphviz的同时写了它。 我正在添加它，我希望它可以在某些方面有所帮助。}

为数字“n”可整除的基本'b'数字stringdeviseDFA：

所以我们可以应用上面的技巧来绘制DFA来识别任意基数'b'数字串，这些数字串可以被整除给定数字'n' 。 在DFA中，状态总数为n （ n余数），边的数量应该等于'b'*'n' – 即完整的DFA：'b'= DFA语言中符号的数量，'n '=州数。

使用上面的技巧，下面我写了一个Python脚本来绘制DFA的inputbase和number 。 在脚本中，函数divided_by_N以base * number步骤填充DFA的转换规则。 在每个步骤中，我使用函数baseN()将num转换为数字串num_s 。 为了避免处理每个数字string，我使用了一个临时的数据结构lookup_table 。 在每个步骤中，对数字串num_s结束状态进行评估并存储在lookup_table ，以便在下一步中使用。

对于DFA的转换图，我使用Pygraphviz库编写了一个函数draw_transition_graph （非常容易使用）。 要使用这个脚本，你需要安装graphviz 。 为了在转换图中添加色彩鲜艳的边缘，我随机生成每个符号get_color_dict函数的颜色代码。

 #!/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) 

执行它：

 ~/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 

输出：

DFA接受基数为4的数字string可以被5整除

类似地，inputbase = 4和number = 7来生成 – dfa接受基数“4”中的数字串，可以被“7”整除，
顺便说一句，尝试将filename更改为.png或.jpeg 。

_{引用那些我用来写这个脚本的人：
➊函数baseN从“将整数转换为python中给定数字库中的string”
➋安装“pygraphviz”： “Python看不到pygraphviz”
➌要学习使用Pygraphviz： “Python-FSM”
➍为每个语言符号生成随机的hex颜色代码： “我将如何使用.join和for循环制作一个随机的hex代码生成器？}

Answer 2

我知道我已经很晚了，但是我只是想为@Grijesh提供的正确答案添加一些内容。 我只想指出，@Grijesh提供的答案不会产生最小的DFA 。 虽然答案肯定是获得DFA的正确方法，但是如果您需要最小的DFA ，则必须查看您的除数。

比如在二进制数中，如果除数是2的幂，即2 ^ n，那么所需的最小状态数将是n + 1。 你将如何devise这样一个自动机？ 只要看看二进制数字的属性。 对于一个数字来说，8是2 ^ 3，它的所有倍数将有最后3位为0.例如，二进制中的40是101000.因此，对于一种语言来接受任何可以被8整除的数字，我们只需要一个自动机，最后3位是0，我们可以在4个状态而不是8个状态中完成。 这是机器的一半复杂性。

事实上，这可以扩展到任何基地。 对于一个三元基数系统，例如，如果我们需要用9来devise一个可分性的自动机，我们只需要看看input的最后2个数字是否为0即可。这又可以在3个状态中完成。

虽然如果除数不那么特殊，那么我们只需要通过@Grijesh的回答。 例如，在二进制系统中，如果我们采用3或7或者21的除数，那么我们只需要有很多个状态。 因此，对于二元系统中的任意奇数n，我们需要n个状态来定义接受n的所有倍数的语言。 另一方面，如果数是偶数，但不是2的幂（只有在二进制数的情况下），那么我们需要将数除以2，直到我们得到一个奇数，然后我们可以find最less的状态数加上产生的奇数和我们除以2的次数。例如，如果我们需要find接受所有可以被20整除的二进制数的DFA的最小状态数，我们做：

 20/2 = 10 10/2 = 5 

因此我们的答案是5 + 1 + 1 = 7 。 （1 + 1，因为我们把数字20分了两次）。