Schafsprache v3 + Hawaiianisch und Testsprache
2010-06-06 23:27:53

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

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

# Schafsprache mit Epsilon Uebergang
trans2 = {0: {'b':[1]},
          1: {'a':[2]},
          2: {'a':[3]},
          3: {'!':[4],'':[2]},
          4: {}}
start2 = 0
final2 = [4]

# Hawaiianisch
trans3 = {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]}}
start3 = 0
final3 = [3]

# Testsprache
trans4 = {0: {'a':[1], '':[0]},
          1: {'':[1, 2]},
          2: {'a':[0],'':[0, 2]}}
start4 = 0
final4 = [0]

def nd_recognize(tape, machine):
   (trans, start, final) = machine
   agenda = [(start, 0)]
   # visited Liste um die bereits besuchten Zustaende
   # zu merken. Verhindert Endlosschleifen.
   visited = []
   (cur_search_state, agenda) = next(agenda)
   while True:
      if trace:
         print "State: %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 = []
   # Ist der akuelle Zustand in trans und ist das Band noch nicht zu Ende?
   if cur_node in trans and len(tape) > index:
      # Gibt es einen Uebergang zu einem Folgezustand mit dem
      # aktuellen Zeichen?
      if tape[index] in trans[cur_node]:
         for i in trans[cur_node][tape[index]]:
            new_states.append((i, index+1))
   # Epsilon-Uebergaenge:
   # - 1 Pruefen, ob vorhanden
   # - 2 Alle in new_states uebernehmen
   # - 3 Alle in visited uebernehmen
   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\n" % new_states
   return (visited, new_states + agenda)

def accept_state((cur_node, index), tape, (trans, start, final)):
   # Akzeptiert wenn der Zeiger am Ende
   # des Bands ist und der aktuelle Zustand
   # ein Endzustand ist.
   if len(tape) == index and cur_node in final:
      return True
   else:
      return False

print nd_recognize("baaa!", (trans1, start1, final1))
#print nd_recognize("baaa!", (trans2, start2, final2))
#print nd_recognize("waikiki", (trans3, start3, final3))
#print nd_recognize("hawai'i", (trans3, start3, final3))
#print nd_recognize("aaaa", (trans4, start4, final4))