¿Qué significa decir que un idioma está "efectivamente cerrado" bajo una operación?

9

He estado leyendo algunos documentos de teoría del lenguaje formal y me he encontrado con un término que no entiendo.

El documento a menudo se referirá a un conjunto que está "efectivamente cerrado bajo intersección" u otras operaciones. ¿Qué significa "efectivamente" aquí? ¿Cómo difiere esto del cierre normal?

Como referencia, el documento en el que estoy viendo estos es:

M. Daley y yo. McQuillan. Modelado formal de la compresión del gen viral. Revista Internacional de Fundaciones de Ciencias de la Computación, 16 (3): 453–469, 2005.

jmite
fuente

Respuestas:

14

"Efectivamente cerrado" significa que la familia está cerrada bajo la operación, y que el cierre se puede calcular dando un autómata / gramática (si los idiomas originales también se dan en una representación tan efectiva). Por ejemplo, dado un autómata de estado finito, podemos encontrar un autómata para el complemento.

Entonces es una pregunta natural, si hay ejemplos de propiedades de cierre que no son efectivas. Sé uno ahora. Para un lenguaje regular y cualquier idioma el cociente es nuevamente regular. No hay forma efectiva de construir un FSA para ese cociente si es, por ejemplo, recursivamente enumable.RLR/LL

Hendrik Jan
fuente