那些遇到过的问题

设计DFA接受可被数字'n'整除的二进制字符串

Nav*_*een 68 regex automata dfa

我需要学习如何设计DFA,以便给定任何数字'n',它接受二进制字符串{0,1},其十进制等效数可以被'n'整除.

不同的'n'会有不同的DFA,但有人可以给出一个基本的方法,我应该遵循任何数字0 <n <10.

Gri*_*han 210

下面,我已经写了一个n等于5 的答案,但你可以应用相同的方法为任何值n和'任何位置数系统' 绘制DFA,例如二进制,三元......

首先使用"完全DFA"一词,在完整域上定义的DFA 在？中:Q×?? Q称为"完全DFA".换句话说,我们可以说; 在完整DFA的转换图中,没有缺失边缘(例如,从Q中的每个状态,对于每个语言符号,存在一个外出边缘？).注意:有时我们将部分 DFA 定义为？？Q×?? Q(读:如何"？:Q×?? Q"在DFA的定义中读取).

设计DFA接受可被数字'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:

  1. 状态q 0,如果提醒是0状态q达到0 是(接受状态)的最终状态.它也是一个初始状态.
  2. 如果提醒为1,则为非最终状态,状态q 1到达.
  3. 状态q 2如果提醒是2,则是非最终状态.
  4. 状态q 3如果提醒是3,则是非最终状态.
  5. 状态q 4如果提醒是4,则是非最终状态.

使用以上信息,我们可以开始绘制五种状态的转换图TD,如下所示:

fig-1
图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       ?
???????????????????????????????????????
  1. To process binary string '1' there should be a transition rule ?:(q0, 1)?q1
  2. 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)
  3. 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)
  4. 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)

fig-2 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:

fig-3 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.

fig-4 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    ?
????????????????????????????????????????????????????????????????

fig-5 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  ?
????????????????????????????????????????????????????????????

fig-6 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  ?
????????????????????????????????????????????????????????????

fig-7 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  ?
????????????????????????????????????????????????????????

fig-8
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 ?
???????????????????????????????????????????????????????

fig-9
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 ?
???????????????????????????????????????????????????????

fig-10
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 ?
???????????????????????????????????????????????????????

fig-11
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 ?
????????????????????????????????????????????????????????

fig-12
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)
Run Code Online (Sandbox Code Playgroud)

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
Run Code Online (Sandbox Code Playgroud)

Output:

base_4_divided_5_best
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?"

  • 参考[这里](http://codereview.stackexchange.com/a/85174/6692)[*检查数字是否可被9*整除](http://codereview.stackexchange.com/q/85163/6692 ). (5认同)
  • 如何证明这个解决方案？ (4认同)

小智 6

我知道我已经很晚了,但我只是想在@Grijesh提供的正确答案中添加一些内容.我想指出@Grijesh提供的答案不会产生最小的DFA.虽然答案肯定是获得DFA的正确方法,但如果你需要最小的DFA,你将需要调查你的除数.

例如,在二进制数中,如果除数是2的幂(即2 ^ n),则所需的最小状态数将是n + 1.你会如何设计这样的自动机？只需查看二进制数的属性即可.对于一个数字,比如8(即2 ^ 3),它的所有倍数都将最后3位作为0.例如,二进制中的40是101000.因此,对于一种语言来接受任何可被8整除的数字,我们只需要一个看到最后3位为0的自动机,我们可以只用4个状态而不是8个状态.这是机器复杂性的一半.

实际上,这可以扩展到任何基础.对于三元基数系统,如果我们需要设计一个自动机用于9的可除性,我们只需要看看输入的最后2个数是否为0.这可以在3个状态中再次完成.

虽然如果除数不是那么特殊,那么我们只需要通过@Grijesh的答案.例如,在二元系统中,如果我们采用3或7或21的除数,我们将只需要那么多个状态.因此,对于二进制系统中的任何奇数n,我们需要n个状态来定义接受n的所有倍数的语言.另一方面,如果数字是偶数但不是2的幂(仅在二进制数的情况下),那么我们需要将数字除以2直到我们得到一个奇数,然后我们可以找到最小数量的状态添加生成的奇数和我们除以2的次数.

例如,如果我们需要找到接受所有可被20整除的二进制数的DFA的最小状态数,我们会:

20/2 = 10 
10/2 = 5
Run Code Online (Sandbox Code Playgroud)

因此我们的答案是5 + 1 + 1 = 7.(1 + 1,因为我们将数字20除以两次).

归档时间：

查看次数：

107252 次

最近记录：

6 年，11 月 前
如何将任何基数中的整数转换为字符串？ 186
Python没有看到pygraphviz 38
"D:Q×Σ→Q"如何在DFA(确定性有限自动机)的定义中读取？ 7
如何使用.join和for循环创建随机hexdigit代码生成器？ 7
二进制数的正则表达式可被3整除 6
更多相关链接
相关归档
检查字符串是否为有效URL的最佳正则表达式是什么？ 751
使用sed和grep/egrep进行搜索和替换 95
如何在Perl中找到正则表达式匹配的位置？ 33
使用正则表达式查找带有五个字母abcde的单词,每个字母按任意顺序出现一次,两者之间没有中断 14
Awk:只分裂2个或更多空格 11
在Java中用'\\'替换单个'\' 10
.net Regular Expression可以匹配任何语言的任何类型的字母 9
在Oracle中regexp_replace vs translate的性能？ 8
正则表达式与.find(),没有结果 7
使用PHP剥离HTML注释但是离开条件 6
难疑归档
如何删除子模块？ 3366
C++中指针变量和引用变量之间有什么区别？ 3115
如何在Git中检索当前提交的哈希值？ 1788
.gitignore和.gitkeep有什么区别？ 1776
int32的最大值是多少？ 1383
如何在Linux shell脚本中提示是/否/取消输入？ 1352
虚拟成员在构造函数中调用 1270
我是否提交了由npm 5创建的package-lock.json文件？ 1164
退出申请不赞成？ 1131
让Chrome接受自签名的localhost证书 1080