3 ms·
(Particular, individual) regular expressions can be implemented with O(1) space. Regular expressions can do lots of useful things.
by repsilat 13y ago
(Particular, individual) regular expressions can be implemented with O(1) space. Regular expressions can do lots of useful things.
- jmpeax 13y agoThis is incorrect, under deliriums pedantic interpretation of space complexity. Some regular expressions require one to accept a certain number of examples of a character. This means that storage space for the count is required, which scales logarithmically in the count.
- repsilat 13y agoThis is why my comment began with the words "particular, individual". A regex like (1{5}0{3})\* can be implemented in constant space, but a language like matches(n, m, string): return matches((1{n}0{m})\*, string) cannot. Just think about it -- the former is just a DFA, and so of course you can do it in constant space (provided your input stream is abstracted away, or you use a TM.