Implementation regex.match on eo

[levBagryansky]

I have a task to reimplement regex.match on eolang. As I see, the main part of the task is to determine if one string belongs to the regex. I find only one solution of it so far:

1. implement nondeterministic finite automaton.
2. implement deterministic finite automaton.
3. Convert regex to NFA
4. implement Rabin Scott algorithm that convert NFA -> DFA.
5. Check if string belongs to the DFA Its also possible to use only DFA. But it may be even more complex. So the solution is enough long and complicated. If you see more simple solution please comment. Thanks.

[yegor256]

@yegor256 what is NFA and DFA? and who is Rabin Scott?)

[levBagryansky]

@yegor256 , NFA is a nondeterministic finite automaton, DFA is deterministic finite automaton. The algoritm converts the first to the second. Usually a regex can be described by the NFA like that: if we have regex (a+b)b(b+c) Each circle matchs to consistanse of the automation. We can see that a "b" can lead to two consistanse: circle 1 and circle 2. That is why it is the nondeterministic automation. So we need to iterate over each option. We also can turn it into the deterministic by the algoritm. The example of determic automation is So on the every circle each symbol lead to the determic circle. But I am looking for a way to delegate this mechanism to smth else. Now it is executing by java. Thank you.

[yegor256]

@levBagryansky maybe you can write up a short paper, explaining the algorithm? And then (or in parallel) implement the algorithm.