NFA

import java.util.ArrayList;

/**
 * Created by Steven on 23/11/2014.
 */
public class NFA {
    private State currentState;

    public NFA(State... states) {
        this.currentState = states[0]; // Always put start state as first state.
    }

    public boolean recognises(String s) {
        return recognises(currentState, s, 0);
    }

    private boolean recognises(State state, String s, int offset) {
        if (offset >= s.length()) {
            return state.isFinalState();
        }
        ArrayList<State> nextStates = state.getTransitions(s.charAt(offset));
        for (State next : nextStates)
            if(recognises(next, s, offset+1))
                return true;

        return false;
    }

    public static void main(String[] args) {
        State startState = new State(false);
        State tState = new State(false);
        State uState = new State(false);
        State vState = new State(true);

        startState.addTransition('A', tState);
//        tState.addTransition('B', vState);
//        tState.addTransition('B', uState);
        tState.addTransition('A', vState);
        tState.addTransition('A', uState);
        tState.addTransition('A', uState);
        uState.addTransition('A', vState);
        vState.addTransition('A', startState);

        NFA nfa = new NFA(startState, tState, uState, vState);
        for(int i = 1; i < 1000; i++) {
            String repeated = new String(new char[i]).replace("\0", "A");
            System.out.println(repeated+":: "+ nfa.recognises(repeated));
        }
    }
}

import java.util.ArrayList;
import java.util.HashMap;

/**
 * Handles states.
 * Created by Steven on 23/11/2014.
 */
public class State {
    private HashMap<Character, ArrayList<State>> transitions;
    private boolean finalState;

    public State(boolean isFinal) {
        transitions = new HashMap<Character, ArrayList<State>>();
        this.finalState = isFinal;
    }
    public void addTransition(char c, State s) {
        ArrayList<State> states = transitions.get(c);
        if(states == null) {
            states = new ArrayList<State>();
        }
        states.add(s);
        transitions.put(c, states);
    }

    public ArrayList<State> getTransitions(char c) {
        if(isValidTransition(c)) {
            return transitions.get(c);
        }
        return new ArrayList<State>(); // return empty list so we can ignore null pointers.
    }

    private boolean isValidTransition(char c) {
        return transitions.get(c) != null;
    }

    public boolean isFinalState() {
        return finalState;
    }
}