Search code examples
stringsubstringstate-machinefsmdfa

Designing a simple state machine generator

I know that designing state machine generators for regular expressions is not trivial, but what about simple strings (when I say a simple string, I mean something like "abcd" -- something without any regular expression syntax). I was thinking of writing a simple string matcher using state machines, but I wanted the state machine to be generated at runtime

The input to the state machine generator is the string to be matched, the output is the state machine. I am not looking for code, but a method/algorithm to do this.

Yes, I could use any of the readily available libraries, but no thanks.

Solution

  • If you want a really simple matcher, you don't even need to build the state machine. You can just march through the pattern as you march through the string. Here is a really nice example from the book called, "Beautiful Code":

    http://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html