Advertisement
tzoonami

Untitled

Nov 22nd, 2013
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.00 KB | None | 0 0
  1. import sys
  2.  
  3. class DFA:
  4.   def __init__(self,states,sigma,table,start,final):
  5.     self.states = set(states)
  6.     self.start = start
  7.     self.final = set(final)
  8.     self.sigma = set(sigma)
  9.     self.table = table
  10.     self.translator = ['']*len(self.sigma)
  11.     i = 0
  12.     for symbol in sorted(self.sigma):
  13.       self.translator[i] = symbol
  14.       i += 1
  15.     self.current = start
  16.     self.delta = lambda state,symbol: self.table[symbol][state]
  17.  
  18.   def output(self):
  19.     print "Number of states:", len(self.states)
  20.     print "Accepting states:",
  21.     for state in sorted(self.final):
  22.       print state,
  23.     print
  24.     print "Alphabet:",
  25.     print "".join(self.translator)
  26.     for state in self.states:
  27.       for i in range(len(self.sigma)):
  28.         print self.delta(state,self.translator[i]),
  29.       print
  30.  
  31.   def advance(self, symbol):
  32.     self.current = self.delta(self.current,symbol)
  33.  
  34.   def advance_sequence(self, symbolseq):
  35.     for symbol in symbolseq:
  36.       self.advance(symbol)
  37.  
  38.   def reset(self):
  39.     self.current = self.start
  40.  
  41.   def recognizes(self, symbolseq):
  42.     cursave = self.current
  43.     self.reset()
  44.     self.advance_sequence(symbolseq)
  45.     rv = self.current in self.final
  46.     self.current = cursave
  47.     return rv
  48.  
  49. def complement(dfa):
  50.   new_final = []
  51.   for state in dfa.states:
  52.     if state not in dfa.final:
  53.       new_final.append(state)
  54.   return DFA(dfa.states,dfa.sigma,dfa.table,dfa.start,new_final)
  55.  
  56. def intersect(dfa1,dfa2):
  57.   states = []
  58.   for s1 in dfa1.states:
  59.     for s2 in dfa2.states:
  60.       states.append((s1,s2))
  61.   def lookup(pair,symbol):
  62.     delta1 = dfa1.delta(pair[0],symbol)
  63.     delta2 = dfa2.delta(pair[1],symbol)
  64.     return states.index((delta1,delta2))
  65.   sigma = dfa1.sigma
  66.   table = {}
  67.   for symbol in sigma:
  68.     for pair in states:
  69.       if not table.has_key(symbol):
  70.         table[symbol] = [lookup(pair,symbol)]
  71.       else:
  72.         table[symbol].append(lookup(pair,symbol))
  73.   start = 0
  74.   final = []
  75.   for pair in states:
  76.     if (pair[0] in dfa1.final) and (pair[1] in dfa2.final):
  77.       final.append(states.index(pair))
  78.   return DFA(range(len(states)),sigma,table,start,final)
  79.  
  80. def DFA_from_input(in_file):
  81.   f = open(in_file)
  82.   s = f.read()
  83.   s = s.split('\n')
  84.   states = range(int(s[0].split("Number of states: ")[1]))
  85.   sfinal =  s[1].split("Accepting states: ")[1].split(" ")
  86.   final = [int(state) for state in sfinal]
  87.   sigma = sorted(s[2].split("Alphabet: ")[1])
  88.   s = s[3:-1]
  89.   table = {}
  90.   for line in s:
  91.     row = line.split(' ')
  92.    
  93.     for i in range(len(sigma)):
  94.       if not table.has_key(sigma[i]):
  95.         table[sigma[i]] = [int(row[i])]
  96.       else:
  97.         table[sigma[i]].append(int(row[i]))
  98.   return DFA(states,sigma,table,0,final)
  99.  
  100. def string_list_from_input(in_file):
  101.   return open(in_file).read().split('\n')[:-1]
  102.  
  103. if __name__ == "__main__":
  104.   myDFA = DFA_from_input(sys.argv[1])
  105.   for s in string_list_from_input(sys.argv[2]):
  106.     if myDFA.recognizes(s):
  107.       print "accept"
  108.     else:
  109.       print "reject"
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement