NFA.to_regex() not implemented

[abhinavsinha-adrino]

@caleb531 I think by mistake I wrote NFA.to_regex() but this function is not there, instead NFA.from_regex(regex) is there. For converting NFA to regex, one has to convert NFA to GNFA and then GNFA to regex.

Very sorry for this.

[caleb531]

@abhinavsinha-adrino Oh, shoot. How soon can you submit me a PR with the code for NFA.to_regex? Unless you mean that NFA.to_regex is not feasible to implement right now, and so I should remove it from the README.

[abhinavsinha-adrino]

@caleb531 GNFA is derived from NFA, I'm not sure if I can import GNFA into NFA class. Without GNFA, we can't convert it to regex.

[caleb531]

@abhinavsinha-adrino I see. Well, we already have GNFA.from_nfa, so perhaps we can just remove NFA.to_regex from the documentation.

I will work on this now, and push out a supplemental release.

[abhinavsinha-adrino]

@caleb531 Yeah, that will be great; we are using GNFA class primarily for NFA & DFA to regex conversion. Adding a direct function will cause circular imports; maybe there is a workaround in these cases, but I'm not aware of it.

Maybe in the release notes or README, we can mention how one should convert NFA/DFA to regex using this package, it's not very trivial.

Again very sorry for this mistake.

[abhinavsinha-adrino]

@caleb531 instead of removing NFA.to_regex(), edit it to NFA.from_regex(regex), this was missed in the documentation.

Are you working on this part, or should I do it? Its just one/two line change.

[caleb531]

@abhinavsinha-adrino No worries! It was my executive decision to subclass GNFA from NFA rather than from FA (which I believe was the right decision, to achieve parity with existing API classes like MNTM/NTM).

And thanks for the heads up re: the documentation—I will take care of updating the README accordingly. I had actually just removed it in 9453d1f but as you said, I will resurrect it and correct to NFA.from_regex.

But the NFA.to_regex was really just serving as as a convenience method, correct? Can't it already be accomplished in the current v6.0.0 via the following?

GNFA.from_nfa(my_nfa).to_regex()

[abhinavsinha-adrino]

@caleb531 Thanks a lot!
Yes it can very well be achieved by GNFA.from_nfa(my_nfa).to_regex(). What I was thinking is, GNFA is not a popular part of automata theory, as its sole purpose is to help in conversion. So it is possible that many people may not be aware of GNFA and hence won't be using it. So I recommend mentioning explicitly how one should achieve NFA.to_regex functionality

[caleb531]

@abhinavsinha-adrino Understood. Could you please take a look at my main...develop diff and see how it looks to you?

https://github.com/caleb531/automata/compare/develop

I have included documentation on converting NFA to a regular expression, as well as some other corrections.

[abhinavsinha-adrino]

@caleb531 It looks great and will avoid any more confusion. Thanks again for cleaning up my mistakes.

[caleb531]

@abhinavsinha-adrino Hey, I decided to try one last thing. It looks like circular imports can work if we implement them correctly. Per https://stackoverflow.com/a/22210807/560642, if we import the entire module (rather than a from ... import), it works just fine, and all tests continue to pass:

diff --git a/automata/fa/nfa.py b/automata/fa/nfa.py
index 133289d..1d64fdd 100644
--- a/automata/fa/nfa.py
+++ b/automata/fa/nfa.py
@@ -9,6 +9,7 @@
 import automata.base.exceptions as exceptions
 import automata.fa.fa as fa
+import automata.fa.gnfa as gnfa
 from automata.fa.dfa import DFA
 
 
 class NFA(fa.FA):
@@ -710,3 +711,6 @@ def _add_new_state(state_set, start=0):
         state_set.add(new_state)
 
         return new_state
+
+    def to_regex(self):
+        return gnfa.GNFA.from_nfa(self).to_regex()

With that, can you please submit me a PR with this NFA.to_regex method and the appropriate tests / updated documentation?

[abhinavsinha-adrino]

@caleb531 Oh, then I will update soon.

[caleb531]

@abhinavsinha-adrino Just merged your PR into my develop branch after resolving a conflict in the README. Will aim to publish a v6.0.1 release (and subsequently close this ticket) tonight or tomorrow.

[caleb531]

@abhinavsinha-adrino Alright, just released v6.0.1 with the restored NFA.to_regex() method, along with tests and updated documentation. Closing this ticket accordingly. Thanks for the quick fix.

https://pypi.org/project/automata-lib/6.0.1/

[caleb531]

@abhinavsinha-adrino Reopening this issue, because we have a MAJOR problem. If I try to

>>> from automata.fa.nfa import NFA
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/caleb/Desktop/foo/.virtualenv/lib/python3.10/site-packages/automata/fa/nfa.py", line 11, in <module>
    import automata.fa.gnfa as gnfa
  File "/Users/caleb/Desktop/foo/.virtualenv/lib/python3.10/site-packages/automata/fa/gnfa.py", line 9, in <module>
    import automata.base.regex as re
  File "/Users/caleb/Desktop/foo/.virtualenv/lib/python3.10/site-packages/automata/base/regex.py", line 6, in <module>
    from automata.fa.nfa import NFA
ImportError: cannot import name 'NFA' from partially initialized module 'automata.fa.nfa' (most likely due to a circular import) (/Users/caleb/Desktop/foo/.virtualenv/lib/python3.10/site-packages/automata/fa/nfa.py)

It turns out that per our circular changes, importing NFA will fail unless we first import GNFA. This means I need to revert your PR and we are back to square one. So sorry. 😕

Apparently, the tests didn't catch this because GNFA must somehow be imported before NFA by the test runner. Ugghh lol.

[caleb531]

@abhinavsinha-adrino Okay, just pushed v6.0.2 that effectively reverts your PR and instead points to the simple workaround for direct NFA->regex conversions.

https://pypi.org/project/automata-lib/6.0.2/