1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

# fa_class.py: simulating DFAs and NFAs
import sys
import re

class FA:  # Finite Automaton
    def __init__(self, f):
        self.filename = f
        # extra variables
        self.stn = 0
        self.symbs = None
        self.eps = False
        self.dfa = True
        # call functions
        self.read_fa(self.filename)
        self.print_fa()
        ### end of: __init__
    
    def read_fa(self, filename):
        self.fa = [] # the actual finite automata
        self.ss = 0 # start state
        self.terms = [] # list of terminal states
        f = open(filename,'r')
        self.line = f.readline()
        r1 = re.compile(R"\s*(\d+).*")
        m1 = r1.search(self.line)
        self.stn = int(m1.group(1))
        
        self.symbs = f.readline()
        self.stp = f.readline() # each state status
        self.ssn = 0  # num of start sts (must be 1)
        self.tn  = 0  # num of term sts (at least 1)
        for i in range(0,self.stn):
            self.fa.append((int(self.stp[i]), []))
            if self.stp[i] == '1' or \
              self.stp[i] == '3':
                self.ss = i
                self.ssn = self.ssn + 1
            if self.stp[i] == '2' or \
              self.stp[i] == '3':
                self.terms.append(i)
                self.tn = self.tn + 1
        if self.ssn != 1:
            sys.stdout.write("ERR, != 1 start st")
        if self.tn < 1:
            sys.stdout.write("ERR, 0 term states")

        # now work on transition data
        r2 = re.compile(R"\s*(\d+)\s+(\S)\s+(\d+)")
        for line in f:
            # read tail_state symb head_state
            m2 = r2.search(line)
            st1 = int(m2.group(1))
            st2 = int(m2.group(3))
            sym = m2.group(2)
            if sym == '@': # check for eps
                self.eps = True
            #  append onto the adjacency list
            self.fa[st1][1].append( (sym, st2) )
        self.dfa = self.check_dfa()
        ### end of: read_fa
        
    def check_dfa(self):
        for i in range(0,self.stn):
            for ch in self.symbs: # all symbs
                t = self.lookup(i, ch)
                if t != None and len(t) >= 2:
                    return False
        return True
        ### end of: check_dfa

    def lookup(self, state, symb):
        ret = []
        if state < 0 or state >= len(self.fa):
            return None
        elif len(self.fa[state][1]) == 0:
            return None
        else:
            t = len(self.fa[state][1])
            for i in range(0,t):
                if self.fa[state][1][i][0] == symb:
                  ret.append(self.fa[state][1][i][1])
            return ret
        ### end of: lookup

    def get_start_state(self):
        return self.ss
        ### end of: get_start_state

    def terminals(self):
        return self.terms
        ### end of: terminals

    def is_terminal(self, state):
        if self.fa[state][0] == 2 or \
          self.fa[state][0] == 3:
            return True
        return False
        ### end of: is_terminal

    def is_dfa():
        return self.dfa
        ### end of: is_dfa

    def print_fa(self):
        if self.eps:
            sys.stdout.write("NFA with epsilon: ")
        elif self.dfa:
            sys.stdout.write("DFA: ")
        else:
            sys.stdout.write("NFA: ")
        sys.stdout.write("States " +str(self.stn)+
          ", Symbols: " + self.symbs + "\n")
        for i in range(0,self.stn):
            if i < 10:
                sys.stdout.write(" " + str(i))
            else:
                sys.stdout.write(str(i))
            if i == self.ss:
                sys.stdout.write("s")
            else:
                sys.stdout.write(" ")
            if self.is_terminal(i):
                sys.stdout.write("t:")
            else:
                sys.stdout.write(" :")
            sys.stdout.write(str(self.fa[i])+"\n")
        sys.stdout.write("\n")
        ### end of: print_fa

    def dfa_sim(self, dat):
        self.dat = dat
        sys.stdout.write("Input: " +self.dat+"\n")
        if not self.dfa:
            sys.stdout.write("Not DFA!\n\n")
            return
        sys.stdout.write("Simulate DFA\n")
        s1 = self.get_start_state()
        sys.stdout.write(str(s1) + "\n")
        for ch in self.dat:
            if ch != '$':
                s2 = self.lookup(s1, ch)[0]
                sys.stdout.write(str(s1) + " " + 
                  ch + " " + str(s2))
                if self.is_terminal(s2):
                    sys.stdout.write(" term")
                sys.stdout.write("\n")
                s1 = s2
            else:
                break
        sys.stdout.write("\n")
        ### end of: dfa_sim

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

    def eps_cl(self, s): # s a set, epsilon cl
        # 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 = self.lookup(u,'@')
            if r != None:
                for v in r:
                    if not (v in  b):
                        b.add(v) # add
                        t.append(v) # push
        return b
        ### end of: eps_cl

    def nfa_sim(self, ndat):
        self.ndat = ndat
        sys.stdout.write("Input: "+self.ndat+"\n")
        sys.stdout.write("Simulate NFA\n")
        x = []
        x.append(self.get_start_state())
        s1 = set(x)
        s1 = self.eps_cl(s1) # start state
        sys.stdout.write("St:" +
          str(list(s1)) + "\n")
        i = 0
        while self.ndat[i] != '$':
            s2 = set()
            for y in s1:
                s = self.lookup(y, self.ndat[i])
                if not s:
                    s = set()
                else:
                    s = set(s)
                s2 = s2 | s  # as sets, union
            # now got set, need epsilon colsure
            s2 = self.eps_cl(s2)
            sys.stdout.write(self.ndat[i] + ": " +
              str(list(s2)))
            if self.is_term(s2):
                sys.stdout.write(" term ")
            sys.stdout.write("\n")
            s1 = s2
            i = i + 1 # next instr
        ### end of: nfa_sim

# fa_exec.py: use the class FA
import sys
import fa_class
fa = fa_class.FA("dfa1.auto")
input = "ababaabbabaaa$"
fa.dfa_sim(input)
fa.nfa_sim(input)
% python fa_exec.py
DFA: States 4, Symbols: ab

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

Input: ababaabbabaaa$
Simulate DFA:
0
0 a 1
1 b 2
2 a 1
1 b 2
2 a 1
1 a 3 term
3 b 3 term
3 b 3 term
3 a 3 term
3 b 3 term
3 a 3 term
3 a 3 term
3 a 3 term

Input: ababaabbabaaa$
Simulate as NFA:
Start:
   [0]
a: [1]
b: [2]
a: [1]
b: [2]
a: [1]
a: [3] term 
b: [3] term 
b: [3] term 
a: [3] term 
b: [3] term 
a: [3] term 
a: [3] term 
a: [3] term 

# fa_exec.py: use the class FA
import sys
import fa_class
fa = fa_class.FA("nfa1.auto")
input = "aacacbccbab$"
fa.dfa_sim(input)
fa.nfa_sim(input)
% python fa_exec.py
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$
Simulate DFA:
Not DFA!

Input: aacacbccbab$
Simulate as NFA:
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]

# fa_exec.py: use the class FA
import sys
import fa_class
fa = fa_class.FA("nfa3.auto")
input = "aaaabaababbabbbb$"
fa.dfa_sim(input)
fa.nfa_sim(input)
% python fa_exec.py
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$
Not DFA!

Input: aaaabaababbabbbb$
Simulate NFA
St:[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]