########## Data structure for representing a DFA ##########

# As an example DFA, we use the DFA on page 25 on Fabrizio's slides,
# with a loop-edge added on state c.

# The states of the DFA will be contained in a list. Their names (a,
# b, c,...) are really indices into this list. Each state is itself a
# list of its edges (out-arrows), and each edge is a two-tuple
# containing a char and a state.

# Create a list to contain the states:
states = [None,None,None,None,None] 

# The states (as indices in the above list):
a = 0
b = 1
c = 2
d = 3
e = 4

# Now create each state in the list:
states[a] = [("H",b)]
states[b] = [("e",c),("i",e)]
states[c] = [("y",d),("e",c)]
states[d] = []
states[e] = []

# The rest of the DFA specification
startstate = a
acceptstates = [c,d,e]

########## Algorithm to test acceptance of a string ##########

## Find the index of the edge (in an edge list) that contains the
## given char. If none exists, return the index -1.
def findEdgeIndex(char,edgeList):
    returnIndex = -1
    currentIndex = 0
    for edge in edgeList:
        if char == edge[0]:
            returnIndex = currentIndex
        currentIndex = currentIndex + 1
    return returnIndex
        
## Check if a string is accepted.
def acceptString(s):
    currentState = startstate
    nextStringIndex = 0
    # While there is more string left AND there is an edge of the
    # current state that has the next char on it, advance the position
    # in DFA (the current state) and the position in the string (the
    # index of the next char to be considered):
    while nextStringIndex < len(s) and findEdgeIndex(s[nextStringIndex],states[currentState]) >= 0:
        char = s[nextStringIndex]
        edgeList = states[currentState]
        edgeIndex = findEdgeIndex(char,edgeList)
        edge = edgeList[edgeIndex]
        currentState = edge[1] # update currentstate to the new state
        nextStringIndex = nextStringIndex + 1 # advance in the string
    # When while loop stops, test if the situation corresponds to
    # acceptance :
    if nextStringIndex == len(s) and currentState in acceptstates:
        print("The string " + s + " is accepted.")
    else:
        print("The string " + s + " is not accepted.")