Repeat pattern not correct in Regular Expression Evaluation via Finite Automata

[bixuanzju]

> let example = (Concat (Literal 'c') (Repeat (Literal 'd')))
> "c" `matches` example
=> False

But "c" should matches "cd*", right?

[bixuanzju]

On a second thought, I think the problem is how you process each input symbol. In your article, you follow any Free Moves before reading each input symbol, while in common theory-of-computation textbooks, we first read a input symbol a, then the current states are updated to be the set of all states that can be reached from input a (and possibly following several Free Moves).

[pbrisbin]

Thank you very much for reporting this. This post was at the very edge of my knowledge on the matter and definitely a "figure it out as I go" style post. I'll have to sit down and spend some time working through that example to find the bug you're describing.

[pbrisbin]

I believe I found the bug. It was actually in accepted. Originally, I said the criteria for accepting input was that any of the machine's current states are an accept state. In actuality, if we can reach an accept state from our current state via a free move (or many) we can also say it accepted the input. You'll see a small commit in a minute showing the fix.

I think there might still be something to your point about "read the input, then update the current state" but it also may be that in Haskell "update the current state" isn't easy, so a different approach works out better. I'd be interested in some day adding a more robust test suite to this little toy to make sure it is in fact correct beyond the example's I've tried.

Anyway, thanks again!