Monoide sintáctico

El monoide más pequeño que reconoce un lenguaje formal

En matemáticas y ciencias de la computación , el monoide sintáctico de un lenguaje formal es el monoide más pequeño que reconoce el lenguaje . ${\displaystyle M(L)}$ ${\displaystyle L}$ ${\displaystyle L}$

Cociente sintáctico

El monoide libre de un conjunto 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 la operación de monoide y la cadena vacía como el elemento identidad . Dado un subconjunto de un monoide libre , se pueden definir conjuntos que consisten en inversos formales izquierdos o derechos de elementos en . Estos se denominan cocientes , y se pueden definir cocientes derechos o izquierdos, dependiendo de qué lado se esté concatenando. Por lo tanto, el cociente derecho de por un elemento de es el conjunto ${\displaystyle S}$ ${\displaystyle M}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle m}$ ${\displaystyle M}$

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

Equivalencia sintáctica

El cociente sintáctico ^{[ aclaración necesaria ]} induce una relación de equivalencia en , llamada relación sintáctica , o equivalencia sintáctica (inducida por ). ${\displaystyle M}$ ${\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 correcta es una congruencia izquierda con respecto a la concatenación de cadenas y viceversa; es decir, para todos los . ${\displaystyle s\sim _{S}t\ \Rightarrow \ xs\sim _{S}xt\ }$ ${\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 de un monoide general . Un conjunto disyuntivo es un subconjunto tal que la congruencia sintáctica definida por es la relación de igualdad. ^[3] ${\displaystyle S}$ ${\displaystyle M}$ ${\displaystyle S}$ ${\displaystyle S}$

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

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

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

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

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

Un lenguaje grupal es aquel en el que el monoide sintáctico es un grupo . ^[5]

Teorema de Myhill-Nerode

El teorema de Myhill-Nerode establece: un lenguaje es regular si y sólo si la familia de cocientes es finita o, equivalentemente, la equivalencia sintáctica izquierda tiene un índice finito (lo que significa que se divide en un número finito de clases de equivalencia). ^[6] ${\displaystyle L}$ ${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$ ${\displaystyle {}_{S}{\sim }}$ ${\displaystyle M}$

Este teorema fue demostrado por primera vez por Anil Nerode (Nerode 1958) y por ello algunos autores se refieren a la relación como congruencia de Nerode . ^{[7] [8]} ${\displaystyle {}_{S}{\sim }}$

Prueba

La prueba de la parte "sólo si" es la siguiente. Supongamos que un autómata finito que reconoce lee la entrada , lo que lleva al estado . Si es otra cadena leída por la máquina, que también termina en el mismo estado , entonces claramente se tiene . Por lo tanto, el número de elementos en es como máximo igual al número de estados del autómata y es como máximo el número de estados finales. ${\displaystyle L}$ ${\displaystyle x}$ ${\displaystyle p}$ ${\displaystyle y}$ ${\displaystyle p}$ ${\displaystyle x\setminus L\,=y\setminus L}$ ${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$ ${\displaystyle \{m\setminus L\,\vert \;m\in L\}}$

Para demostrar la parte "si", supongamos que el número de elementos en es finito. Se puede construir un autómata donde es el conjunto de estados, es el conjunto de estados finales, el lenguaje es el estado inicial y la función de transición está dada por . Claramente, este autómata reconoce . ${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$ ${\displaystyle Q=\{m\setminus L\,\vert \;m\in M\}}$ ${\displaystyle F=\{m\setminus L\,\vert \;m\in L\}}$ ${\displaystyle L}$ ${\displaystyle \delta _{y}\colon x\setminus L\to y\setminus (x\setminus L)=(xy)\setminus L}$ ${\displaystyle L}$

Por lo tanto, un lenguaje es reconocible si y solo si el conjunto es finito. Nótese que esta prueba también construye el autómata mínimo. ${\displaystyle L}$ ${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$

Ejemplos

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

Referencias

1. Holcombe (1982) pág. 160
2. Lawson (2004) pág. 210
3. Lawson (2004) pág. 232
4. Straubing (1994) pág. 55
5. Sakarovitch (2009) pág. 342
6. Nerode, Anil (1958), "Transformaciones de autómatas lineales", Actas de la American Mathematical Society , 9 (4): 541–544, doi : 10.1090/S0002-9939-1958-0135681-9 , JSTOR  2033204
7. Brzozowski, Janusz; Szykuła, Marek; Ye, Yuli (2018), "Complejidad sintáctica de los ideales regulares", Teoría de los sistemas informáticos , 62 (5): 1175–1202, doi :10.1007/s00224-017-9803-8, hdl : 10012/12499 , S2CID  2238325
8. Crochemore, Maxime; et al. (2009), "De la congruencia de Nerode a los autómatas de sufijo con desajustes", Theoretical Computer Science , 410 (37): 3471–3480, doi : 10.1016/j.tcs.2009.03.011 , S2CID  14277204
9. Straubing (1994) pág. 54
10. Lawson (2004) págs. 211-212
11. McNaughton, Robert; Papert, Seymour (1971). Autómatas sin contador . Monografía de investigación. Vol. 65. Con un apéndice de William Henneman. MIT Press. p. 48. ISBN 0-262-13076-9.Zbl 0232.94024  .
12. Lawson (2004) pág. 233
13. Marcel-Paul Schützenberger (1965). "Sobre monoides finitos que tienen sólo subgrupos triviales" (PDF) . Información y Computación . 8 (2): 190–194. doi : 10.1016/s0019-9958(65)90108-7 .
14. Straubing (1994) pág. 60

• 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 . Cambridge Studies in Advanced Mathematics. Vol. 1. Cambridge University Press . ISBN. 0-521-60492-3.Zbl 0489.68046  .
• Lawson, Mark V. (2004). Autómatas finitos . Chapman y 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 formal del lenguaje (PDF) . Vol. 1. Springer-Verlag . págs. 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.Zbl1188.68177  .​
• Straubing, Howard (1994). Autómatas finitos, lógica formal y complejidad de circuitos . Progreso en la ciencia informática teórica. Basilea: Birkhäuser. ISBN 3-7643-3719-2.Zbl 0816.68086  .