存在 A、B 两个正则表达式描述的数据集合 A1、B1,是否存在一种通用的方式判断 A1 完全是 B1 的子集？

[Aruforce]

比如\d 必定是*的子集。
搜索了下应该涉及编译相关的东西...半路出家完全不会啊...
有成熟的工具么？

[zhuangjia]

感觉这种场景比较适合使用 chatGPT 了

[lookStupiToForce]

要满足题述要求的完备，需要对 A 和 B 这两个正则做形式化证明（ A 可转化为 B ，属于 B 的特例，B 则不可转化为 A ）
感觉这种工作得看学计算理论的那帮人有没有造出相应的轮子

[Aruforce]

@lookStupiToForce A1 == B1 也行...

[lookStupiToForce]

英文讨论可以用 regex expression true subset 做关键词搜，不过搜出来的多是 SO 的问答或者其他讨论串

中文倒是有人写过代码解决方法，原理用的有限自动机判断是否等价 /包含（判断此人是个计算理论 /编译原理大神😂）
wu-kan[.]cn/2020/07/03/%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%85%B3%E7%B3%BB%E5%88%A4%E5%AE%9A/

OP 你有心思可以就着参考实现一下

[learningman]

简单的可以展开成 DFA 然后 dfs ，但是如果带环的话就不太好判了

[ALLROBOT]

把捕获组转换 python 的 list 、字典、字符串等数据格式，然后 if 判断完事

[lyhang]

import re

def is_subset(A1, B1):
"""
判断 A1 是否完全是 B1 的子集
参数：
A1: 列表，表示数据集合 A1
B1: 列表，表示数据集合 B1
返回值：
如果 A1 完全是 B1 的子集，返回 True ，否则返回 False
"""
# 将 B1 中的所有正则表达式编译成 pattern 对象
patterns = [re.compile(b) for b in B1]
# 遍历 A1 中的所有元素，看是否能被 B1 中的正则表达式匹配
for a in A1:
matched = False
for p in patterns:
if p.match(a):
matched = True
break
# 如果 A1 中的某个元素不能被 B1 中的任何正则表达式匹配，那么 A1 不是 B1 的子集
if not matched:
return False
# 如果 A1 中的所有元素都能被 B1 中的正则表达式匹配，那么 A1 是 B1 的子集
return True

[mascteen]

感觉可以用上范畴论了

[iamqk]

如果有 set 容器的话
把两个 set 合并，如果数目是 B1 的话
就可以判断了

[xuanbg]

单从正则字符串本身来判断的话，除非只是定义，否则应该是不准确的。因为特定目标数据会导致 A 和 B 符合定义上的交集，但实际上没有相交的数据，变成并集；或者 A 完全包含 B ，变成 B 是 A 的子集。

[Aruforce]

@lookStupiToForce 周末 再仔细看下。。感觉有点像。。。

[Aruforce]

@ALLROBOT 没太看懂 但感觉不是

[Aruforce]

@lyhang 你理解错意思了

[Aruforce]

@xuanbg 入参 只有 A 和 B 两个正则本身