Regular Expressions

regex.py

class Vertex:
    def __init__(self, n):
        self.number = n
        self.edgeList = []
        self.isAcceptingState = None

    def setAcceptingState(self):
        self.isAcceptingState = True

    def addEdge(self,e):
        self.edgeList.append(e)

    def followEdge(self,c):
        for i in self.edgeList:
            if i.character == c:
                return i.destination
        return None

class Edge:
    def __init__(self, c, dest):
        self.destination = dest
        self.character = c


class DFA:
    def __init__(self,s):
        self.start = s

    def match(self,s):
        self.characters = list(s)
        self.current = self.start

        print("trying to match "+s+": ")

        for i in self.characters:
            if self.current == None:
                print("no match")
                return
            print(self.current.number ," ")
            self.current = self.current.followEdge(i)

        if self.current == None:
            print("no match")
            return

        print(self.current.number);
        if self.current.isAcceptingState:
            print("match")
        else:
            print("no match")
        return



v1 = Vertex(1)
v2 = Vertex(2)
v3 = Vertex(3)
v4 = Vertex(4)
v5 = Vertex(5)
v6 = Vertex(6)
v4.setAcceptingState()
v6.setAcceptingState()

v1.addEdge(Edge("a",v2))
v1.addEdge(Edge("b",v1))
v2.addEdge(Edge("b",v3))
v2.addEdge(Edge("a",v5))
v3.addEdge(Edge("c",v4))
v5.addEdge(Edge("b",v6))
v6.addEdge(Edge("c",v6))
v4.addEdge(Edge("d",v1))

stateMachine = DFA(v1)
stateMachine.match("abc")
stateMachine.match("bbabc")
stateMachine.match("baab")
stateMachine.match("baabcc")
stateMachine.match("abcdbbbabc")
stateMachine.match("abcd")
stateMachine.match("e")