集合理論中的concat表示法

Question

我正在爲自動機理論類做功課。到目前爲止，它的正則表達式並沒有太瘋狂。無論如何，我的問題是這是什麼是串聯適當的設置符號？例如，我知道R + S與R union S是一樣的，但對於我的生活，我不記得集合理論等價於串聯。

我不會發布任何問題，因爲我認爲我會很好地處理它們，任何人都可以在正確的方向上給我一點點推動力嗎？

Answer 1

我相信你指的是常規集合的連接。通常，級聯或點運算符表示常規集合的級聯。相同的表示法適用於正則表達式。例如

• AB = A·B = {XY：X∈A &ý∈B}

形式上，正則集形成的Kleene代數，這是一個冪等與Kleene星半環滿足一系列公理的算子。在代數冪等半環的代數中，乘法通常通過連接或點運算符表示爲。這就是爲什麼常規集合的連接 - Kleene代數中的乘法運算 - 用連接或點運算符表示。正則表達式也是如此。

Answer 2

R + S與R union S不同，因爲字符串不是集合。字符串在字母表這是一組。 （儘管技術上你可以將一個字符串表示爲一組有序對（char，index））。

當你打算拼接時，你應該說R + S。你不能連接一般集合。

但是，您可以連接組字符串。對於字符串U和V，並置，UV由uv形式的所有字符串組成，其中u是來自U的字符串，v是來自V的字符串。它有點像交叉積。