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 回答