6 ms·
Hmm my relevant theory is a little sketchy, but there are FSMs that aren't modellable by regex right? (e.g. Nested tags).
by nopassrecover 16y ago
Hmm my relevant theory is a little sketchy, but there are FSMs that aren't modellable by regex right? (e.g. Nested tags).
- batterseapower 16y agoActually they are exactly equivalent. See for example http://en.wikipedia.org/wiki/Regular_expression http://en.wikipedia.org/wiki/Regular_expression ("Regular expressions in this sense can express the regular languages, exactly the class of languages accepted by deterministic finite automata.")
- xtacy 16y agoMost of the regex engines in languages (like Perl) allow keeping track of state by using back references. If you're talking about this, then theoretically, they aren't "finite state" machines.
- jemfinch 16y agoNested tags can't be matched by fsms.
- andrewf 16y agoFSMs can't handle nested tags. Pushdown Automata can.
- qntm 16y agoMost "regular" expression engines in modern programming languages can handle back-references (e.g. "(.)\1"), which are actually so complex that you need a full-blown Turing machine to handle them.