rust-algorithms icon indicating copy to clipboard operation
rust-algorithms copied to clipboard

feat(string): add finite automaton

Open grabus opened this issue 10 months ago • 1 comments

added finite automaton. this is deterministic one. I am not sure if we want to split finite automaton item into deterministic and non-deterministic, but if yes, I'd implement it within separate PR.

grabus avatar Apr 19 '24 17:04 grabus

Hey! This is looking very good, but I think it should be a bit closer to the theory so that it is more general and it serves as a reference implementation.

You can take a look at this implementation. It's not perfect, but I think that's the gist.

Also, I think it's fine if we call it Dfa instead of DeterministicFiniteAutomaton.

I am not sure if we want to split finite automaton item into deterministic and non-deterministic

We do! That way we can also implement more advanced algorithms later like conversion between them, regexes, etc.

The NFA is also a good candidate for parallelism, so that's an interesting thing to explore.

alexfertel avatar Apr 20 '24 13:04 alexfertel

so I will close this while I am playing with alexfertel/atl

grabus avatar May 14 '24 17:05 grabus