concatenation - 集合论中的 concat 符号

Question

我正在为自动机理论课做作业。到目前为止，它只是涉及正则表达式的证明，并没有太疯狂。无论如何，我的问题是什么是连接的正确集合符号？例如，我知道 R + S 将与 R union S 相同，但对于我的一生，我不记得等效于串联的集合论是什么。

我不会发布任何问题，因为我认为我会很好地解决它们，有人可以在正确的方向上给我一点帮助吗？

Answer 1

我相信您指的是常规集合的串联。通常，连接或点运算符表示规则集的连接。相同的符号适用于正则表达式。例如

• AB = A·B = { xy : x ∈ A & y ∈ B }

形式上，正则集形成了一个 Kleene 代数，它是一个具有 Kleene 星算子的幂等半环，它满足一组公理。在像幂等半环这样的代数中，乘法通常通过连接或点运算符表示。这就是为什么常规集合的连接（Kleene 代数中的乘法运算）由连接或点运算符表示。正则表达式也是如此。

Answer 2

R + S 与 R union S 不同，因为字符串不是集合。字符串在一个字母表上，这是一个集合。（虽然从技术上讲，您可以将字符串表示为一组有序对（char，index））。

当您要连接时，您应该只说 R + S 。您不能连接通用集。

但是，您可以连接字符串集。对于字符串 U 和 V 的集合，连接, UV 由 uv 形式的所有字符串组成，其中 u 是来自 U 的字符串，v 是来自 V 的字符串。这有点像叉积。