I also don't like that every state needs to take a NonTerminal parameter in its constructor indicating the NonTerminal it's a part of. Why not make State and its subclasses inner classes of NonTerminal. Then you would say something like:

    NonTerminal nt = new NonTerminal("Foo");
    nt.new NonTerminalState("foo", nt, false);

You could even have a helper constructor that takes its predecessor, like so:

    public NonTerminalState(String stateName, NonTerminal nt, boolean isLookahead, NextableState previous) {
        this(stateName, nt, isLookahead);
        previous.next.add(this);
    }

It would make building grammar objects a lot cleaner and neater.