R自明言語とは何ですか? つまり、定義は何ですか？
R自明なモノイドとは何ですか?
コンテキスト: 形式言語。確かに、R-自明な言語はスターフリー言語のサブセットです。
私は主に形式言語とオートマトン理論のバックグラウンドを持っていますが、構文的なモノイドの特徴付けについてはあまり知りません。したがって、そのような言語の小さな例で基本的な定義を示すとよいでしょう。
（QAサイトを置き去りにしたくないため、複数のQAサイトをサポートし、その質問もそこに表示するために、この質問を他のサイトにも投稿しました：cstheory.stackexchange.com、math .stackexchange.com , mathoverflow.net . 一般に、私はクロスポストに反対していますが、この場合、特定の分野の質問の完全な参照になるという同じ目標を持っているため、質問をクロスポストすることが最善の方法ですできるよ。）
Michael Blondinからも非常に良い回答が得られました。
半群 $S$ は $R\text{-trivial}$ iff $a : R : b \Rightarrow a = b$ for all $a, b \in S$ ここで、$R$ はGreen の関係$a : R : b \Leftrightarrow aS^1 = bS^1$. $R\text{-trivial}$ モノイドのセットは、方程式 $(xy)^nx = (xy)^n$ によって最終的に定義できる多様体を形成します。
構文モノイドが $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$, $A_i \subseteq A \setminus {a_{i+1}}$ for $0 \leq i \leq n-1$. [Pin]で与えられた別の定義は、私がよく知らない、いわゆる自動拡張機能(「拡張オートマトン」) を使用します。[ピン]で、これらの言語に関するより多くの結果を見つけることができます。この本には英語版があります。私は読んだことがありませんが、同じ内容を見つけることができると確信しています。
完全を期すために、ここに $R\text{-trivial}$ 言語の例を示します: ${b}^* a {a,c}^* b {a}^* b {a,b,c }^* \cup {d}^* \cup abcd$. 前の定義を使用して他の例を作成できます。$R\text{-trivial}$ 言語については、さまざまな言語のすべてのプロパティが保持されることに注意してください。したがって、それらは結合、共通部分、および補完の下で閉じられています。より複雑な言語を構築するのに役立つはずです。
モノイド上のグリーンの関係R が等式と一致する場合、モノイドは R-自明です。
もう 1 つの特徴は、おそらく CS の人々にとってより明確ですが、通常の言語は、その最小の決定論的有限オートマトンが部分的に順序付けられている場合、つまりサイクルを持たない場合 (自己ループはサイクルとは見なされません)、R 自明であるということです。