> and most definitely egrep and classic Thompson DFA construction and DFA->NFA conversion was definitely Unix folklore/taught in Uni I think you mean "Thompson

> and most definitely egrep and classic Thompson DFA construction and DFA->NFA conversion was definitely Unix folklore/taught in Uni I think you mean "Thompson NFA construction" and "NFA->DFA." Regardless though, this is not what the OP is pointing out. 'egrep' (or just GNU grep these days) is doing something more clever (emphasis mine): > Al Aho expected his deterministic regular-expression recognizer would beat Ken's classic nondeterministic recognizer. Unfortunately, for single-shot use on complex regular expressions, Ken's could finish while egrep was still busy building a deterministic automaton. To finally gain the prize, Al sidestepped the curse of the automaton's exponentially big state table by inventing a way to build on the fly only the table entries that are actually visited during recognition. Russ Cox talks about this a bit in part 3 of his articles on regex matching[1]. Its implementation in RE2 is here: https://github.com/google/re2/blob/master/re2/dfa.cc https://github.com/google/re2/blob/master/re2/dfa.cc [1] - https://swtch.com/~rsc/regexp/regexp3.html https://swtch.com/~rsc/regexp/regexp3.html