perl vs grep

A friend at work claimed that perl uses NFAs and grep uses DFAs. He gave this example regular expression: (a?){30}a{30}. Then he ran the following command:

echo "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" | grep -E "(a?){30}a{30}"

which found a match instantaneously. Then he ran the following command:

perl -e "print \"match\\n\" if 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' =~ /(a?){30}a{30}/"

About 5 minutes later it printed "match".

I get the impression that grep really does convert a regular expression into a DFA, which is cool, though I seem to recall that DFAs can get pretty big for some evil regular expressions. I'll have to try giving it such an expression.

I get the impression that perl is a bit more ad-hoc than using NFAs -- I think perl can do more powerful things than NFAs support. However, it does appear that perl is not converting regular expressions into DFAs.