Comment by mekoka | Hacker News Reader

Comment by mekoka | Hacker News Reader

Parent Full thread

I'm not a CS graduate. I first learned of state machine from an article posted here on HN a few months ago.

I learned regular expression from the regular-expression.info site and from the first 4 chapters of Jeffrey Friedl's book over 5 years ago. I don't recall an introduction to NFA/DFA from them either. I'm pretty comfortable with regex and use them regularly (no pun intended) and so far, I don't feel that I've missed much.

I'm not disagreeing with your view, but I think it's worth pointing out from someone having developed an understanding of regex from a different perspective, that NFA/DFA might not be such a strong prerequisite and people should not feel like they're going in at a disadvantage.

An understanding of finite-state machines is useful, because that way you'll understand the limitations you have when using regular expressions, which have been grossly misused.

It also helps you write optimal regular expressions - for instance if your regular expression clearly describes a DFA, then it will probably perform well. Otherwise in many cases you can optimize it - just as you can turn any NFA into a DFA.

It isn't so clear and cut these days however, as the regexp capabilities provided by modern libraries exceed the capabilities of finite state machines - for instance the engine in Perl 5.10 has support for recursion, which means a regular expression in Perl 5.10 can describe a Pushdown Automaton (PDA) instead, so things get way more complicated.

Either way, I suggest you do some reading on Automata Theory, because it's fun and not that hard.

Chapter 4 of Jeffrey Friedl's "Mastering Regular Expressions" goes in depth about NFA/POSIX NFA/DFA. It even has car analogies!

It must have been the 3 first chapters then. At the time, they were enough for me to understand and "get going" with regex. Various other online resources have filled little gaps here and there over time. This thread makes me want to revisit the book and resume my reading of the next 3 chapters, a long overdue promise to myself. I'm glad that the book will cover the topic of FA then.

Reply on news.ycombinator.com