Monoide sintáctico

En matemáticas e informática , el monoide sintáctico${\displaystyle M(L)}$de un lenguaje formal${\displaystyle L}$es el monoide mínimo que reconoce el lenguaje${\displaystyle L}$Según el teorema de Myhill-Nerode , el monoide sintáctico es único salvo isomorfismo único.

Un alfabeto es un conjunto finito .

El monoide libre en un alfabeto dado es el monoide cuyos elementos son todas las cadenas de cero o más elementos de ese conjunto, con la concatenación de cadenas como operación de monoide y la cadena vacía como elemento identidad .

Dado un subconjunto${\displaystyle S}$de un monoide libre${\displaystyle M}$, se pueden definir conjuntos que consisten en inversos izquierdos o derechos formales de elementos en${\displaystyle S}$Estos se denominan cocientes , y se pueden definir cocientes derechos o izquierdos, dependiendo de qué lado se esté concatenando. Así, el cociente derecho de${\displaystyle S}$por un elemento${\displaystyle m}$de${\displaystyle M}$es el conjunto

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

De manera similar, el cociente izquierdo es

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

El cociente sintáctico induce una relación de equivalencia en${\displaystyle M}$, llamada relación sintáctica o equivalencia sintáctica (inducida por${\displaystyle S}$).

La equivalencia sintáctica correcta es la relación de equivalencia

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

De manera similar, la equivalencia sintáctica izquierda es

${\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)}$.

Obsérvese que la equivalencia sintáctica derecha es una congruencia izquierda con respecto a la concatenación de cadenas y viceversa; es decir,${\displaystyle s\sim _{S}t\ \Rightarrow \ xs\sim _{S}xt\ }$a pesar de${\displaystyle x\in M}$.

La congruencia sintáctica o congruencia de Myhill ^{[ 1 ]} se define como ^{[ 2 ]}

${\displaystyle s\equiv _{S}t\ \Leftrightarrow \ (\forall x,y\in M\colon \ xsy\in S\Leftrightarrow xty\in S)}$.

La definición se extiende a una congruencia definida por un subconjunto${\displaystyle S}$de un monoide general${\displaystyle M}$Un conjunto disyuntivo es un subconjunto${\displaystyle S}$de tal manera que la congruencia sintáctica definida por${\displaystyle S}$es la relación de igualdad. ^{[ 3 ]}

Permítanos llamar${\displaystyle [s]_{S}}$la clase de equivalencia de${\displaystyle s}$para la congruencia sintáctica. La congruencia sintáctica es compatible con la concatenación en el monoide, en el sentido de que se tiene

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

a pesar de${\displaystyle s,t\in M}$Por lo tanto, el cociente sintáctico es un morfismo monoide e induce un monoide cociente.

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

Este monoide${\displaystyle M(S)}$se denomina monoide sintáctico de${\displaystyle S}$. Se puede demostrar que es el monoide más pequeño que reconoce${\displaystyle S}$; eso es,${\displaystyle M(S)}$reconoce${\displaystyle S}$y para cada monoide${\displaystyle N}$reconocer${\displaystyle S}$,${\displaystyle M(S)}$es un cociente de un submonoide de${\displaystyle N}$. El monoide sintáctico de${\displaystyle S}$es también el monoide de transición del autómata mínimo de${\displaystyle S}$. ^{[ 1 ] [ 2 ] [ 4 ]}

Un lenguaje de grupo es aquel cuyo monoide sintáctico es un grupo . ^{[ 5 ]}

• Dejar${\displaystyle L}$ser el idioma sobre${\displaystyle A=\{a,b\}}$de palabras de longitud par. La congruencia sintáctica tiene dos clases,${\displaystyle L}$sí mismo y${\displaystyle L_{1}}$, las palabras de longitud impar. El monoide sintáctico es el grupo de orden 2 en${\displaystyle \{L,L_{1}\}}$. ^{[ 6 ]}
• Para el idioma${\displaystyle (ab+ba)^{*}}$, el autómata mínimo tiene 4 estados y el monoide sintáctico tiene 15 elementos. ^{[ 7 ]}
• El monoide bicíclico es el monoide sintáctico del lenguaje de Dyck (el lenguaje de conjuntos equilibrados de paréntesis).
• El monoide libre en${\displaystyle A}$(dónde${\displaystyle \left|A\right|>1}$) es el monoide sintáctico del lenguaje${\displaystyle \{ww^{R}\mid w\in A^{*}\}}$, dónde${\displaystyle w^{R}}$es la inversión de la palabra${\displaystyle w}$. (Para${\displaystyle \left|A\right|=1}$(Se puede utilizar el lenguaje de las potencias cuadradas de la letra).
• Todo monoide finito no trivial es homomorfo al monoide sintáctico de algún lenguaje no trivial, ^{[ 8 ]} pero no todo monoide finito es isomorfo a un monoide sintáctico. ^{[ 9 ]}
• Todo grupo finito es isomorfo al monoide sintáctico de algún lenguaje regular. ^{[ 8 ]}
• El idioma sobre${\displaystyle \{a,b\}}$en el que el número de ocurrencias de${\displaystyle a}$y${\displaystyle b}$son congruentes módulo${\displaystyle 2^{n}}$es un lenguaje de grupo con monoide sintáctico${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$. ^{[ 5 ]}
• Los monoides de traza son ejemplos de monoides sintácticos.
• Marcel-Paul Schützenberger ^{[ 10 ]} caracterizó los lenguajes sin estrella como aquellos con monoides sintácticos aperiódicos finitos . ^{[ 11 ]}

• Anderson, James A. (2006). Teoría de autómatas con aplicaciones modernas . Con contribuciones de Tom Head. Cambridge: Cambridge University Press . ISBN 0-521-61324-8. Zbl 1127.68049 . 
• Holcombe, WML (1982). Teoría de autómatas algebraicos . Estudios de Cambridge en Matemáticas Avanzadas. Vol.  1. Cambridge University Press . ISBN 0-521-60492-3. Zbl 0489.68046 . 
• Lawson, Mark V. (2004). Autómatas finitos . Chapman and Hall/CRC. ISBN 1-58488-255-7. Zbl 1086.68074 . 
• Pin, Jean-Éric (1997). "10. Semigrupos sintácticos". En Rozenberg, G.; Salomaa, A. (eds.). Manual de teoría del lenguaje formal (PDF) . Vol.  1. Springer-Verlag . pp. 679–746 . Zbl 0866.68057 .  
• Sakarovitch, Jacques (2009). Elementos de la teoría de autómatas . Traducido del francés por Reuben Thomas. Cambridge University Press . ISBN 978-0-521-84425-3. Zbl 1188.68177 . 
• Straubing, Howard (1994). Autómatas finitos, lógica formal y complejidad de circuitos . Avances en informática teórica. Basilea: Birkhäuser. ISBN 3-7643-3719-2. Zbl 0816.68086 .