21 ms·
Pretty much anybody who has read a book on automata (even if long ago) will remember that each item in this list can express a superset of what the previous can
by AlchemistCamp 7y ago
Pretty much anybody who has read a book on automata (even if long ago) will remember that each item in this list can express a superset of what the previous can:
- finite state machines
- regular expressions[1]
- context free grammars
- recursive languages
- turing complete languages
- an even larger set of algorithms which cannot be encoded in any language (google Cantor Diagonalization argument, Turing Machines)
Many people, myself included, have read such books outside of the context of formal schooling. It's likely an order of magnitude more have gone through an automata MOOC. Other than Data Structures & Algorithms, it's probably the formal CS schooling material the comes up most broadly in professional programming careers.
[1]Caveat: Regular languages are equal in power to FSM but what we call "regex" have actually been extended past the point of technically being regex with PCRE and lookaround expressions. Thank you Perl and friends!
- klodolph 7y agoThis 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.