Transduktor v1
2010-06-12 14:05:45

strategy = "FIFO" # LIFO oder FIFO
trace = True


trans1 = {0: {('b', 'a'):[1]},
          1: {('a', 'b'):[2]},
          2: {('a', 'b'):[2, 3]},
          3: {('!', '?'):[4]},
          4: {}}
start1 = 0
final1 = [4]

trans2 = {0: {('x', 'a'):[0], ('', 'b'):[0], ('', 'c'):[0]}}
start2 = 0
final2 = [0]


def nd_recognize_cc(tape, machine):
   (trans, start, final) = machine
   agenda = [(start, 0, [], "")]
   output = []
   run = True
   (cur_search_state, agenda) = next(agenda)
   while run:
      if trace:
         print "State: %s, Index: %s, Agenda: %s" % (cur_search_state[0], cur_search_state[1], agenda)
      dummy = accept_state_cc(cur_search_state, tape, machine)
      if not dummy == None:
         output.append(dummy)
         if trace:
            print "Accepted: \"%s\"" % dummy
      agenda = generate_new_states_cc(cur_search_state, agenda, tape, machine)
      if len(agenda) == 0:
         run = False
      else:
         (cur_search_state, agenda) = next(agenda)
   return output

def next(agenda):
   if strategy == "LIFO":
      if len(agenda) > 1:
         return (agenda[0], agenda[1:])
      else:
         return (agenda[0], [])
   elif strategy == "FIFO":
      if len(agenda) > 1:
         return (agenda[-1], agenda[:-1])
      else:
         return (agenda[0], [])

def generate_new_states_cc((cur_node, index, cyc_states, str), agenda, tape, (trans, start, final)):
   new_states = []
   if cur_node in trans:
         if index < len(tape):
            for i in trans[cur_node]:
               if i[0] == tape[index]:
                  for j in trans[cur_node][i]:
                     new_states += [(j, index+1, [], str+i[1])]
         for i in trans[cur_node]:
            if i[0] == '' and (cur_node, i[1]) not in cyc_states:
               for j in trans[cur_node][i]:
                  new_states += [(j, index, [(cur_node, i[1])]+cyc_states, str+i[1])]
   if trace:
      print "New States: %s\n" % new_states
   return new_states + agenda

def accept_state_cc((cur_node, index, cyc_states, str), tape, (trans, start, final)):
   if cur_node in final:
      return str
   else:
      return None

#print nd_recognize_cc("baaa!", (trans1, start1, final1))
print nd_recognize_cc("x", (trans2, start2, final2))