In the first paragraph I mentioned that a specific, very simple FSM language is PSPACE, and in the second paragraph I was talking about terminating languages in

In the first paragraph I mentioned that a specific, very simple FSM language is PSPACE, and in the second paragraph I was talking about terminating languages in general, and didn't mention EXPTIME. For more elaborate terminating languages, the complexity of analysis is much, much bigger than EXPTIME.