Operación cociente en autómatas

Descripción general:
De acuerdo con los aspectos teóricos de Automata , una operación de cociente se puede definir como la técnica que reconoce un superconjunto de la automatización dada, particularmente para la string dada de lenguaje formal (Un lenguaje formal es un conjunto de strings de símbolos extraídos de un finito alfabeto (puede tener reglas basadas en expresiones regulares o una gramática libre de contexto que genera/acepta el lenguaje). Por lo tanto, se puede obtener un autómata cociente a partir de una determinada automatización finita no determinista uniendo algunos de sus estados.

Propiedades de cierre de la operación de cociente:
algunas propiedades de cierre comunes e importantes de la operación de cociente en la teoría de los autómatas son las siguientes.

• La operación cociente de una lengua regular con cualquier otra lengua es regular.
• La operación cociente de un lenguaje libre de contexto con un lenguaje regular es libre de contexto.
• La operación cociente de dos lenguajes recursivamente enumerables es recursivamente enumerable.
• La operación cociente dos lenguajes libres de contexto puede ser cualquier lenguaje recursivamente enumerable.

Tipos de operación de cociente:
La operación de cociente se puede dividir en dos partes de la siguiente manera.

Tipo-1:
cociente derecho (corte a la derecha) –

 L1/L2 = { a | ab ∈  L1 for some b ∈  L2 }                                

Aquí, ∑ (a, b). La expresión dada establece la operación de cociente correcto del lenguaje L1 con respecto a L2, que es un lenguaje que consta de strings ‘b’ tales que ‘ab’ está en L1 para alguna string ‘b’ en L2.

Ejemplo 1 :

Let   L1 = { hooray, sunray, defray, ray},  
      L2 = { ray}
so,   L1/L2 = { hoo , sun, def,  ∈ } 

Ejemplo-2:

Let   L1 = {∈, a, ab, aba, abab, ... },  
      L2 = { b, bb, bbb, bbbb, ... }
so,   L1/L2 = { a, aba, ababa, ... } 

Tipo-2:
cociente izquierdo (corte a la izquierda) –

L1/L2 = { b | ab ∈  L1 for some a ∈  L2 }                                

Aquí, ∑ (a, b). La expresión dada establece la operación de cociente izquierdo del lenguaje L1 con respecto a L2, que es un lenguaje que consta de strings ‘a’ tales que ‘ab’ está en L1 para alguna string ‘a’ en L2.

Ejemplo 1 :

Let   L1 = { match, matter, mat, matzoth },  
      L2 = { mat}
so,   L1/L2 = { tch , ter, ∈ , zoth } 

Ejemplo-2:

Let   L1 = { 10, 100, 1010, 101110},  
      L2 = { 10}
so,   L1/L2 = { ∈ , 0, 10, 1110 }