Duplicating states when removing lambdas of NFA

[danichurras]

It seems to be duplicating every state when I ask to remove the epsilons.

from automata.fa.nfa import NFA

pattern = 'test|ok'
nfa = NFA.from_regex(pattern)
nfa = nfa.eliminate_lambda()
nfa.show_diagram('test.png')

Output:

[caleb531]

On the surface, it seems like duplicating the states would actually make sense in order to create a machine without lambda/epsilon transitions, especially since the resulting machine needs to accept the same language as the original.

@eliotwrobson @Tagl Can you guys confirm if this is the expected behavior according to the algorithm we are using?

[eliotwrobson]

So I didn't write this particular algorithm (and am not a huge expert on how it works), but I think this is actually the expected behavior. This is because the eliminate lambda algorithm intentionally doesn't remove any states, and these are the same states that appear when the NFA was constructed originally:

Now that I look at it, there actually might be a way to reduce the number of states that get created in this situation, but that's really a separate issue.

EDIT: Sorry, the algorithm actually does remove states in some situations.

[eliotwrobson]

Can this issue be closed? It seems like this is expected behavior of the algorithm and parsing logic.

[caleb531]

@eliotwrobson Yeah, I've been mulling over what to do about this issue. But ultimately I agree that it's fine as-is.

@DanielChavesSimao I agree that the behavior is as expected. My apologies if that complicates matters on your end, but please let me know if there's a deeper issue you need help working around.