package nfa




// A nondeterministic Finite Automaton (NFA) consists of states,
// symbols in an alphabet, and a transition function.

// A state in the NFA is represented as an unsigned integer.
type state uint

// An symbol in the NFA is a single rune, i.e. a character.
type symbol rune

// Given the current state and a symbol, the transition function
// of an NFA returns the set of next states the NFA can transition to
// on reading the given symbol.
// This set of next states could be empty.
type TransitionFunction func(st state, sym symbol) []state

// Reachable returns true if there exists a sequence of transitions
// from transitions such that if the NFA starts at the start state
// start it would reach the final state final after reading the
// entire sequence of symbols input; Reachable returns false otherwise.
var transitionsLength = 0
var explored []bool

func Reachable(transitions TransitionFunction, start, final state, input []symbol) bool {
    nextState := transitions(start, 99)
    n := len(input)


    if n == 0 { //base case

        if start == final{
            return true
        } else{
            return false
        }
    }



    if n != 0{
        nextState = transitions(start, input[0]) //check len.  check if empty.
        transitionsLength = len(nextState)


    }


    if transitionsLength == 0{
        return false
    }
    if transitionsLength >=1{ //only explore the transitions if they can be explored.

        if n != 0{
            deleteThisIndex := 0
            new_input := append(input[:deleteThisIndex], input[deleteThisIndex+1:]...) //update symbols
            for i := 0; i < len(nextState); i++{
                //update explored
                explored = append(explored, Reachable(transitions, nextState[i], final, new_input))

            }



        }

    }


    for i := 0; i < len(explored); i++{
        if explored[i]{
            explored = explored[:0]
            return true
        }
    }

    return false
}