A parenthesis counter that's limited to, say, 1024 bits for its count, is still a finite state machine and can be implemented in those 1024 bits (plus a few extras for book keeping, I guess).

You don't need to have every state in an FSM be explicitly constructed up-front.

The pdf you mention is great, btw.