regex - 正则语言闭包取消连接

Question

我正在尝试找到一种可以采用常规语言并将其与另一种语言“取消连接”的操作。例如:

a*L - a* = L | where L is a regular language

我知道差(减)不是我想要的运算。但我相信我已经表达了我的观点。

另一种看待它的方法是，如果有一个逻辑上等于 (A ∪ B) 的集合 L，但我们无法访问 A。因此，如果我们只能使用 L、B 及其导数，我们能以某种方式导出 A 吗？基本上:

L - B = A | L = (A ∪ B)

我对这个问题进行了很多思考，使用了许多不同的补语、交集和常规语言的其他闭包属性，但我就是无法弄清楚。

我能想到的最好的办法是:

A = ((L - B) ∪ (A ∩ B) | L = (A ∪ B)

但是这需要 A 在右侧。

Answer 1

If L = A U B, define an operator - such that L - B = A.

问题是运算符 - 没有明确定义:给定 L 和 B，可能有几种语言满足 L = A U B。特别是，如果 A 是 L 的子集，并且任何(可能不正确) ) L\B 的超集，则 A 是一个解；也就是说，如果 A = (L\B) U C，其中 C 是 B 的子集(可能不正确)，则 L - B 也可能等于该集合。

现在，您可以定义 - 来表示所有此类 A 的集合，在这种情况下，您可以使用集合差、并集和幂集运算符使其可行。那么，L - B = Q 其中 Q = {(L\B) U {}, (L\B) U {B[0]}, ..., (L\B) U B = L}。

如果您指定，则可以明确定义 - 始终返回 Q 的“最小”元素(对于有限集，是元素最少的元素；对于无限集，是所有其他集的子集)在这种情况下，您只需恢复 L\B。

If L = B.A, define an operator - such that L - B = A.

这里也存在类似的问题:可能有几种语言，当附加到 B 后，给出 L。例如，考虑 B = a*，A 的两个选择:a* 和 {e}，该语言只包含空集。您可以毫不费力地证明 a* a* = a* e，因此 L 是相同的，B 是相同的，并且 L - B 现在必须产生两个不同的值:a* 或 {e}。