# nfa.py: simulate an nfa
import auto
import sys

def is_term(s):  # s set, contains term?
    if not s:
        return False
    else:
        for x in s:
            if auto.is_terminal(x):
                return True
        return False

def eps_cl(s): # s a set, epsilon closure
    # could use s for b, save one list
    t = list(s) # list t is stack or queue
    b = set(t)  # set of "black" states
    while len(t) != 0:
        u = t.pop() # remove end elt
        # use @ for epsilon
        r = auto.lookup(u,auto.eps_symb)
        if r != None:
            for v in r:
                if not (v in  b):
                    b.add(v) # add
                    t.append(v) # push
    return b
    
auto.read_fa("dfa1.auto")
auto.printfa()
sys.stdout.write("\n")

# OK, let's simulate this sucker
f = open("dfa1.input",'r')
instr = f.readline()
ss = auto.get_start_state()
x = []
x.append(auto.get_start_state())
s1 = set(x)
s1 = eps_cl(s1) # start state
sys.stdout.write("Start:\n   " +
       str(list(s1)) + "\n")
i = 0
while instr[i] != '$':
    s2 = set()
    for y in s1:
        s = auto.lookup(y, instr[i])
        if not s:
            s = set()
        else:
            s = set(s)
        s2 = s2 | s  # as sets, union
    # now got set, need epsilon colsure
    s2 = eps_cl(s2)
    sys.stdout.write(instr[i] + ": " +
          str(list(s2)))
    if is_term(s2):
        sys.stdout.write(" term ")
    sys.stdout.write("\n")
    s1 = s2
    i = i + 1 # next instr

NFA: States 4, Symbols: abc

0s :(1, [('a', 0), ('b', 0), ('c', 0), ('a', 1), ('b', 2)])
1  :(0, [('c', 2), ('a', 3)])
2  :(0, [('c', 1), ('b', 3)])
3 t:(2, [])

Input: aacacbccbab$

Start: [0]
a: [0, 1]
a: [0, 1, 3] term 
c: [0, 2]
a: [0, 1]
c: [0, 2]
b: [0, 2, 3] term 
c: [0, 1]
c: [0, 2]
b: [0, 2, 3] term 
a: [0, 1]
b: [0, 2]

NFA: States 5, Symbols: abc

0s :(1, [('a', 0), ('b', 0), ('c', 0), ('a', 3), ('b', 1)])
1  :(0, [('b', 2)])
2 t:(2, [('a', 2), ('b', 2), ('c', 4)])
3  :(0, [('a', 4)])
4 t:(2, [('a', 4), ('b', 4)])

Input: ababababbacaa$

Start: [0]
a: [0, 3]
b: [0, 1]
a: [0, 3]
b: [0, 1]
a: [0, 3]
b: [0, 1]
a: [0, 3]
b: [0, 1]
b: [0, 1, 2] term 
a: [0, 2, 3] term 
c: [0, 4] term 
a: [0, 3, 4] term 
a: [0, 3, 4] term 

NFA: States 5, Symbols: ab

0s :(1, [('a', 0), ('a', 1), ('b', 0)])
1  :(0, [('a', 2), ('b', 2)])
2  :(0, [('a', 3), ('b', 3)])
3  :(0, [('a', 4), ('b', 4)])
4 t:(2, [])

Input: aaaabaababbabbbb$

Start: [0]
a: [0, 1]
a: [0, 1, 2]
a: [0, 1, 2, 3]
a: [0, 1, 2, 3, 4] term 
b: [0, 2, 3, 4] term 
a: [0, 1, 3, 4] term 
a: [0, 1, 2, 4] term 
b: [0, 2, 3]
a: [0, 1, 3, 4] term 
b: [0, 2, 4] term 
b: [0, 3]
a: [0, 1, 4] term 
b: [0, 2]
b: [0, 3]
b: [0, 4] term 
b: [0]

DFA: States 16, Symbols: abc

0  :(0, [('a', 1), ('b', 1), ('c', 1)])
1  :(0, [('@', 3), ('@', 0)])
2s :(1, [('@', 0), ('@', 3)])
3  :(0, [('@', 14)])
4  :(0, [('a', 5)])
5  :(0, [('@', 6)])
6  :(0, [('b', 7)])
7  :(0, [('@', 15)])
8  :(0, [('a', 9)])
9  :(0, [('@', 10)])
10  :(0, [('a', 11)])
11  :(0, [('@', 12)])
12  :(0, [('c', 13)])
13  :(0, [('@', 15)])
14  :(0, [('@', 4), ('@', 8)])
15 t:(2, [])

Input: cabcaaacabac$

Start: [0, 2, 3, 4, 8, 14]
c: [0, 1, 3, 4, 8, 14]
a: [0, 1, 3, 4, 5, 6, 8, 9, 10, 14]
b: [0, 1, 3, 4, 7, 8, 14, 15] term 
c: [0, 1, 3, 4, 8, 14]
a: [0, 1, 3, 4, 5, 6, 8, 9, 10, 14]
a: [0, 1, 3, 4, 5, 6, 8, 9, 10, 11, 12, 14]
a: [0, 1, 3, 4, 5, 6, 8, 9, 10, 11, 12, 14]
c: [0, 1, 3, 4, 8, 13, 14, 15] term 
a: [0, 1, 3, 4, 5, 6, 8, 9, 10, 14]
b: [0, 1, 3, 4, 7, 8, 14, 15] term 
a: [0, 1, 3, 4, 5, 6, 8, 9, 10, 14]
c: [0, 1, 3, 4, 8, 14]