Well, PSPACE-hard is pretty damn hard, so this really depends on the size and complexity of your NFA ;) Of course most of the time you don&#x27;t hit the pathological cases like the one I described above. My comment was not meant to provide a guideline on how to fix this, consider it a fun observation on automata theory.