用于建模dfas的python库。
dfa的Python项目详细描述
DFA
dfa的简单python实现。
目录
功能：
- 状态可以是任何哈希对象。
- 字母表可以是任意有限的散列对象序列。
- 设计为不可变和哈希的（假设组件是 不可变和散列）。
- 允许转换映射和接受集的设计选择
作为函数而不是显式的
dict或set给出。
安装
如果您只需要使用dfa，您可以运行：
$ pip install dfa
对于开发人员，请注意此项目使用 poetrypython包/依赖项 管理工具。请熟悉它，然后 运行：
$ poetry install
用法
dfaapi以DFA对象为中心。
默认情况下，DFA对象对aDeterministic Finite Acceptor建模，
例如，一种常规语言的识别器。
示例用法：
fromdfaimportDFAdfa1=DFA(start=0,inputs={0,1},label=lambdas:(s%4)==3,transition=lambdas,c:(s+c)%4,)dfa2=DFA(start="left",inputs={"move right","move left"},label=lambdas:s=="left",transition=lambdas,c:"left"ifc=="move left"else"right",)
会员查询
assertdfa1.label([1,1,1,1])assertnotdfa1.label([1,0])assertdfa2.label(["move right"]*100+["move left"])assertnotdfa2.label(["move left","move right"])
过渡和轨迹
assertdfa1.transition([1,1,1])==3assertlist(dfa1.trace([1,1,1]))==[0,1,2,3]
非布尔输出字母
有时，对能够标记单词的自动机建模是很有用的。
使用非布尔字母表。例如，{True, False, UNSURE}。
DFA对象通过指定输出字母表来支持这一点。
UNSURE=Nonedefmy_labeler(s):ifs%4==2:returnNonereturn(s%4)==3dfa3=DFA(start=0,inputs={0,1},label=my_labeler,transition=lambdas,c:(s+c)%4,outputs={True,False,UNSURE},)
注意：如果将outputs设置为None，则不进行检查
输出在输出字母表内。
dfa3=DFA(start=0,inputs={0,1},label=my_labeler,transition=lambdas,c:(s+c)%4,outputs=None,)
摩尔机器
最后，通过重新解释DFA对象的结构，可以
模拟摩尔机器。例如，在3状态计数器dfa1中，
摩尔机器可以输出电流计数。
assertdfa1.transduce(())==()assertdfa1.transduce((1,))==(False,)assertdfa1.transduce((1,1,1,1))==(False,False,False,True)
DFA<；->；字典
注意，dfa提供了从字典中获取的帮助函数
基于确定性过渡系统到DFA的表示
物体和背部。
fromdfaimportdfa2dict,dict2dfa# DFA encoded a nested dictionaries with the following# signature.# <state>: (<label>, {<action>: <next state>})dfa_dict={0:(False,{0:0,1:1}),1:(False,{0:1,1:2}),2:(False,{0:2,1:3}),3:(True,{0:3,1:0})}# Dictionary -> DFAdfa=dict2dfa(dfa_dict,start=0)# DFA -> Dictionarydfa_dict2,start=dfa2dict(dfa)assert(dfa_dict,0)==(dfa_dict2,start)
计算可达状态
# Perform a depth first traversal to collect all reachable states.assertdfa1.states()=={0,1,2,3}
采样路径
通常情况下，采样两个状态之间的路径非常有用，例如a
以及b。dfa使用dfa.utils.paths支持此功能。这个函数
返回单词的生成器w，以便dfa.transition(w, start=b) == a。例如：
fromdfa.utilsimportpathsaccess_strings=paths(dfa1,start=0,end=1,# Optional. If not specified returns all paths# starting at `start`.max_length=7,# Defaults to float('inf')randomize=True,# Randomize the order. Shorter paths still found first.)forwordinaccess_strings:assertdfa1.transition(word,start=0)==1
可视化DFA
dfa可选地支持使用graphviz可视化dfa。使用这个
功能请确保使用draw选项安装dfa。
pipinstalldfa[draw]
或
poetryinstall-Edraw
然后可以简单地使用dfa.draw.write_dot来编写.dot文件
代表DFA。这个.dot文件可以使用
Graphviz支撑工具。
fromdfa.drawimportwrite_dotwrite_dot(dfa1,"path/to/dfa1.dot")
在linux中使用dot命令将生成dfa1的以下呈现。
$ dot -Tsvg path/to/dfa1.dot > dfa1.svg
欢迎加入QQ群-->： 979659372
