improvement possible in NFA.kleene_star(self)

[abhinavsinha-adrino]

Automata version: 5.0.0

Presently kleene_star() function adds two new states (new initial state and new final state). However, this can be done by just adding one new initial state. The following image explains the method: It is not necessary for us to have only one accept state.

I'm working on the conversion of regular expressions to NFA, it has to be done piecewise, and I am using the functions concatenate, kleene_star (wrote union myself). If kleene_star function adds only one new state instead of two, it would generate NFA with lesser states in this respect.

Bug

Also there is a bug:

from automata.fa.nfa import NFA
nfa = NFA(
    states={'q0', 'q1'},
    input_symbols={'a'},
    transitions={
        'q0': {'a': {'q1'}}
    },
    initial_state='q0',
    final_states={'q1'}
)

nfa2 = nfa.kleene_star()

Traceback (most recent call last):
  File "/media/abhinav/store/GitHub/automata/test.py", line 12, in <module>
    nfa2 = nfa.kleene_star()
  File "/media/abhinav/store/GitHub/automata/automata/fa/nfa.py", line 213, in kleene_star
    if '' not in new_transitions[state]:
KeyError: 'q1'

It assumes outgoing transitions from every final state which is not necessarily true.

[caleb531]

@abhinavsinha-adrino I see. Well, I am not very familiar with the math behind the Kleene Star operation (that was a user contribution to the library). But, if you would be up to submitting a PR with new/updated tests, I would gladly review it!

[caleb531]

@abhinavsinha-adrino Just in case you were wondering: I plan to keep this issue open until your code gets merged to main as part of the v6 release. 😄

[caleb531]

@abhinavsinha-adrino Closing this issue now that Automata v6 is released with these optimizations/fixes. Thanks again for contributing these!