En matemáticas e informática , el cociente correcto (o simplemente cociente ) de un idioma con respecto al lenguaje es el lenguaje que consta de cadenas w tal que wx está enpara un poco de cuerda x en. [1] Formalmente:
En otras palabras, tomamos todas las cuerdas en que tienen un sufijo en y elimine este sufijo.
Del mismo modo, el cociente izquierdo de con respecto a es el lenguaje que consta de cadenas w tal que xw está enpara un poco de cuerda x en. Formalmente:
En otras palabras, tomamos todas las cuerdas en que tienen un prefijo en y elimine este prefijo.
Tenga en cuenta que los operandos de están en orden inverso: el primer operando es y es segundo.
Ejemplo
Considerar
Ahora, si insertamos un divisor en un elemento de , la parte de la derecha está en solo si el divisor se coloca adyacente a a b (en cuyo caso i ≤ n y j = n ) o adyacente a a c (en cuyo caso i = 0 y j ≤ n ). La parte de la izquierda, por lo tanto, será o ; y Se puede escribir como
Propiedades
Algunas propiedades de cierre comunes de la operación de cociente incluyen:
- El cociente de un idioma regular con cualquier otro idioma es regular.
- El cociente de un lenguaje libre de contexto con un lenguaje regular es libre de contexto.
- El cociente de dos lenguajes libres de contexto puede ser cualquier lenguaje enumerable de forma recursiva .
- El cociente de dos lenguajes enumerables recursivamente es enumerable recursivamente.
Estas propiedades de cierre son válidas para los cocientes izquierdo y derecho.
Ver también
Referencias
- ^ Linz, Peter (2011). Introducción a los lenguajes formales y los autómatas . Editores Jones & Bartlett. págs. 104-108. ISBN 9781449615529. Consultado el 7 de julio de 2014 .