공식 언어 : R-trivial은 무엇을 의미합니까?

Question

R-trivial 언어 란 무엇입니까? 나는. 무엇이 정의인가?

R-trivial monoid 란 무엇입니까?

컨텍스트 : 형식 언어. Afaik, R - 사소한 언어는 starfree 언어의 하위 집합입니다.

나는 공식적인 언어와 자동 자료 이론에 배경 지식을 가지고 있지만 구문 론적 인 단조로운 특성에 대해서는 그렇지 않다. 어쩌면 그런 언어의 작은 예를 들어 기본 정의를 내리는 것이 좋을 것입니다.

---

(I 어떤 QA-사이트는 뒤에 남아서도 표현이 질문을하고 싶지 않기 때문에 여러 QA-사이트를 지원하기 위해, 또한이 다른 사이트에이 질문을 게시 한 : cstheory.stackexchange.com, math.stackexchange.com, mathoverflow.net 일반적으로 교차 게시에 반대합니다. 그러나이 경우에는 특정 지역에서 전체 질문을하는 것이 동일한 목표를 가지고 있기 때문에 교차 게시 질문을하는 것이 가장 좋은 방법입니다. .

Answer 1

Monoid는 Green's relation R이 평등과 일치하는 경우 R-trivial입니다.

Answer 2

(A)는 아주 좋은 대답은 Michael Blondin에 의해 here을 받고있다 :

반군의 $의 S $으로 $ R의 \ 텍스트입니다 {-trivial} $ IFF $ A : R : B \ 우측으로 향하는 화살표 A = $ B에 대한 모든 S $에서 $ R $은 Green's relation $ a : R : b \ Leftrightarrow aS^1 = bS^1 $입니다. $ R \ text {-trivial} $ monoid의 집합은 방정식 $ (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 + 내가 익숙하지 않은 [Pin]에 주어진 또 다른 정의는 이른바 을 사용하여 extensifs ("광범위한 자동 연산")을 자동화합니다. 해당 언어에 대한 더 많은 결과는 [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이라는 것입니다.