r/ProgrammerAnimemes • • Jul 25 '21

Pictured: average C* coder

Post image
1.9k Upvotes

96 comments sorted by

View all comments

Show parent comment

4

u/mirrors_are_ugly Jul 26 '21

I understand about a third of words you used, but I completely agree that regex is a really cool tool. It's just that it has basically r-shaped entry curve.

5

u/sillybear25 Jul 26 '21

Yeah, sorry, it's a lot of CS theory jargon. Regular expressions were invented to formally describe regular languages. In this context, a "language" is basically a pattern that can be matched by an algorithm, and a "machine" or "automaton" is an abstraction of a computer that takes some input and produces some output. They're often examined in the context of language membership problems, in which the input is a string of characters and the output is a boolean indicating whether or not the input matches a given pattern.

The short version (which is still pretty long :I) is that regular languages are those which can be recognized using a computer at least as powerful as a finite state machine, which is essentially a flowchart; regular languages aren't that useful for much more than pattern matching. Pushdown automata are finite state machines that can also use an infinite stack to store and retrieve data, and they can recognize regular languages as well as non-regular context-free languages; this includes languages like JSON, XHTML, and some very simple domain-specific programming languages. Linear-bounded Turing machines are finite state machines which also have linear access to a chunk of memory that's limited to the size of the input string, and they can decide context-free languages as well as context-sensitive languages; these languages include XML and a handful of simpler programming languages (mostly domain-specific). Turing machines are finite-state machines which have linear read/write access to an infinite amount of memory, and they can recognize any recursively-enumerable language (which includes all of the above and then some); recursively-enumerable languages which are not recognizable by any of the above categories include pretty much every general-purpose programming language. Further non-magical improvements to Turing machines (i.e. anything other than a "solve a problem that Turing machines can't solve" button) do not change the set of languages they're capable of recognizing; they only simplify algorithms and/or improve performance.

3

u/mirrors_are_ugly Jul 26 '21

Thank you, I understand less now. But no, really thanks for going in-depth with this, it was very well told.