Regular Expression Matching Can Be Simple And Fast

Re:Regular Expression Matching Can Be Simple And Fast by alexk on Thursday February 05, 2009 @01:21AM (#467203)

"some of which are completely incompatible with the usual NFA and DFA algorithms" - It would be nice if you pointed to some article/resource giving more info on this.

[ Parent | on HN ]

Re:Regular Expression Matching Can Be Simple And Fast by tome on Thursday February 05, 2009 @06:05AM (#467561)

Well here's a starter for you. Using enhanced regex syntax you can match a language containing strings of prime length. On the other hand (using the pumping lemma[1]) you can prove that that set is not regular, hence not detectable by a standard regex.

[1] http://books.google.com/books?id=MDQ_K7-z2AMC&pg=PA47...

[ Parent | on HN ]

Re:Regular Expression Matching Can Be Simple And Fast by llimllib on Thursday February 05, 2009 @09:40AM (#467846)

Sipser's book is great for understanding this stuff, IMHO: http://books.google.com/books?id=eRYFAAAACAAJ&dq=sipser+...

[ Parent | on HN ]