Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import sys
- class DFA:
- def __init__(self,states,sigma,table,start,final):
- self.states = set(states)
- self.start = start
- self.final = set(final)
- self.sigma = set(sigma)
- self.table = table
- self.translator = ['']*len(self.sigma)
- i = 0
- for symbol in sorted(self.sigma):
- self.translator[i] = symbol
- i += 1
- self.current = start
- self.delta = lambda state,symbol: self.table[symbol][state]
- def output(self):
- print "Number of states:", len(self.states)
- print "Accepting states:",
- for state in sorted(self.final):
- print state,
- print
- print "Alphabet:",
- print "".join(self.translator)
- for state in self.states:
- for i in range(len(self.sigma)):
- print self.delta(state,self.translator[i]),
- print
- def advance(self, symbol):
- self.current = self.delta(self.current,symbol)
- def advance_sequence(self, symbolseq):
- for symbol in symbolseq:
- self.advance(symbol)
- def reset(self):
- self.current = self.start
- def recognizes(self, symbolseq):
- cursave = self.current
- self.reset()
- self.advance_sequence(symbolseq)
- rv = self.current in self.final
- self.current = cursave
- return rv
- def complement(dfa):
- new_final = []
- for state in dfa.states:
- if state not in dfa.final:
- new_final.append(state)
- return DFA(dfa.states,dfa.sigma,dfa.table,dfa.start,new_final)
- def intersect(dfa1,dfa2):
- states = []
- for s1 in dfa1.states:
- for s2 in dfa2.states:
- states.append((s1,s2))
- def lookup(pair,symbol):
- delta1 = dfa1.delta(pair[0],symbol)
- delta2 = dfa2.delta(pair[1],symbol)
- return states.index((delta1,delta2))
- sigma = dfa1.sigma
- table = {}
- for symbol in sigma:
- for pair in states:
- if not table.has_key(symbol):
- table[symbol] = [lookup(pair,symbol)]
- else:
- table[symbol].append(lookup(pair,symbol))
- start = 0
- final = []
- for pair in states:
- if (pair[0] in dfa1.final) and (pair[1] in dfa2.final):
- final.append(states.index(pair))
- return DFA(range(len(states)),sigma,table,start,final)
- def DFA_from_input(in_file):
- f = open(in_file)
- s = f.read()
- s = s.split('\n')
- states = range(int(s[0].split("Number of states: ")[1]))
- sfinal = s[1].split("Accepting states: ")[1].split(" ")
- final = [int(state) for state in sfinal]
- sigma = sorted(s[2].split("Alphabet: ")[1])
- s = s[3:-1]
- table = {}
- for line in s:
- row = line.split(' ')
- for i in range(len(sigma)):
- if not table.has_key(sigma[i]):
- table[sigma[i]] = [int(row[i])]
- else:
- table[sigma[i]].append(int(row[i]))
- return DFA(states,sigma,table,0,final)
- def string_list_from_input(in_file):
- return open(in_file).read().split('\n')[:-1]
- if __name__ == "__main__":
- myDFA = DFA_from_input(sys.argv[1])
- for s in string_list_from_input(sys.argv[2]):
- if myDFA.recognizes(s):
- print "accept"
- else:
- print "reject"
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement