I am not convinced that what is shown as an NFA corresponds to what is normally understood as an NFA. I don't think that makes it bad (in fact, it can do more t

I am not convinced that what is shown as an NFA corresponds to what is normally understood as an NFA. I don't think that makes it bad (in fact, it can do more things than a strict NFA, like capturing and back-references), but it is remarkably different to a Thompson NFA or a Glushkov NFA. Something that can backtrack has a stack. I suspect this removes you from 'finite' territory; the 'F' in '*FA'. I think Friedl has a lot to answer for in his muddying of the waters here. It's created a lot of headaches for us over the years, as we implement both DFA and NFA (strict) matching in Hyperscan, and people do ask us why our NFAs can't do backreferences. :-)