正式な言語：R違反とはどういう意味ですか？

Question

rtrivial言語とは何ですか？つまり、定義は何ですか？

rtrivialモノイドとは何ですか？

コンテキスト：正式な言語。 Afaik、R-違反言語は、宇宙式言語のサブセットです。

私は主に正式な言語とオートマトン理論のバックグラウンドを持っていますが、構文的なモノイドの特性評価ではそれほどではありません。したがって、そのような言語の小さな例で基本的な定義を与えることは素晴らしいことです。

---

（QAサイトを後ろに留まらせたくないので、複数のQAサイトをサポートするために、その質問もそこに表現するために、これらの他のサイトにもこの質問を投稿しました。 cstheory.stackexchange.com, math.stackexchange.com, Mathoverflow.net. 。一般的に私はクロスポストに反対していますが、この場合、特定の領域で質問の完全な参照を参照するという同じ目標を持っているため、クロスが投稿する質問はあなたができる最善のことです。）

Answer 1

モノイドはRに違反します グリーンの関係 Rは平等と一致します。

Answer 2

非常に良い答えも与えられています ここ に マイケル・ブロンディン:

a semigroup $ s $は$ r text {-trivial} $ iff $ a：r：b rightarrow a = b $ for all $ a、b in s $ グリーンの関係 $ 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_i subseteq a setminus {a_ {i+1}} $ for $ 0 leq i leq n-1 $。で与えられた別の定義 ピン, 、私がよく知らない、いわゆるものを使用します 拡張を自動化します （「大規模なオートマトン」）。これらの言語に関するより多くの結果を見つけることができます ピン. 。この本には英語版がありますが、私はそれを読んだことがありませんが、同じコンテンツを見つけることができると確信しています。

完全性のために、$ r text {-trivial} $ language：$ {b}^* a {a、c}^* b {a}^* b {a、b、cの例を次に示します。 }^* cup {d}^* cup abcd $。以前の定義で他の例を作成できます。言語の品種のすべての特性は、$ r text {-trivial} $言語を保持しているため、組合、交差、補完の下で閉鎖されていることに注意してください。より複雑な言語を構築するのに役立つはずです。

Answer 3

おそらくCSの人々にとってより明確なもう1つの特性は、最小限の決定論的な有限オートマトンが部分的に順序付けられている場合、通常の言語がrに違反されることです。つまり、サイクルはありません（自己ループはサイクルとは見なされません）。