Bridging the Gap: From Regular Expressions to Machines

Earlier I said that when regular expression libraries are implemented in programming languages, the way that they work is by converting regular expressions to finite state machines and then using the FSM that they generated to process input strings.

Doing the translation from the regular expression to an FSM is interesting. There are several different ways of converting a regular expression to an FSM. It’s not a one-to-one translation. Depending on which method you choose, you can wind up with different FSMs for the same regular expression. (In fact, theoretically, there are an infinite number of different finite state machines for each regular expression!) Fortunately, that doesn’t matter, ...

Get Good Math now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.