1

我正在尝试找到一种在 python 中最小化 DFA 的算法。我找到了一些例子,它们都有代码类。现在,我不知道如何转发放置在 .txt 文件中的 DFA 定义并将它们放入这些类中。.txt 格式如下:

  1. line:由逗号分隔的状态集,按字典顺序排列
  2. line:一组用逗号分隔的字母符号,按字典顺序排列
  3. line:以逗号分隔的可接受状态集,按字典顺序排列
  4. 行:第一个状态
  5. 和所有其他行:格式为当前状态的传递函数,字母符号->下一个状态

定义示例:

dyny,fllf,gdci,gwtj,knos,kole,mjnw,msdl,mtfz,nbat,njgb,nzwx,rzpn,vcsc,zgfx

b,d,e,f,g,k,l,m,n,o,p,q,r,t,u,w

dyny,njgb,zgfx

mtfz

dyny,b->rzpn

dyny,d->msdl

dyny,e->gdci
.
.
.

类的例子

class DFA:

    def __init__(self, states, alphabet, delta, start, accepts):
        self.states = states
        self.start = start
        self.delta = delta
        self.accepts = accepts
        self.alphabet = alphabet
        self.current_state = start

我加载 .txt 文件

f = open('definition.txt','r')

lines = f.readlines()
4

1 回答 1

0

到目前为止,这与自动机的最小化无关,对吧?您正在尝试从某些(给定的)文件格式创建自动机。

由于这是一个家庭作业,我只是给你一些提示:

readlines返回一个列表。您可以通过索引来处理特定的行,即lines[0]第一行、lines[1]第二行等。这些行中的每一行都是一个字符串。以包含状态集(lines[0],它保持'dyny,fllf,gdci,gwtj,knos,kole,mjnw,msdl,mtfz,nbat,njgb,nzwx,rzpn,vcsc,zgfx')的行为例,您可以使用

lines[0].split(',')

用逗号分割它,它会给你一个字符串列表,每个字符串代表一个状态。代表单个转换的那些行遵循稍微复杂的格式:

<state>','<input symbol>'->'<next state>

您想要解析这些行,以便获得上面描述的三个组件。string.split又是你的朋友。您还应该为转换函数 (delta) 确定合适的数据结构。

注意:readlines一次读取整个文件。在实践中,自动机通常很大,在这种情况下,最好以增量方式读取文件。文件对象(f在您的代码中)实现迭代器协议并允许您迭代文件的行。特别是,我建议使用

line1 = f.next()  # Next line (first line, if first call of next)
line2 = f.next()  # Next line
...

对于前四行(获取状态集等)并遍历其余行(转换):

for line in f:
    ...

有关详细信息,请参阅http://docs.python.org/tutorial/inputoutput.html

于 2012-03-20T19:47:23.130 回答