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 . ${\ Displaystyle M (L)}$ ${\ Displaystyle L}$ ${\ Displaystyle 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 , se pueden definir conjuntos que consistan en inversos formales de izquierda o derecha de elementos en . Estos se denominan cocientes y se pueden definir cocientes de derecha o de izquierda, dependiendo de qué lado se esté concatenando. Por lo tanto, el cociente correcto de por un elemento de es el conjunto ${\ Displaystyle S}$ ${\ Displaystyle M}$ ${\ Displaystyle S}$ ${\ Displaystyle S}$ ${\ Displaystyle m}$ ${\ Displaystyle M}$

El cociente sintáctico induce una relación de equivalencia en , llamada relación sintáctica , o equivalencia sintáctica (inducida por ). ${\ Displaystyle M}$ ${\ Displaystyle 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 \}$ ${\ Displaystyle x \ in 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] ${\ 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 que uno tiene ${\ Displaystyle [s] _ {S}}$ ${\ Displaystyle s}$