Schafsprache v1
2010-06-04 16:59:31

strategy = "LIFO"

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

start1 = 0
final1 = [4]

trace = True


def nd_recognize(tape, machine):
   (trans, start, final) = machine
   agenda = [(start, 0)]
   (cur_search_state, agenda) = next(agenda)
   while True:
      if accept_state(cur_search_state, tape, machine):
         return "accept"
      else:
         agenda = generate_new_states(cur_search_state, agenda, tape, machine)
         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)):
   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))
   return 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("baaaaaa!", (trans1, start1, final1))