Well, I read Jeffrey Friedl's "Mastering Regular Expressions" two or three times since the 2nd edition was released and I can tell you there's no way anything more than a simple regex is going to be easier to grok when converted to some FSM, especially with look-behind or lazy operators and significant backtracking. I'm referring to the Perl/PCRE regular expression flavour which is the only variant that matters to me. Perl regexen are NFA so I'm not sure your assumptions about FSMs apply.