实现NFA算法（基于Python）
参考：
求解问题的思路
数据结构的设计
参考了NFA的定义，NFA是⼀个5-元组：M = (Q, ∑, Δ, s, F)
其中：Q是状态的有限集
∑是有穷字母表
s是开始状态
F含于Q，结束状态集
胸口长痣
Δ状态转移函数的集合
求解算法：
NFA识别字符串：某个字符串经过NFA，有多种可能路径，只要存在⼀种可以最终到达结束状态，则这个NFA就可以识别这个字符串。因此，只要得到这个字符串经过NFA最终到达的状态的集合，查看其中是否存在结束状态。若存在，则NFA可以识别这个字符串，否则不可以。
还要考虑空字符e的问题，某⼀状态经过空字符e可以到达的状态集合，即需要考虑某个状态的空闭包的问题。若 I 是⼀个状态集合的⼦集，那么 I 会有⼀个空闭包集合，记作 ε-closure(I)。这个空闭包集合同样是⼀个状态集合，它的元素符合以下⼏点：I 的所有元素都是空闭包集合的元素；对于 I 中的每⼀个元素，从该元素出发经过任意条 ε 弧能够到达的状态，都是空闭包集合的元素。
在类NFA中，设计了四个函数，分别是read_string()，e_closure()，next_state()，match_final_state()。
函数read_string(input_str)：读取输⼊的字符串，判断是否能够被NFA接受
函数e_closure(state)：求取某个状态的空闭包（BFS的思想）
函数next_state(current_states, c)：当前状态集经字符c到达的下⼀状态集
函数match_final_state(final_current_states)：最终状态与接受状态匹配
"""设计识别字符串的NFA"""
import string
from collections import deque
class NFA:
def __init__(lf, states, symbols, t_state, start_state, final_state): # 初始化
拌洋葱lf.states = states # 状态集
lf.symbols = symbols # 输⼊的符号集/字母表
lf.t_state = t_state # 状态转移函数
lf.start_state = start_state # 开始状态
lf.final_state = final_state # 结束状态
def read_string(lf, input_str): # 读取字符串进⼊NFA鉴定
for c in input_str: # 判断字符串满⾜字母表
if c not in lf.symbols:
print('字符串中的字符不合法')
return
next_states = [lf.start_state]
for i in str:
next_states = lf.next_state(next_states, i)
result = lf.match_final_state(next_states)
if result == True:
print('NFA可接受该字符串')
print('NFA可接受该字符串')
el:
print('NFA不能接收该字符串')
def e_closure(lf, state): # 求取某个状态的空闭包
d_state = deque() # 双端队列，存储中间状态
empty_bag = [] # 某个状态的空闭包
d_state.append(state)
empty_bag.append(state)
while (len(d_state)):
current_state = d_state[0]
if current_state in lf.t_state.keys(): # 如果当前状态存在
if 'e' in lf.t_state[current_state].keys(): # 若存在空字符转移
for s in lf.t_state[current_state]['e']:
if s not in empty_bag: # 如果状态不在空闭包内
d_state.append(s) # 将经e到达的状态⼊队和加⼊空闭包
empty_bag.append(s)
d_state.popleft() # 抛出当前状态
return empty_bag
def next_state(lf, current_states, c): # 当前状态经过某字符能够到达的下⼀状态的集合，包括空闭包 next_states = [] # 下⼀个状态集，包括下⼀个状态集的空闭包的集合
for state in current_states:
if state in lf.t_state.keys():
if c in lf.t_state[state].keys():
n_states = lf.t_state[state][c]
for s in n_states: # 获取下⼀个状态集的空闭包
s_closure = lf.e_closure(s)
for s_c in s_closure: # 将空闭包的集合加⼊下⼀状态集合
if s_c not in next_states:
next_states.append(s_c)
print('状态转移：')
print(current_states, end=' ')
print('-' + c + '->', end=' ')
print(next_states)
return next_states # 返回获取的下⼀状态的集合/通过字符c的状态集
def match_final_state(lf, final_current_states: list) ->bool : # 最终状态匹配结束状态
令我难忘的一件事作文for state in final_current_states:
if state in lf.final_state:
return True
return Fal
if __name__ == '__main__':
states = ['q1', 'q2', 'q3', 'q4'] # NFA状态集
彩虹桥symbols = ['0', '1'] # NFA字母表
t_state = {
'q1': {
'0': ['q1'],
'1': ['q1', 'q2']
},
'q2': {
'e': ['q3'],翡翠大观
'0': ['q3']
},
'q3': {
'1': ['q4']
},
'q4': {
'0': ['q4'],
'1': ['q4']
}
} # 状态转移函数
start_state = 'q1' # 开始状态
final_state = ['q4'] # 结束状态集
幼儿园老师寄语while True:
str = input("请输⼊测试的字符串：")
if str == 'exit':
夏天像个
break
nfa = NFA(states, symbols, t_state, start_state, final_state) ad_string(str)
月子早餐吃什么好
