Following all paths in an NFA to see if some word is accepted.

NondeterministicDirectedGraph.java

//GLOBALS
ArrayList<String> alphabet;       //all the characters for this a language
ArrayList<Vertex> graph;          //set of all vertices containing edge relationships and cost requirments for traversal
private final String START = "S"; //file format quantifier for a START (initial) vertex
private final String END   = "F";   //file format quantifier for a END (termination) vertex



//business method - decides whether a given word can reach a TERMINAL state in a TM (graph).
public boolean CheckWordAgainstGraph(String word)
{
        boolean valid = false;  //result of if this word is accepted by this graph
        int initStateIndex = 0; //init state is always state 0 by construction
        

        //array of each state we are currently at. 
        //Starts at initial state but can take multiple paths depending on non-deterministic graph
        ArrayList<Integer> stateIndexes = new ArrayList<Integer>();
        stateIndexes.add(initStateIndex); //init state


        //keep track of new possible paths we could take if there are multiple edges with the same cost
        ArrayList<Integer> newPathStates = new ArrayList<Integer>();
        
        
        //keep track of indices for paths we are following that have crashed so we can clean them up after 1 full move through each path
        ArrayList<Integer> crashedPathIndexes = new ArrayList<Integer>();

        
        ArrayList<Edge> currentUseableVertexEdges = null; //container for all edges available to take for a given cost at a given vertex.
        String currentWordLetter; //container for each letter we attempt to parse in a word
        int currentPathState;     //convenient code readability holder for the current state of a path
        int nextState;            //convenient code readability holder for the next state we reach based on edge we traverse


        //traverse the whole word and then check the final state for TERMINAL state
        for (int wordIndex = 0; wordIndex < word.length(); wordIndex++) 
        {
                currentWordLetter = Character.toString(word.charAt(wordIndex));

                
                //account for each possible path we can take through our graph. 
                //Multiple paths could be generated from two edges from a vertex having the same cost.
                for (int pathIndex = 0; pathIndex < stateIndexes.size(); pathIndex++) 
                {
                        currentPathState = stateIndexes.get(pathIndex);
                        
                        
                        //collect all edges we could take at a vertex (state) with the cost we have (currentWordLetter)
                        currentUseableVertexEdges = this.graph.get(currentPathState).GetEdges(currentWordLetter);


                        //Go through all edge options that can be made by keeping track of new path's as needed.
                        if(currentUseableVertexEdges.size() > 0) 
                        {
                                for (int edgeIndex = 0; edgeIndex < currentUseableVertexEdges.size(); edgeIndex++) 
                                {
                                        nextState = Integer.parseInt(currentUseableVertexEdges.get(edgeIndex).GetDest());

                                        if(edgeIndex == 0) 
                                        {
                                                //Choose the first edge we already know about as being our first choice of edges to take
                                                stateIndexes.set(pathIndex, nextState);
                                        } else {
                                                //any remaining options for edges to take need to be new possible paths.
                                                //multiple paths can be taken because of a possible NFA graph, so we account for all possible edge choices.
                                                newPathStates.add(nextState); 
                                        }
                                }
                        }
                       else {
                                //no edge was available
                                crashedPathIndexes.add(pathIndex);
                        }
                }
                

                //remove paths that have reached a crash state -- must not have been the choice of edge to take at a previous vertex
                for (Integer crashedPathIndex : crashedPathIndexes) {
                        stateIndexes.remove((int)crashedPathIndex); //remove index of crashed path                                
                }
                crashedPathIndexes.clear();        
                
                
                //add any new edge choices as unique paths.
                //again, these stem from the potential NonDeterministic behavior at a vertex
                stateIndexes.addAll(newPathStates);
                newPathStates.clear();        
        }
       
        
        //After we have computed all possible path choices through a graph based on our word,
        //  then check the final state of all possible path choices. Only 1 of these possible paths
        //  that our word took needs to be a TERMINAL state.
        for (int pathIndex = 0; pathIndex < stateIndexes.size() && valid==false ; pathIndex++)
        {
                int currentState = stateIndexes.get(pathIndex); 

                if( this.graph.get(currentState).GetEndFlag() == true ) {
                        valid = true;
                }
        }

        return valid;
}