4 ms·
This is an example of an important piece of knowledge that typically only programmers with a formal education in computer science are taught. This theorem is ta
by 2sk21 7y ago
This is an example of an important piece of knowledge that typically only programmers with a formal education in computer science are taught. This theorem is taught in all formal language courses.
- saagarjha 7y agoI had friends who came into college already knowing this, so this isn't a given.
- coreyp_1 7y agoYou may know of a few individuals who already knew this, but that doesn't discount the gp's word "typically". Most people don't know about it, period. For those who do know about it, unless they have taken an Automata or Theory of Computing course, then they have probably still missed the point of this factoid, which is actually the main reason that this theorem is important. A Finite State Machine is capable of performing many computations, but is limited in processing capability in that it has no memory. A Regular Expression is capable of expressing the exact same computations as the FSM, and is subject to the same constraint as the FSM and therefore the same limitations. (Of course, it is also important to know that the RegEx that is talked about in an Automata class is different from the RegEx that most programmers and SysOps deal with in practice). The underlying (important) concept is that the process of validating the pattern of characters in any string is simply a proxy for understanding a computational problem. In fact, all computational problems can be represented in this paradigm (the validation of a string of input). Whether or not the machine in question can perform that validation is the purpose of the Automata or Theory of Computing class. It's not sufficient to say "I know a fact." And simply knowing the fact isn't the point of the class. The reason for the class is to understand why the fact is important to know.
- saagarjha 7y agoI am specifically asserting that there were people in my college freshman class who had a handle on what the statement meant, its implications, and a whole lot more on formal automata than you've talked about here. Mostly because they had an interest in it before arriving and were exposed to it in some way beforehand, be it through an actual textbook or practical experience. What I'm trying to say is that there is nothing that can only be learned in a class; it just often provides a decent framework for getting a well-rounded exposition to a topic.
- umanwizard 7y agoI know this and I don’t have a formal education in computer science. In general you don’t need to pay someone to tell you to read books. You can just read them.
- dgb23 7y agoThat is certainly true but these theoretical concepts don't seem to have obvious/tangible benefits at first, so it is very understandable that many who are self-taught wouldn't know much about them.
- tomxor 7y agoThis is true for me, i'm unlikely to have learnt about this unless it particularly interested me.
- tomxor 7y agoOut of interest, what book did you read that explained this? I know a bit about FSMs, but for regex I only know they are based on them - However my self learning tends to be more impulsive and reactive.
- umanwizard 7y agoI don’t remember, since I’ve known about this construction for years. Could just be some lecture notes I downloaded from somewhere.
- edflsafoiewq 7y agoI think I learned this because of the pumping lemma for regular languages. In the FSM picture, it becomes totally obvious: every sufficiently long path in a finite graph contains a loop.
- pubby 7y agoThe "Dragon" compiler book is pretty comprehensive on regex.
- stcredzero 7y agoThis is an example of an important piece of knowledge that typically only programmers with a formal education in computer science are taught. This is the 21st Century. Why aren't we teaching stuff like this in Middle School? It wouldn't require an entire course. Just cover FSM and stack machines, then letting people know that there's stuff beyond that. This would get people a basic level of the "mental furnishings" to deal with notions of computational complexity, beyond the level of total fuzzy "woo." In 2019, ordinary people need to know something about this stuff to make decisions at work and to vote! Yes, just the most basic, minimally concrete idea of how this stuff works would be valuable for society. When Ford automobiles were new, some new car owners would try to "fix" their cars by hanging bulbs of garlic under the hood. Today, we find this quaint, magical thinking, because everyone has the barest, minimally concrete, idea of how a car engine works. Are you annoyed at the general ignorance of politicians around technical issues? Well, it's just analogous to politicians with the above level of automotive ignorance passing motor vehicle laws.
- dgb23 7y agoI agree in general but I find this piece of knowledge to be too theoretical and specific (the equivalence of regex & finite automata). I find it much more important to know how networking and the Internet works and basic client-server architecture. And maybe some things about authentication. These topics seem much more tangible and important to non-technical people than CS theory.
- pingyong 7y agoPretty sure this equivalence was more or less the first sentence in the regex tutorial I read during high school...
- hyperpape 7y agoGeneral technical literacy is important, but I have a hard time connecting the equivalence of finite automata and regular expressions to anything one would vote on (and I say that as a fan of automata!)
- AlchemistCamp 7y agoPretty 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!
- anentropic 7y agoI would love to read more about why this is important/interesting/useful My eyes very quickly glazed over while reading the blog post, it seemed like an obscure theoretical curiosity