Regular Expression conversions in both direction + NFA.eliminate_labmda + some other functions and changes

[abhinavsinha-adrino]

Thanks for this nice library.

So basically, I have worked on converting an NFA/DFA to regular expression and also backward, regular expression to NFA conversion. All other changes were done to help this task, test it, and remove existing errors.

1. New class added: GNFA - Generalised Nondetermistic Finite automaton. (as automata/fa/gnfa.py). I have added a description of GNFA in README.me explaining its characteristics.

• GNFA.from_nfa(cls, nfa)
• GNFA.from_dfa(cls, dfa)
• GNFA.to_regex(self) #13
• GNFA.show_diagram(self, path=None, show_None = True All other functions were defined as helper functions or for initializing the class. Check README.me for all additions.

2. Additions /Changes to NFA (automata/fa/nfa.py)

• NFA.from_regex(cls, regex) #13
• NFA.eliminate_lambda(self) #31
• NFA.kleene_star(self) Debugged and changed it according to #45
• NFA.union(self, other)
• NFA.show_diagram(self, path=None)
• NFA.option(self) for ? but can't read '' because of the way this empty symbol is defined here. Nevertheless, this can help in building other NFAs (as helped in regex to NFA conversion)

3. Regular expressions (automata/base/regex.py): Just a set of methods for dealing with regular expressions. I have explained the syntax for a regular expression in README.me

• automata.base.regex.validate(regex)
• automata.base.regex,issequal(re1, re2)
• automata.base.regex.issubset(re1, re2)
• automata.base.regex.issuperset(re1, re2)

[caleb531]

@abhinavsinha-adrino Wow, thank you for all this work! There's more in this PR than I was expecting, but I welcome it! Two things, however:

1. Do you feel like there is not enough code overlap between GNFA and NFA to have GNFA subclass from NFA directly? I just wonder how much NFA logic is duplicated by adding GFNA to the mix.
2. Also, there appear to be failing tests when your changes are run on CI (GitHub Actions). Can you please review and resolve them? https://github.com/caleb531/automata/actions/runs/2735999465

[abhinavsinha-adrino]

@caleb531

1. Yeah, I added it under it because theoretically it is derived from NFA. In the future, I think of adding other features such as reading inputs, so maybe it can remain there.
2. Yeah, I noticed, forgot to run all tests before making PR, sorry for that. I did one more commit to it few minutes ago, some tests are still failing for DFA, but actually, they are correct, just the state names aren't matching because they are string forms of sets. I will try to figure it out.

[caleb531]

@abhinavsinha-adrino

1. I meant to ask why you chose to subclass GNFA from the abstract FA class and not from NFA. Currently, your docs show GNFA(FA), but if you say GNFA is theoretically derived from NFA, then I would expect to see GNFA(NFA). But let me know your thoughts.
2. No worries! Although I am wondering why DFA tests are failing at all. All tests were passing before this PR was created, so your changes must've affected DFA somehow (even though your PR seems to mostly relate to NFAs). Any ideas?

[abhinavsinha-adrino]

@caleb531

1. Oh I understand, deriving from NFA will be better. I will do it in sometime.
2. I changed two lines in dfa.py in _stringyfy_states(states) function. it was not actually made for handling integer states. DFAs are the point of comparison of finite machines, so NFAs are converted to DFA ultimately.

[abhinavsinha-adrino]

@caleb531

1. I changed GNFA to be derived from NFA
2. It's done now! all tests are passing. (at least on my PC :smiling_face_with_tear: )

[coveralls]

Coverage remained the same at 100.0% when pulling 548c958181ae150c60b8a5bd8c58cc38e334e4d2 on abhinavsinha-adrino:main into dda6e64d74e74097116467f29ff7d3d810c281ec on caleb531:main.

[caleb531]

I changed two lines in dfa.py in _stringyfy_states(states) function. it was not actually made for handling integer states

Ah yes, sorry about that. I made commits a while back to handle non-string states for NFAs, but after reviewing those commits (c381159 and 31fbe8f), I suppose I never updated the corresponding logic for DFAs.

One more thing: all tests are passing across all supported Python versions, which is great. However, the coverage % decreased a little, and I really strive to maintain 100% coverage for the library. Could you please examine the coverage report below to see what additional test cases you might need to handle?

https://coveralls.io/builds/51150916

As for everything else, it will take me a couple days to really review all the code you've contributed (I've only skimmed it so far). I may have a few minor comments for you re: documentation or coding conventions. So be on the lookout for those.

Overall, I am very pleased with what I am seeing, so thank you for everything so far.

[abhinavsinha-adrino]

Yeah, I will write the test cases, will take some time. This was the first time I have done this work; never worried about coverage before :sweat_smile:

I have tried my best to follow CONTRIBUTING.md, yes write if any changes are to be made, I'll do.

Much of this work depended on already existing functions, so it was nice to work upon it. And this is one of the few packages that exist for automata, and this is probably the best! So thanks to you!

[abhinavsinha-adrino]

Can u help me help here @caleb531 , Here the line no. 138 shows a partial hit because the case when len(master)==0 is not covered in tests. But it is a helper function and length of the master list is never going to be zero. How can I tackle this?

[caleb531]

@abhinavsinha-adrino Hmm, might you be able to cover that branch if you provide an empty string as a regex to your conversion method?

That is, writing a test for:

NFA.from_regex('')

[abhinavsinha-adrino]

@caleb531 It didn't work, I didn't make other functions accept zero-length string, they show errors.

Another problem is that NFA is not allowed to have just one state, which is also the initial state according to current validation rules.

automata.base.exceptions.MissingStateError: initial state 0 has no transitions defined

I think I can fix that partial hit by changing for loop to a while True loop. But still, we are not allowing '' as an input regex which should ideally return an NFA with one state.

[caleb531]

@abhinavsinha-adrino I would recommend updating the validation rules to allow for a single-state machine, then. I assume the same single-state case is equally valid for DFAs, as well, correct?

As for the loop, you can just ignore the partial branch by adding # pragma: no branch after the colon of the loop, e.g.

for i in range(len(master)):  # pragma: no branch
    ...

[caleb531]

@abhinavsinha-adrino I think you're pretty close, but there's still some missed coverage in gnfa.py: https://coveralls.io/builds/51282846/source?filename=automata%2Ffa%2Fgnfa.py#L237

Also, I still left you some comments to make some tweaks to the README markup. Thank you again for everything you're doing!

[abhinavsinha-adrino]

@caleb531 Where do I see the comments for README? I'm a bit new here :smiling_face_with_tear: Also my semester started so I'm getting less time for this.

[caleb531]

@abhinavsinha-adrino No worries! It should be under the Files Changed tab at the top of the PR. Here are some screenshots of the comments I've posted:

[abhinavsinha-adrino]

@caleb531 Thanks a lot! I will do the changes soon.

[caleb531]

@abhinavsinha-adrino Thanks! Also, I'd hate to add on one more thing, but it looks like the coverage has decreased ever so slightly:

https://coveralls.io/builds/51359029

[abhinavsinha-adrino]

@caleb531 Somehow, I'm not able to see the comments in the Files Changed tab.

And can you please update the README, I have been very busy these times. I hope only little work is left now.

[caleb531]

@abhinavsinha-adrino Yep, I'll take care of the README, and I'll post comments on the remaining items in a little bit.

[caleb531]

@abhinavsinha-adrino So it looks like all of my outstanding comments on this PR have been resolved, and I see that you've brought the code coverage back up to 100%. So I think everything is done on your part.

I'm taking care of the README cleanup now, and I have a few more housekeeping tasks to perform before pushing v6. But besides that, this PR should be merged very soon.

Thank you for all of your contributions to the library. I know it will be much appreciated by many when v6 goes live.