4 ms·

I take it sexp parsers are technically dfa?

• pjscott 11y ago
  S-expressions are a classic example of something that can't be matched with a DFA or NFA. In order to know how many parens are currently open (and therefore needing to be matched with closing parens) it would need an unbounded number of states.
  • jstimpfle 11y ago
    On the other hand, it's just a matter of maintaining the number of open parentheses. Similar fact, one can't count string lengths in linear time (because lengths can be arbitrarily large). But for concerns of implementation it's just O(n).