形式言語：R-trivialはどういう意味ですか？

Question

R-trivial言語とは何ですか？私。定義は何ですか？

R-trivial monoidとは何ですか？

コンテキスト：形式言語。 Afaik、R-trivial言語は、星空言語のサブセットです。

私はほとんどが形式的言語とオートマトン理論の背景を持っていますが、構文的モノゴイドの特徴付けはあまりありません。したがって、そのような言語の小さな例を使って基本的な定義を与えるとよいでしょう。

---

（私は任意のQAサイトは、背後に滞在しても、そこに表され、その質問を持っている必要がしたくないので、複数のQA-サイトをサポートするために、私はまた、これらの他のサイトでこの質問を掲載しています： cstheory.stackexchange.commath.stackexchange.commathoverflow.net一般的に私はクロスポストに反対していますが、この場合、特定の分野での質問の完全な参照であるという同じ目標を持っているため、クロスで質問を投稿することができます。

Answer 1

Monoidは、Green's relationのRが平等と一致する場合、R-trivialです。

Answer 2

非常に良い答えはまたMichael Blondinでhereを与えられている：すべてのための$ B \ RIGHTARROW A = B：R：

A半群$ S $は$ R \テキスト{-trivial} $のIFF $ aは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 $の形の言語の互いに素な和集合として書くことができるすべての言語の集合として、 $ 0 \ leq i \ leq n-1 $に対して、$ a_1、\ ldots、a_n \をA $、$ A_i \ subseteq \ setminus {a_ {i + 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の人々にとっては、おそらくはっきりしたもう一つの特徴は、その最小限の決定論的有限オートマトンが部分的に順序づけられているならば、普通の言語であることです。つまり、サイクルはありません（自己ループはサイクルと見なされません）。