4 ms·
This is misleading. Regular expressions are equally as powerful as finite state machines. So it would go: - finite state machines / regular expressions / regul
by klodolph 7y ago
This is misleading. Regular expressions are equally as powerful as finite state machines. So it would go:
- finite state machines / regular expressions / regular languages
- context-free grammars / pushdown automata / context-free languages
- recursive languages (in general, languages programmers use fall into this category)
- turing machines / recursively enumerable languages (some programming languages fall in this category, but it’s usually by accident)
- non-computable, e.g. busy beaver
Playing fast and loose with language / program because of the equivalences. Also note “regular expressions” above doesn’t include PCRE or things like backreferences.
- albertzeyer 7y agoBtw, to add on that: A pushdown automata with two separate stacks is as powerful as a turing complete language. And you could interpret a standard finite state machine as a pushdown automata without any stack. So the number of stacks is what makes it more powerful (although more than 2 stacks does not make it more powerful).
- AlchemistCamp 7y agoThanks, updated and added a note for regexp so as not to mislead!
- klodolph 7y agoIn that case it’s absolutely incorrect, not merely misleading. It definitely should not be between FSM and CFG. It should either be equal to FSM (regular expressions) or it should be much more powerful (if you have backreferences, like PCRE does, you can encode SAT problems in your regexes, and this cannot be done with CFG, but recursive languages are strictly more powerful).
- AlchemistCamp 7y ago> It should either be equal to FSM... superset != strict superset
- klodolph 7y agoThat's why I originally said “misleading”, if we’re going to be pedantic.