使用FAdo查看正则表达式的交集是否为空

Question

我想知道两个正则表达式之间是否有任何重叠。我认为最好的方法是将正则表达式转换为非确定性有限自动机，然后查看这些 NFA 的交集是否为空。

我在这里看到这个 FAdo Python 包：https://pypi.org/project/FAdo/

以及文档：https://www.dcc.fc.up.pt/~rvr/FAdo.pdf

这是我的函数：

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)*')

但是我不知道在空白处放什么来判断c是否为空。我不知所措 - 感谢您的帮助！

Answer 1

不幸的是，这并不能完美地回答最初的问题，但我最终使用 greenery 库解决了我的问题（计算两个正则表达式的交集）：https://github.com/qntm/greenery

使用FAdo查看正则表达式的交集是否为空

See if the intersection of regular expressions is empty using FAdo

python

regex

fsm

nfa

formal-languages