Technical answer: traditionally, `egrep`

used a deterministic finite automaton (DFA) internally while `grep`

used a non-deterministic finite automaton (NFA). These days, GNU `grep`

and `egrep`

take a hybrid NFA/DFA approach.

According to Friedl's book Mastering Regular Expressions, to discover if your `egrep`

(for example) has an NFA engine or if it has a DFA engine try:

```
echo =XX========================================= | egrep 'X(.+)+X'
```

Freidl (p.147) says:

If it takes a long time to finish, it's an NFA ... If it finishes quickly, it's either a DFA or an NFA with some advanced optimization. Does it display a warning message
about a stack overow or long match aborted? If so, it's an NFA.

Friedl describes the NFA engine as "regex-directed" and the DFA as "text-directed". The details of the distinction are described from p.153 of his book onwards.

The consequence is that there are some pattern/text combinations that are matched more quickly by a DFA and some that are matched more quickly by an NFA. Also, the way you write a regex for an NFA can have a significant effect on the speed of matching. Often, a DFA will be faster, but DFAs do not support lazy matching, they match differently in some cases, they cannot do look-around expressions or back-references, and they omit some other features compared to NFAs.

According to Freidl, GNU `grep`

uses a DFA when possible and reverts to an NFA when back-references are used.