Gun's Blog

NFA确定化

Word count: 1.5kReading time: 6 min
2019/10/30 Share

一.实验目的

  • (1) 加深对NFA确定化算法的熟悉程度
  • (2) 进一步理解高级语言在计算机中的执行过程, 加深对编译原理中重点算法和编译技术的理解, 提高自己的编程能力, 掌握将NFA转换为与之等价的DFA的算法。

二.实验内容

通过设计编写和调试将不确定的有穷自动机转换为与之等价的确定的有穷自动机的程序,掌握转换过程中的相关概念和方法。

  • input NFA
  • output 与之等价的DFA

三.实验原理

算法描述:

  • (1) 若pNFA的初态,则DFA的初态为$A=\epsilon-closure({p})$;
  • (2) 对NFA中的每一个箭弧标记m,计算$\epsilon-closure(f(q,m))$,其中q是已经生成了的DFA状态。即遍历字母表的每个字符作为输入,例如字母表${a,b}$,则$B=\epsilon-closure(f(A,a))$,$C=\epsilon-closure(f(A,b))$. 若B,C不是空集, $D=\epsilon-closure(f(B,a))$,$E=\epsilon-closure(f(B,b))$重复这一个过程. 直到不在出现新的状态集合.
  • (3) 重新命名DFA中的状态,并修改其他项.
  • (4) DFA M的初态为原NFA M'初始状态的子集,终态为原终止状态的子集.

四.实现方法

  • 构造NFA的输入格式:

    主要是NFA M的状态转移函数的输入:

    $f=[{‘e’:[1,7]},{‘e’:[2,4]},{‘a’:[3]},{‘e’:[6]},{‘b’:[5]},{‘e’:[6]},{‘e’:[7,1]},{‘a’:[8]},{‘b’:[9]},{‘b’:[10]},{}]$
    上述输入的转移函数的含义: 以lpython中的list的索引映射到NFA M的j节点,每个列表项对应的是状态转移函数的关系. 例如,上述状态转移函数 f 中python列表第一项的索引为0,字典 的值为${‘e’:[1:7]}$表示的是:0节点识别e后转移到1号和7号节点.最后
    NFA M确定化后得到的状态转换函数也将以上述形式输出.

  • python具体实现方法

    首先构造一个NFA的类,其成员有状态集S,初态S0,终态Z,还有两个函数成员.

    e_closure(self,I):此方法实现求$\epsilon-closure(I)$,
    transfer(self,I,way):此方法实现I里的每一个元素识别一个符号到达的状态集,是求$Ia$的一个步骤.如图所示:
    NFA CLASS
    接下来相应的实现一个DFA的类,将上面的NFA传入成员中作相应的处理. 求$Ia$.
    最后,使用python的第三方库prettytable将结果在表格中显示出来. 源代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    #!/usr/bin/python3
    #_*_coding:utf-8_*_

    from prettytable import PrettyTable #表格的第三方库
    class NFA:
    def __init__(self,S,S0,Z,f):
    self.S=S #状态集
    self.S0=S0 #初态
    self.Z=Z #终态
    self.f=f #转换规则,f为List嵌套dict

    def e_closure(self,I): #求解e闭包
    e_closure=list()
    Stack=list()

    for i in I:
    Stack.append(i) #"栈结构"
    e_closure.append(i) #第一步,如果i属于I,则i属于e_closure

    while Stack: #第二步,按照给定的转换规则识别n步e,将新元素加入到e_closure中
    i = Stack.pop()
    if 'e' in f[i]: #以e代表伊普西隆
    closure=self.f[i]['e'] #closure=[2,4]->[5]
    for new_ele in closure:
    if new_ele not in e_closure: #去重
    Stack.append(new_ele)
    e_closure.append(new_ele)
    return e_closure #列表

    def transfer(self,I,way): #求解I识别不同的路径后到达的状态,way代表字符
    closure=list()
    for i in I:
    if way in f[i]:
    s=self.f[i][way]
    for ele in s:
    if ele not in closure:
    closure.append(ele)
    return closure #列表

    class DFA:
    def __init__(self,N):
    self.S=[]
    self.S.append(set(N.e_closure([0])))
    #状态集,list嵌套list
    self.f=list() #转换规则
    self.S0=list()
    self.Z=list()

    index=0
    stack=[N.e_closure([0])]
    ways=[] #路径,可以代表一个字符
    extra_ways=list()
    table=['state'] #状态表的第一列

    for i in N.f:
    for j in list(i):
    if list(i)!=[] and j!='e':
    extra_ways.append(j) #ways=['a','b','c'.....]表示路经
    for letter in extra_ways: #列表元素去重
    if letter not in ways:
    ways.append(letter)
    table.append(letter)

    state_table=PrettyTable(table) #设计DFA状态转换表
    state_table.align["state"]="1" #与第一列对齐
    state_table.padding_width=2 #宽度

    row=[] #状态表的每一行
    state=[]
    while stack:
    I=stack.pop()
    row.append(set(I)) #转换为set
    state.append(set(I))

    #print("I:{}".format(I))
    for way in ways:
    extra_state=N.e_closure(N.transfer(I,way))
    #print("extra_state:{}".format(extra_state))
    #print("S:{}".format(self.S))
    if set(extra_state) not in self.S:
    stack.append(extra_state)
    self.S.append(set(extra_state))
    if self.f==[]:
    self.f.append({'{}'.format(way):extra_state})
    else:
    self.f[index].update({'{}'.format(way):extra_state})
    row.append(set(extra_state))
    state_table.add_row(row)
    self.f.append({})
    index = index+1
    row=[]
    self.f.pop()
    #print("s:{}".format(state))
    for m in state: #包含NFA原始(终止)状态的状态子集为DFA的初态(终态)
    if N.S0 in m:
    self.S0.append(state.index(m))
    if N.Z in m:
    self.Z.append(state.index(m))
    print(state_table)

    if __name__=='__main__':
    #print("输入状态集S(格式为列表):")
    #S=eval(input())
    print("输入初态S0:")
    S0=int(input())
    print("输入终态:")
    Z=int(input())
    S=[0,1,2,3,4,5,6,7,8,9,10]
    #f=[{'e':[1]},{'a':[1],'b':[1],'e':[2]},{'a':[5],'b':[6]},{'e':[4]},{'a':[4],'b':[4],'e':[7]},{'a':[3]},{'b':[3]},{}]
    f=[{'e':[1,7]},{'e':[2,4]},{'a':[3]},{'e':[6]},{'b':[5]},{'e':[6]},{'e':[7,1]},{'a':[8]},{'b':[9]},{'b':[10]},{}]
    #f=[{'e':[3],'a':[1,2]},{'a':[1],'b':[3]},{'c':[2,3]},{}]
    N=NFA(S,S0,Z,f)
    print("数据收集完毕")
    D=DFA(N)
    print(D.f)
    print("DFA的初态为:{}".format(D.S0))
    print("DFA的终态为:{}".format(D.Z))

五. 结果验证

  • 将教材上的图2-9按照相应的格式输入,运行结果如图所示:
    result
  • 有多个字符的情况,并且求闭包时会出现空集:
    result2
  • 一般情况:
    result3

实验总结

python的数据类型很灵活,特别在处理一些数据结构方面的实际问题时,表现的更为突出,相比于其他语言,如c++,可以节省很多的代码量.通过此次动手实践,加深了对NFA确定化算法的熟悉程度.

CATALOG
  1. 1. 一.实验目的
  2. 2. 二.实验内容
  3. 3. 三.实验原理
  4. 4. 四.实现方法
  5. 5. 五. 结果验证
  6. 6. 实验总结