monoide sintáctico

---

En matemáticas e informática , el monoide sintáctico de un lenguaje formal es el monoide más pequeño que reconoce el lenguaje .${\ estilo de visualización M (L)}$ ${\ estilo de visualización L}$${\ estilo de visualización L}$

El monoide libre en 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 operación monoide y la cadena vacía como elemento de identidad . Dado un subconjunto de un monoide libre , uno puede definir conjuntos que consisten en inversas formales izquierda o derecha de elementos en . Estos se llaman cocientes , y uno puede definir cocientes a la derecha o a la izquierda, dependiendo de qué lado se esté concatenando. Así, el cociente derecho de por un elemento de es el conjunto${\ estilo de visualización S}$${\ estilo de visualización M}$${\ estilo de visualización S}$${\ estilo de visualización S}$${\ estilo de visualización m}$${\ estilo de visualización M}$

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

Observe que la equivalencia sintáctica derecha es una congruencia izquierda con respecto a la concatenación de cadenas y viceversa; es decir, para todos .${\displaystyle s\sim _{S}t\ \Rightarrow \ xs\sim _{S}xt\ }$${\ estilo de visualización x \ en M}$

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]${\ estilo de visualización S}$${\ estilo de visualización M}$${\ estilo de visualización S}$${\ estilo de visualización 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 que uno tiene${\ estilo de visualización [s] _ {S}}$${\ estilo de visualización}$

---