Transduktor v2
2010-06-13 15:37:47

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

# Erweiterte baa!-Sprache
# baa! -> [abb?]
trans1 = {0: {('b', 'a'):[1]},
          1: {('a', 'b'):[2]},
          2: {('a', 'b'):[2, 3]},
          3: {('!', '?'):[4]},
          4: {}}
start1 = 0
final1 = [4]

# Morphem-Splitter 1
# hundehof -> [hund-e-hof]
# hofhund  -> [hof-hund]
trans2 = {0: {('h', 'h'):[1, 4]},
          1: {('o', 'o'):[2]},
          2: {('f', 'f'):[3]},
          3: {('',  '-'):[0]},
          4: {('u', 'u'):[5]},
          5: {('n', 'n'):[6]},
          6: {('d', 'd'):[7]},
          7: {('',  '-'):[8]},
          8: {('e', 'e'):[3]}}
start2 = 0
final2 = [3, 7]

# Morphem-Splitter 2
# abteilen -> [ab-teilen, abt-eilen]
# abtei    -> [abtei, abt-ei]
trans3 = { 0: {('a', 'a'):[1]},
           1: {('b', 'b'):[2]},
           2: {('', '-') :[3], ('t', 't'):[10]},
           3: {('t', 't'):[4]},
           4: {('e', 'e'):[5]},
           5: {('i', 'i'):[6]},
           6: {('l', 'l'):[7]},
           7: {('e', 'e'):[8]},
           8: {('n', 'n'):[9]},
           9: {(' ', ' ') :[0]},
          10: {('', '-') :[4, 11], ('e', 'e'):[12]},
          11: {('e', 'e'):[12]},
          12: {('i', 'i'):[9]}}
start3 = 0
final3 = [9]

def nd_recognize_cc(tape, machine):
   (trans, start, final) = machine
   agenda = [(start, 0, [], "")]  # Erweiterte Agenda
   output = []                    # Liste zum Speichern der akzeptierten Woerter
   run = True                     # Schleifenbedingung
   (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)
      # accepted enthaelt akzeptiertes Wort oder None
      accepted = accept_state_cc(cur_search_state, tape, machine)
      if not accepted == None:
         # accept an output anhaengen
         output.append(accepted)
         if trace:
            print "Accepted: \"%s\"" % accepted
      agenda = generate_new_states_cc(cur_search_state, agenda, tape, machine)
      if len(agenda) == 0:
         # Schleifenbedingung auf False setzen
         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, cur_str), agenda, tape, (trans, start, final)):
   new_states = []
   if cur_node in trans:
      for i in trans[cur_node]:
         if index < len(tape):
            for j in trans[cur_node][i]:
               if i[0] == tape[index]:
                  new_states += [(j, index+1, [], cur_str+i[1])]
         # Epsilon-Uebergaenge (in trans aber noch nicht in cyc_states?)
         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, cur_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, cur_str), tape, (trans, start, final)):
   # Gibt akzeptiertes Wort oder None zurueck
   if cur_node in final and index == len(tape):
      return cur_str
   else:
      return None

#print nd_recognize_cc("baaa!", (trans1, start1, final1))
print "hofhundehofhof -> %s" % nd_recognize_cc("hofhundehofhof", (trans2, start2, final2))
print "abteilen       -> %s" % nd_recognize_cc("abteilen", (trans3, start3, final3))
print "abtei          -> %s" % nd_recognize_cc("abtei", (trans3, start3, final3))