Regular Expression Matching Can Be Simple And Fast [2007]

Its not clear how allowing the state machine to be in all states at the same time consitutes "guess[ing] correctly", but the article is nonetheless quite informative