正式語言：R-trivial是什麼意思？

Question

什麼是R平凡語言？即定義是什麼？

什麼是R-trivial monoid？

上下文：正式語言。 Afaik，R-trivial語言是無星語言的一個子集。

我大部分都有正式語言和自動機理論的背景，但與句法幺半羣表徵不太相關。所以最好給一個基本的定義，或許是一個這樣的語言的小例子。

---

（爲了支持多個QA-網站，因爲我不希望有任何QA現場留下，並有一個問題也代表了那裏，我也張貼在這些網站這個問題： cstheory.stackexchange.com,math.stackexchange.com,mathoverflow.net。總的來說，我反對交叉發帖，但在這種情況下，因爲他們都有相同的目標是對特定領域的問題的完整參考，所以交叉發佈問題是您可以做的最好的事情。）

Answer 1

如果Green's relation R與其相等，則Monoid是R-trivial。

Answer 2

一個很好的答案也被Michael Blondin給出here：

半羣$ S $是$ R \ {文本} -trivial $當且僅當$一個，R：乙\ RIGHTARROW A = B $所有$ a，b \ in S $其中$ R $是Green's relation $ a：R：b \ Leftrightarrow aS^1 = bS^1 $。 $ R \ text {-trivial} $ monoids集合形成了一個變種，它可以由方程$（xy）^ n x =（xy）^ n $最終定義。

如果語言的syntactic monoid爲$ R \ text {-trivial} $，則語言爲$ R \ text {-trivial} $。這種多種語言可以被定義爲所有語言的集合，這些語言可以被寫爲一種不相交的語言聯合體，形式爲$ A_0^* a_1 A_1^* a_2 \ ldots a_n A_n^* $，其中$ n \ geq 0 $， $ a_1，\ ldots，a_n \ in $，$ A_i \ subseteq A \ setminus {a_ {i + 1}} $ for $ 0 \ leq i \ leq n-1 $。在我不熟悉的[Pin]中給出的另一個定義使用了所謂的自動擴展（「廣泛的自動機」）。您可以在[Pin]中找到有關這些語言的更多結果。這本書有英文版本，我從來沒有讀過它，但我確信你可以找到相同的內容。

爲了完整起見，下面是一個$ R \ text {-trivial} $語言的例子：$ {b}^* a {a，c}^* b {a}^* b {a ，b，c}^* \ cup {d}^* \ cup abcd $。您可以使用以前的定義構建其他示例。請注意，各種語言的所有屬性都適用於$ R \ text {-trivial} $語言，因此它們在聯合，交集和互補下處於關閉狀態。它應該有助於構建更復雜的語言。

Answer 3

對於CS人員來說，另一個特徵是，如果最小確定性有限自動機是部分有序的，即它沒有周期（自循環不被認爲是週期），則正則語言是R-trivial。