让我们首先了解计算理论 (TOC) 中的子集。
子集
如果 A 和 B 是集合，则 A ⊂ B（A 是 B 的子集）如果 w ∈ A 这意味着 w ∈ B；即 A 的每个元素也是 B 的元素。
例子
设 A = {ab, ba} 和 B = {ab, ba, aaa}。则 A ⊂ B，但 B ⊄ A。
设 A = {x, xx, xxx, . . .} 和 B = {∧, x, xx, xxx, . . .}. 那么，A ⊂ B，但 B ⊄ A。
设 A = {ba, ab} 和 B = {aa, bb}。然后，A ⊄ B 和 B ⊄ A。
定义
设 A 和 B 为 2 组。如果 A ⊂ B 且 B ⊂ A，则 A = B。
例子
设 A = {ab, ba} 和 B = {ab, ba}。则 A ⊂ B 和 B ⊂ A，所以 A = B。
设 A = {ab, ba} 和 B = {ab, ba, aaa}。则 A ⊂ B，但 B ⊄ A，所以 A ⊄ B。
设 A = {x, xx, xxx, . . .} 和 B = {xn| n≥1}。则 A ⊂ B 和 B ⊂ A，所以 A = B。
联盟
给定两组字符串 S 和 T，我们可以定义 S + T = {w : w ∈ S or w ∈ T} 为 S 和 T 的并集，即 S + T 由 S 或T（或两者兼有）。
例子
假设 S = {ac, bb} 和 T = {aa, bb, a}。然后 S + T = {ac, bb, aa, a}。
路口
给定两个字符串集合 S 和 T，我们可以定义 S ∩ T = {w : w ∈ S and w ∈ T}，它是 S 和 T 的交集，即 S ∩ T 由两个 S 中的字符串组成和T。
当 S ∩ T = ∅ 时，集合 S 和 T 是不相交的。
例子
设 S = {ab, bb} 和 T = {aa, bb, a}。那么 S∩T = {bb}。
设 S = {ab, bb} 和 T = {ab, bb}。那么 S∩T = {ab, bb}。
设 S = {ab, bb} 和 T = {aa, ba, a}。然后 S ∩ T = ∅
区别
对于任意 2 个字符串集合 S 和 T，我们可以定义 S − T = {w : w ∈S, w ⊄ T}。
例子
令 S = {a, b, bb, bbb} 和 T = {a, b, bab}。然后 S − T = {b, bbb}。
设 S = {ab, ba} 和 T = {ab, ba}。则 S − T = ∅。
笛卡尔积
两个集合 A 和 B 的笛卡尔积是有序对的集合 A × B = {(x, y) : x ∈ A, y ∈ B}。
例子
如果 A = {ab, ba, bbb} 且 B = {bb, ba}，则
A × B = {(ab, bb), (ab, ba), (ba, bb), (ba, ba), (bbb, bb), (bbb, ba)}。
注意 (ab, ba) ∈ A × B。
另外，请注意
B × A = {(bb, ab), (bb, ba), (bb, bbb), (ba, ab), (ba, ba), (ba, bbb)}。
(bb, ba) ∈ B × A,
但是 (bb, ba) ⊄ A × B，所以 B × A ⊄ A × B。
我们可以定义超过 2 个集合的笛卡尔积。