통사성 단면체

수학과 컴퓨터 과학에서, 정식 $언어{\displaystyle }$ L$${\$displaystyle L$$}$의 구문론적 모노이드 $M{\displaystyle (L}$) {\$displaystyle M(L)}$은 $언어{\displaystyle }$ L$${\$displaystyle L}$을(를) 인식하는 가장 작은 모노이드다$.$

통사적 지수

주어진 집합의 자유 모노이드는 그 집합으로부터 0 이상의 원소의 모든 문자열인 모노이드로, 모노이드 연산으로는 문자열 결합, ID 요소로는 빈 문자열이 있다.$자유{\displaystyle }$ 모노이드 $M{\displaystyle }$ ${\displaystyle M}$의 부분 $집합{\displaystyle }$ S ${\displaystyle$ S$}$을(를$)$ 제공하면, S$${\$displaystyle S}$의 원소 반대편에 있는 공식 왼쪽 또는 오른쪽으로 구성된 집합을 정의할 수 있다$.$ 이러한 값을 인용이라고 하며, 어느 쪽이 연결되는지 여부에 따라 오른쪽 또는 왼쪽 인용구를 정의할 수 있다.따라서, $M{\displaystyle }${\$displaystyle M}$의 $요소{\displaystyle }$ m$${\$displaystyle$m}에$$ $의한{\displaystyle }$ S$${\$displaystyle$S}의 오른쪽 몫은 집합이다$$.

$\\displaystyle S\ /\m=\{u\in M\;\vert \;um\in S\}.}$

마찬가지로 왼쪽 지수도

$\displaystyle m\setminus S=\{u\in M\;\vert \;mu\in S\}.}$

통사적 등가성

구문적 인수는 구문적 관계 또는 구문적 동등성($S{\displaystyle }$ ${\displaystyle S}$에 의해 유도됨)이라고 하는$$$M{\displaystyle }$ ${\displaystyle M}$에 동등성 관계를 유도한다.

오른쪽 구문적 등가성은 등가관계다.

${\displaystyle s\sim _{S}t\ \Leftrightarrow \ S\,/\,s\;=\;S\,/\,t\ \Leftrightarrow \ (\forall x\in M\colon \ xs\in S\Leftrightarrow xt\in S)}$.

마찬가지로 왼쪽 구문적 등가성은 다음과 같다.

${\displaystyle s\;{}_{S}{\sim }\;t\ \Leftrightarrow \ s\setminus S\;=\;t\setminus S\ \Leftrightarrow \ (\forall y\in M\colon \ sy\in S\Leftrightarrow ty\in S)}$.

우측 통사적 등가성이 문자열 연결에 관한 왼쪽 합치물이며, 그 반대도 마찬가지라는 점을 주의하십시오. 즉, $모든{\displaystyle }$ x$m$에 $대한{\displaystyle {}_{}}$s ~ ${\displaystyle S_{}}$ ${\displaystyle {}_{}\text{x}}$ $s$ ~ ${\displaystyle {}_{}}$ ${\displaystyle x}$ t ~ ${\displaystyle S_{}}$ x t$\\S}t\\\Rightarrow$\ $xs\s\sim$ $_{S}xt\$$\}\}\}\}.$

통사적 합치 또는 마이힐 합치성은^[1] 다음과^[2] 같이 정의된다.

${\displaystyle s}$ ${\displaystyle {}_{}}$ ${\displaystyle S_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \text{⇔}}$ (${\displaystyle \mathrm{\forall }}$ ${\displaystyle x}$, ${\displaystyle y}$ ${\displaystyle \in }$ ${\displaystyle m}$: ${\displaystyle x}$ ${\displaystyle \in }$ ${\displaystyle S}$ ${\displaystyle \iff }$ x t x ${\displaystyle t}$ s x ${\displaystyle xx}$ x${\displaystyle \_}$ _ _ _ _ _ _ _$_ _$\\$pretrightarrow$ \ \ $\xty\in$ S$)\}.$

이 정의는 일반 단일형 $M{\displaystyle }$ ${\displaystyle M}$의 $부분집합{\displaystyle }$ S ${\displaystyle S}$에 의해 정의되는 조합으로 확장된다$.$ 이격집합 집합은 $부분집합{\displaystyle }$ $S{\displaystyle }$ ${\displaystyle S}$^[3]에 의해 정의된 구문합합합합합합성이 평등 관계인$$ 경우.

[${\displaystyle {}_{}}$ ${\displaystyle S}$ ${\$라고 부르자.${S}$ 구문합성에 대한$$ $s{\displaystyle }$ ${\displaystyle s}$의 동등성 클래스.통사적 결합은 단면체의 결합과 호환된다. 단면체의 결합은 단면체의 결합과 호환된다.

$[\displaystyle [s]_{S}[t]_{S}=[st]_{S}$

모든${\displaystyle }s$에 ${\displaystyle \mathrm{대해}}$, t ${\displaystyle \in }$ M$${\$displaystyle s,t\in$ M$\}.$ 따라서, 구문적 인수는 단모형 형태론이며, 인지도 단모형을 유도한다.

${\displaystyle M}$( ${\displaystyle S}$)${\displaystyle }$= ${\displaystyle M}$ /${\displaystyle \equiv {}_{}}$ ${\displaystyle S_{}}$ ${\$

This monoid ${\displaystyle M(S)}$ is called the syntactic monoid of ${\displaystyle S}$. It can be shown that it is the smallest monoid that recognizes ${\displaystyle S}$; that is, ${\displaystyle M(S)}$ recognizes ${\displaystyle S}$, and for every monoid ${\displaystyle N}$ recognizing${\displaystyle S}$ ${\displaystyle$ S$\},$ $M{\displaystyle (S)}$ ${\displaystyle M(S)}$은(는) $(\displaystyle N}$의 서브모노이드의 $몫$이다$.$$$S {\$displaystyle$ S$}$의 통사적 모노이드도 $S{\displaystyle }$ ${\displaystyty S}$의 최소 자동화의 전환 단면이다$.$^[1][2][4]

그룹 언어는 통사적 모노이드(monoid)가 그룹인 언어 중 하나이다.^[5]

마이힐-네로드 정리

The Myhill–Nerode theorem states: a language ${\displaystyle L}$ is regular if and only if the family of quotients ${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$ is finite, or equivalently, the left syntactic equivalence ${\displaystyle {}_{S}{\sim }}$ has finite index (meaning it partitions $$${\displaystyle M}$ $[\displaystyle M}$을(를) 정밀하게 많은 동등성 클래스로).^[6]

이 정리는 Anil Nerode (Nerode 1958)에 의해 처음 증명되었으며, 관계 ${\displaystyle {}_{}}$~ ${\$을(^[7][8]를) 일부 저자에 의해 Nerode 일치라고 한다.

증명

" only if" 부분의 증거는 다음과 같다.$L{\displaystyle }$ ${\displaystyle L}$을(를) 인식하는 유한 자동화가 $입력{\displaystyle }$ x ${\displaystyle x}$을(를) 읽어서 $상태$ p ${\displaystyle p}$을(를) 발생시킨다고 가정하십시오$.$ $y{\displaystyle }$ ${\displaystyty$ y$}$도 동일한 $상태{\displaystyle }$ p$${\$displaystyp$에서 종료되는 다른 문자열인$$ 경우, 하나는 ${\displaystyle x}$l${\displaystyle }$L $=$를 ${\displaystyle \mathrm{명백히}}$ $가지고$ 있음$yle x\setminus L\,=y\setminus L}$. Thus, the number of elements in ${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$ is at most equal to the number of states of the automaton and ${\displaystyle \{m\setminus L\,\vert \;m\in L\}}$ is at most the number of final states.

"if" 부분에 대한 증명의 경우$,{\displaystyle }$ {${\displaystyle m}$ ${\displaystyle \setminus }$ L ${\displaystyle m}$ ${\displaystyle \in }$ ${\displaystyle M}$ ${\displaystyle \}}$ ${\displaystyle \{m\setminus$ L$\,\vert \;m\in$ M$\}$의 요소 수가 유한하다고$$ 가정한다.One can then construct an automaton where ${\displaystyle Q=\{m\setminus L\,\vert \;m\in M\}}$ is the set of states, ${\displaystyle F=\{m\setminus L\,\vert \;m\in L\}}$ is the set of final states, the language ${\displaystyle L}$ is the initial state, and the transition functionis given by ${\displaystyle y\setminus (x\setminus L)=(xy)\setminus L}$. Clearly, this automaton recognizes ${\displaystyle L}$. Thus, a language ${\displaystyle L}$ is recognizable if and only if the set ${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$ is finite.이 증거는 또한 최소한의 자동화를 구축한다는 점에 유의하십시오.

예

• $L{\displaystyle }$ ${\displaystyle L}$을(를) $A{\displaystyle }$=${\displaystyle }${ ${\displaystyle a,}$ ${\displaystyle b\}}$ ${\displaystyle A=\{a,b\}}$을(를) 넘는 언어로 한다.통사적 합칭은 $L{\displaystyle }$ ${\displaystyle L}$ 그$$ 자체와 $L{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}의 두 개의 등급이 있는데$,$ 이는 홀수 길이의 단어다.통사적 ${\displaystyle {}_{}}$는 { ${\displaystyle {L\mathrm{}}_{}}$ , L 1 ${\displaystyle {}_{}}$ $displaystyle \{L,L_{1}\}}$에 있는 순서 2의 그룹이다$.$^[9]
• 자전거 모노이드(byclic monoid)는 Dyck 언어(균형화된 괄호 집합의 언어)의 통사적 모노이드다.
• The free monoid on ${\displaystyle A}$ (where ${\displaystyle \left A\right >1}$) is the syntactic monoid of the language ${\displaystyle \{ww^{R}\mid w\in A^{*}\}}$, where ${\displaystyle w^{R}}$ is the reversal of the word ${\displaystyle w}$.
• 모든 유한 모노이드들은 어떤 비삼각적 언어의 통사적 단모이드에 동형성이지만^{[clarification needed]},^[10] 모든 유한 모노이드들이 통사적 단모이드에 이형성이 있는 것은 아니다.^[11]
• 모든 유한 집단은 어떤 비삼각적 언어의 통사적 단모형에 이형적이다.^[10]
• The language over ${\displaystyle \{a,b\}}$ in which the number of occurrences of ${\displaystyle a}$ and ${\displaystyle b}$ are congruent modulo ${\displaystyle 2^{n}}$ is a group language with syntactic monoid ${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$.^[5]
• 미량 모노이드들은 통사적 모노이드의 예들이다.
• 마르셀폴 슈트젠베르거는^[12] 항성 없는 언어가 유한한 주기적 구문 모노이드로 특징지어졌다.^[13]

참조

• Anderson, James A. (2006). Automata theory with modern applications. With contributions by Tom Head. Cambridge: Cambridge University Press. ISBN 0-521-61324-8. Zbl 1127.68049.
• Holcombe, W.M.L. (1982). Algebraic automata theory. Cambridge Studies in Advanced Mathematics. Vol. 1. Cambridge University Press. ISBN 0-521-60492-3. Zbl 0489.68046.
• Lawson, Mark V. (2004). Finite automata. Chapman and Hall/CRC. ISBN 1-58488-255-7. Zbl 1086.68074.
• Pin, Jean-Éric (1997). "10. Syntactic semigroups". In Rozenberg, G.; Salomaa, A. (eds.). Handbook of Formal Language Theory (PDF). Vol. 1. Springer-Verlag. pp. 679–746. Zbl 0866.68057.
• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
• Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel: Birkhäuser. ISBN 3-7643-3719-2. Zbl 0816.68086.