乐趣区

关于程序员:DFA最小化

jiezi

一、试验名称

确定有穷自动机的最小化

 

二、试验目标

  1. 输出 DFA，输入等价的状态数起码的 DFA
  2. 实现子集划分算法
  3. 输出和输入均以定义的模式

 

三、试验原理

1、DFA 的定义

一个确定的有穷自动机 M 是一个五元组，M=(K,E,f,S,Z) 其中

a. K 是一个有穷集，它的每个元素称为一个状态；

b. E 是一个有穷字母表，它的每个元素称为一个输出符号；

c. f 是转换函数，是 K×E->K 上的映像，即，如 f(ki,a)=kj(ki∈K,kj∈K) 就意味着，以后状态为 ki，输出字符为 a 时，将转换到下一状态 kj，咱们把 kj 称作 ki 的一个后继状态；

d. S∈K，是惟一的一个初态；

e. Z 蕴含于 K，是一个终态集，终态也称可承受状态或完结状态。

 

2、无用状态

所谓有穷自动机的无用状态，是指这样的状态：从该自动机的开始状态登程，任何串也不能到达的那个状态。或者从这个状态没有通路达到状态。

 

3、状态等价条件

​ a. 一致性条件——状态 s 和 t 必须同时为可承受状态或不可承受状态

​ b. 蔓延性条件——对于所有输出符号，状态 s 和状态 t 必须转换到等价的状态里。

 

四、试验思路

1、输出

​ 依据试验要求，以 DFA 的定义模式输出，即输出 M =(K,E,f,S,Z)，其中 f 另外输出。采纳 putin 作为输出函数，首先输出定义模式，用 split 函数依照’}‘进行宰割，再依照’}’宰割。最初对失去的二维列表 zanshi1 中的元素进行输入，失去 K,E,S,Z。再输出 f 中弧的条数，顺次输出弧。

 

2、move 算法

​ move 算法与 NFA 的确定化里的算法一样，在这里为了求某一子集通过弧达到什么子集而应用 move 算法。思路是：建设一个新列表寄存 move 算法产生的状态汇合，若 f 中的弧的输出符号为 a 或者 b，求通过紧跟 a 或者 b 的下一个状态，将这些状态放于新列表中。

 

3、子集划分算法

​ 定义 operation() 函数为子集划分算法函数，具体执行步骤如下：

​ a. 将 K 中的状态集分为两种：终态集和非终态集，存于 KK 中，KK 寄存最终划分后失去的汇合。

​ b. 设立循环条件，子集划分算法划分最细的状况是每个状态都为一个子集，所以以此作为循环条件。若 KK 中汇合个数不等于 K 中状态个数，则持续循环。

​ c. 设立标记位 llag= 0 用来决定是否跳出循环，每不执行一次划分算法则 llag 加 1，若最终 llag 等于 KK 长度，阐明此次循环没有子集划分，则阐明划分结束，退出循环。

​ d. 对 KK 中的汇合顺次进行操作，判断他们进过 move 算法失去的汇合是否是 KK 中已有的汇合，若是则不执行划分，否则执行划分算法。

​ e. 若执行划分算法，则先算出汇合中首个状态的 move 算法失去的汇合属于哪个已知汇合，再对其余状态进行同样操作，和首个状态 move 算法属于雷同汇合的放于同一个列表中，其余的放于另一个列表中。

​ f. 将 KK 中原来要划分的汇合删除，退出划分后的两个汇合。循环执行上述步骤，晓得 KK 中汇合个数和标记位 llag 值雷同或者 KK 中汇合个数等于 K 中状态个数，则退出循环。

 

4、输入

​ 输入同样为 DFA 的定义模式，先输入 M =(K,E,f,S,Z)，再输入其中的 f。

 

五、试验小结

​ 本次试验次要遇到了以下问题：

1、输出存储问题

​ 输出要求应用定义模式，须要辨别输出的元素，别离失去状态集，输出符号集，初态集以及终态集。通过 python 中的 split 函数将输出的字符串别离以’{‘和’}’离开，再通过循环操作取出失去的二维列表中每一个元素的第二个元素，即为所求的状态集，输出符号集，初态集以及终态集，再输入 f 的具体弧。

 

2、子集划分算法问题

​ 子集划分算法须要对划分后失去的汇合始终执行划分算法，然而会有一个示意划分结束的后果，在程序中通过设立两个条件来判断是否划分结束，一是划分失去的子集个数是否等于状态集中状态个数，若是则阐明每个状态都为一个子集，即必定划分完结。另一判断条件为设置一个标记位，通过观察标记位的数值来判断本次划分算法是否执行，若没有执行则阐明曾经划分结束，同样退出循环。

 

3、输入问题

​ 输入的模式为 DFA 的定义模式，通过对格局的管制，将本来定义中的列表类型都转为汇合类型，最初输入。同时定义中的 f 须要独自输入。

 

六、附件

1、源代码 
K = []  # 状态
E = []  # 符号
f = []  # 弧
f1 = [] # 新弧
S = []  # 初态
Z = []  # 终态
zanshi1 = []  # 寄存五元组模式 1
KK = []  # 最终状态集

#M=({1,2,3,4,5,6,7},{a,b},f,{1},{5,6,7})
# 输出
def putin():
    print('输出 DFA M')
    M = input('以定义模式输出 DFA( 如:M=(K,E,f,S,Z):)')
    N = M.split('}')
    for i in N:
        zanshi1.append(i.split('{'))
    K1 = (zanshi1[0][1])
    K1 =K1.split(',')
    for i in K1:
        K.append(i)
    E1 = (zanshi1[1][1])
    E1 =E1.split(',')
    for i in E1:
        E.append(i)
    S1 = (zanshi1[2][1])
    S1 =S1.split(',')
    for i in S1:
        S.append(i)
    Z1 = (zanshi1[3][1])
    Z1 =Z1.split(',')
    for i in Z1:
        Z.append(i)
    print('输出 f 中弧的条数:')
    n = int(input())
    print('输出弧 ( 别离输出状态 1, 输出符号, 状态 2, 以空格辨别换行完结,ε 示意为 $)')
    for i in range(n):
        f.append([])
        a = input()
        f[len(f)-1] = a.split(' ')
def move(a, e, f):  # a 为列表 e 为一个符号
      s = []
      for i in a:
          for j in range(len(f)):
              if i == f[j][0] and f[j][1] == e:
                  s.append(f[j][2])
      return sorted(s)

# 子集划分算法
def operation():
    a = []
    for x in K:
        if x not in Z:
            a.append(x)
    KK.append(a)
    KK.append(Z)
    while len(KK) != len(K):
        llag = 0
        for i in range(len(KK)):
            ziji = KK[i]
            glag = 0
            for jj in range(len(E)):
                ziji1 = move(ziji, E[jj], f)
                flag = 0
                for k in range(len(KK)):
                    if len(set(ziji1).difference(set(KK[k]))) != 0:
                        flag = flag+1
                if flag == len(KK):
                    glag = glag + 1
                    break
            if glag == 1:
                ilag = jj
                zhenziji1 = []
                zhenziji1.append(ziji[0])
                ziji1 = move(zhenziji1, E[ilag], f)
                for k in range(len(KK)):
                    if len(set(ziji1).difference(set(KK[k]))) == 0:
                        hlag = k
                        break
                zhenziji2 = []
                for j in range(1, len(ziji)):
                    zz = []
                    zz.append(ziji[j])
                    ziji1 = move(zz, E[ilag], f)
                    if len(set(ziji1).difference(set(KK[hlag]))) == 0:
                        zhenziji1.append(ziji[j])
                    else:
                        zhenziji2.append(ziji[j])
                KK.pop(i)
                KK.append(zhenziji1)
                KK.append(zhenziji2)
            else:
                llag = llag+1
        if llag == len(KK):
            break

# 运行
putin()
operation()
for yy in KK:
    if len(yy) >= 2:
        for i in range(1, len(yy)):
            if yy[i] in K:
                K.remove(yy[i])
            if yy[i] in S:
                S.remove(yy[i])
            if yy[i] in Z:
                Z.remove(yy[i])
            for yyy in f:
                if yyy[0] == yy[i]:
                    yyy[0] = yy[0]
                if yyy[2] == yy[i]:
                    yyy[2] = yy[0]
for yy in f:
    if yy not in f1:
        f1.append(yy)
for i in range(len(K)):
    K[i] = int(K[i])
for i in range(len(S)):
    S[i] = int(S[i])
for i in range(len(Z)):
    Z[i] = int(Z[i])
print('输入最小化 DFA M')
print('M1=(',set(K),',',set(E), ',', 'f', ',',set(S), ',', set(Z), ')')
print('其中 f 为')
k = 0
for yy in f1:
    print('f(',yy[0],',',yy[1],')=',yy[2],end=' ')
    k = k+1
    if k == 4:
        print('\n')
        k = 0
2、运行后果截图

 

 

 

退出移动版