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: ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ $${\displaystyle L_{1}/L_{2}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\colon \ wx\in L_{1}\}}$$

En otras palabras, para todas las cadenas que tienen un sufijo en , se elimina el sufijo. ${\displaystyle L_{1}}$ ${\displaystyle 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: ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ $${\displaystyle L_{2}\backslash 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. ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$

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

Ejemplo

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 ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle a^{n}b^{n-i}}$ ${\displaystyle a^{n}b^{n}c^{n-j}}$ ${\displaystyle L_{1}/L_{2}}$ $${\displaystyle \{\ a^{p}b^{q}c^{r}\ \mid \ p=q\geq r\ \ {\text{or}}\ \ (p\geq q{\text{ and }}r=0)\ \}.}$$

Propiedades

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.

Véase también

• Derivado de Brzozowski

Referencias

1. Linz, Peter (2011). Introducción a los lenguajes formales y autómatas. Jones & Bartlett Publishers. pp. 104–108. ISBN 9781449615529. Recuperado el 7 de julio de 2014 .