Depends on the implementation, but I believe grep actually builds a Finite State Machine from its input regular expression. More complicated (non 'regular' rege

Depends 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.