39 ms·
> Not at all true, the language of balanced parens is not regular and cannot be matched by a FSM no matter how much memory you have. But this is not what the g
by Sharlin 13y ago
> Not at all true, the language of balanced parens is not regular and cannot be matched by a FSM no matter how much memory you have.
But this is not what the grandparent was saying. They said that the language of balanced parentheses with some depth limit d can be matched with a FSM, for any finite d. Similarly, a "Turing machine" with a bounded tape can only recognize a bounded version of the balanced parentheses language.