4 ms·
for real? Is RegEx actually a FSM behind the scenes? or are you trying to say something else
by afturner 7y ago
for real? Is RegEx actually a FSM behind the scenes? or are you trying to say something else
- jkern 7y agoYep. Take a look at https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
- afturner 7y agothank you very much.
- dexen 7y agoYes and no. The theoretical "regular expressions" are indeed Type-3 grammars in Chomsky's hierarchy. In practice, the common "RegEx" implementation implement a lot of extras, that break the theoretical backing, and also exhibit highly non-linear behaviors. Cf. this excellent paper by Russ Cox: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
- jldugger 7y agoDepends on the implementation, but I believe grep actually builds a Finite State Machine from its input regular expression. More complicated (non 'regular' regex) engines don't use this approach, but in theory the two are equivalent. This equivalence is one of the fundamental findings of CS, and exposure to this concept is pretty much mandatory for acquiring a degree in the field. Sadly, this perspective is not often shared in the bootcamps and autodidacts, even though it's moderately documented in https://en.wikipedia.org/wiki/Regular_expression#Deciding_equivalence_of_regular_expressions https://en.wikipedia.org/wiki/Regular_expression#Deciding_eq... But the more mindblowing aspect is that you can use nondeterministic Finite Automata for the same purpose.
- pdpi 7y agoTextbook regular expressions correspond precisely to DFAs, so they’re definitely a type of FSM. Most Regexp implementations in the wild are more powerful than textbook regexps, so they not only encode all languages accepted by DFAs, but can also encode other languages. E.g. back-references are not a feature of regular languages.