想调用下面那个SFA_Ops类里的intersect方法去实现ex_1_4a,但是直接写intersect方法没反应,怎么调用啊?
at_least_three_a = {
'states':{'q1','q2','q3','q4','q5'},
'alphabet':{'a','b'},
'transitions':{
('q1','a'):'q2', ('q1','b'):'q3',
('q2','a'):'q4', ('q2','b'):'q2',
('q3','a'):'q2', ('q3','b'):'q3',
('q4','a'):'q5', ('q4','b'):'q4',
('q5','a'):'q5', ('q5','b'):'q5',
},
'start':'q1',
'accept': {'q5'}
# write code here
}
at_least_two_b = {
'states':{'q1','q2','q3','q4'},
'alphabet':{'a','b'},
'transitions':{
('q1','a'):'q2', ('q1','b'):'q3',
('q2','a'):'q4', ('q2','b'):'q2',
('q3','a'):'q2', ('q3','b'):'q3',
('q4','a'):'q4', ('q4','b'):'q4',
},
'start':'q1',
'accept': {'q4'}
# write code here
}
ex_1_4a = intersect(at_least_three_a,at_least_two_b)
ex_1_4a_test = (['aaabb','ababa'],['','aaa','bb','aabb','aaab'])
import itertools
class SFA_Ops:
@staticmethod
def cross_states(set1, set2):
cp = set()
# code to make the cartesian product of set1 by set2
for i in itertools.product(set1, set2):
cp.add(i)
return cp
@staticmethod
def cross_deltas(state, alphabet, d1, d2):
d = {} # an empty dictionary
# code to make the cartesian product transition function from
# the transition functions d1 and d2
for i in alphabet:
for j in state:
d[(j,i)] = (d1[(j[0],i)],d2[(j[1],i)])
return d
@staticmethod
def cross_machine(fa1, fa2):
assert fa1['alphabet'] == fa2['alphabet']
"""
returns a new dictionary; however the elements are not copied
"""
states = SFA_Ops.cross_states(
fa1['states'],
fa2['states'])
d = SFA_Ops.cross_deltas(states,
fa1['alphabet'],
fa1['transitions'],
fa2['transitions'])
fa = {
'states': states,
'alphabet': fa1['alphabet'],
'transitions':d,
'start': (fa1['start'],fa2['start']),
'accept':set()
}
return fa
@staticmethod
def intersect(fa_o,fa_i):
desc = SFA_Ops.cross_machine(fa_o,fa_i)
accept = set()
# create the set of accept states for the intersection of
for i in fa_o['accept']:
for j in fa_u['accept']:
accept.add(i,j)
# languages accepted by fa_o and fa_i
desc['accept'] = accept
return desc
@staticmethod
def union(fa_o,fa_u):
desc = SFA_Ops.cross_machine(fa_o,fa_u)
accept = set()
# create the set of accept states for the union of
# languages accepted by fa_o and fa_i
for i in fa_o['accept']:
for j in fa_u['states']:
accept.add((i,j))
for i in fa_u['accept']:
for j in fa_o['states']:
accept.add((j,i))
desc['accept'] = accept
return desc
@staticmethod
def complement(fa_c):
desc = fa_c.copy() # a shallow copy, to avoid aliasing two machines
accept = set()
# create the set of accept states for the complement of
# language accepted by fa_c
for i in fa_c['states']:
if not (i in fa_c['accept']):
accept.add(i)
desc['accept'] = accept
return desc