Schafsprache v2 + Hawaiianisch (buggy)
2010-06-04 20:18:56

strategy = "LIFO" # LIFO or FIFO
trace    = True   # True or False

# Schafsprache
trans1 = {0: {'b':[1]},
          1: {'a':[2]},
          2: {'a':[2, 3]},
          3: {'!':[4]},
          4: {}}
start1 = 0
final1 = [4]

# Hawaiianisch
trans2 = {0: {'h':[1], 'k':[1], 'l':[1], 'n':[1], '\'':[1], 'w':[1]},
          1: {'a':[2, 3], 'i':[3], 'o':[3], 'u':[3]},
          2: {'i':[3]},
          3: {'':[0]}}
start2 = 0
final2 = [3]

def nd_recognize(tape, machine):
   (trans, start, final) = machine
   agenda = [(start, 0)]
   visited = []
   (cur_search_state, agenda) = next(agenda)
   while True:
      if trace:
         print "nState: %s, Index: %s, Agenda: %s" % (cur_search_state[0], cur_search_state[1], agenda)
      if accept_state(cur_search_state, tape, machine):
         return "accept"
      else:
         (visited, agenda) = generate_new_states(cur_search_state, agenda, tape, machine, visited)
         if len(agenda) == 0:
            return "reject"
         else:
            (cur_search_state, agenda) = next(agenda)

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((cur_node, index), agenda, tape, (trans, start, final), visited):
   new_states = []
   if cur_node in trans:
      if tape[index] in trans[cur_node]:
         for i in trans[cur_node][tape[index]]:
            new_states.append((i, index+1))
   if '' in trans[cur_node]:
      for i in trans[cur_node]['']:
         if not (i, index) in visited:
            new_states.append((i, index))
            visited.append((i, index))
   if trace:
      print "New States: %s" % new_states
   return (visited, new_states + agenda)

def accept_state((cur_node, index), tape, (trans, start, final)):
   if len(tape) == index and cur_node in final:
      return True
   else:
      return False

print nd_recognize("waikikuko", (trans2, start2, final2))