Cociente de un lenguaje formal

En matemáticas y ciencias de la computación , el cociente derecho (o simplemente cociente ) de un lenguaje con respecto al lenguaje es el lenguaje que consiste en cadenas w tales que wx es en para alguna cadena x en . ^[1] Formalmente: $Estilo de visualización L_{1}$$Estilo de visualización L_{2}$ $Estilo de visualización L_{1}$$Estilo de visualización L_{2}$$${\displaystyle L_{1}/L_{2}=\{w\en \Sigma ^{*}\mid \exists x\en L_{2}\colon \ wx\en L_{1}\}}$$

En otras palabras, para todas las cadenas que tienen un sufijo en , se elimina el sufijo. $Estilo de visualización L_{1}$$Estilo de visualización L_{2}$

De manera similar, el cociente izquierdo de con respecto a es el lenguaje que consiste en cadenas w tales que xw está en para alguna cadena x en . Formalmente: $Estilo de visualización L_{1}$$Estilo de visualización L_{2}$$Estilo de visualización L_{1}$$Estilo de visualización L_{2}$$${\displaystyle L_{2}\barra invertida L_{1}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\colon \ xw\in L_{1}\}}$$

En otras palabras, tomamos todas las cadenas que tienen un prefijo en y eliminamos este prefijo. $Estilo de visualización L_{1}$$Estilo de visualización L_{2}$

Tenga en cuenta que los operandos de están en orden inverso: el primer operando es y es el segundo. ${\displaystyle \barra invertida}$$Estilo de visualización L_{2}$$Estilo de visualización L_{1}$

Considere y $${\displaystyle L_{1}=\{a^{n}b^{n}c^{n}\mid n\geq 0\}}$$$${\displaystyle L_{2}=\{b^{i}c^{j}\mid i,j\geq 0\}.}$$

Ahora bien, si insertamos un divisor en un elemento de , la parte de la derecha está en sólo si el divisor se coloca adyacente a un b (en cuyo caso i  ≤  n y j  =  n ) o adyacente a un c (en cuyo caso i  = 0 y j  ≤  n ). La parte de la izquierda, por lo tanto, será o ; y puede escribirse como $Estilo de visualización L_{1}$$Estilo de visualización L_{2}$$Estilo de visualización a^{n}b^{ni}}$${\displaystyle a^{n}b^{n}c^{nj}}$$Estilo de visualización L_{1}/L_{2}}$$${\displaystyle \{\ a^{p}b^{q}c^{r}\ \mid \ p=q\geq r\ \ {\text{o}}\ \ (p\geq q{\text{ y }}r=0)\ \}.}$$

Algunas propiedades de cierre comunes de la operación cociente incluyen:

• El cociente de un lenguaje regular con cualquier otro lenguaje es regular.
• El cociente de un lenguaje libre de contexto con un lenguaje regular es libre de contexto.
• El cociente de dos idiomas libres de contexto puede ser cualquier idioma enumerable recursivamente .
• El cociente de dos lenguajes recursivamente enumerables es recursivamente enumerable.

Estas propiedades de cierre son válidas tanto para los cocientes izquierdo como derecho.

• Derivado de Brzozowski