Search code examples
pythonregexfsmformal-languagesnfa

See if the intersection of regular expressions is empty using FAdo

I'm interested in seeing if there's any overlap between two regular expressions. I thought the best way is to convert the regular expressions to nondeterministic finite automata and then see if the intersection of those NFAs is empty.

I see this FAdo Python package here: https://pypi.org/project/FAdo/

And the documentation: https://www.dcc.fc.up.pt/~rvr/FAdo.pdf

Here is my function:

from FAdo import reex

def no_overlap(a, b):
    n1 = reex.str2regexp(a).toNFA()
    n2 = reex.str2regexp(b).toNFA()
    c = n1.conjunction(n2)
    return _______

assert no_overlap('(a)*', '(b)*')

But I can't figure out what to put in the blank to figure out if c is empty. I'm at a loss - thanks for your help!

Solution

  • Unfortunately this doesn't perfectly answer the original question, but I ended up solving my problem (computing the intersection of two regular expressions) using the greenery library: https://github.com/qntm/greenery