Varias propiedades de los lenguajes libres de contexto (CFL)

El lenguaje libre de contexto (CFL) es un lenguaje generado por una gramática libre de contexto o gramática de tipo 2 (según la clasificación de Chomsky) y es aceptado por un autómata pushdown. 

Algunas propiedades muy importantes de un lenguaje libre de contexto son: 

Los lenguajes libres de contexto de regularidad son lenguajes PDA no regulares. 

Propiedades de cierre : 
los lenguajes libres de contexto se cierran bajo alguna operación específica, cerrado significa que después de hacer esa operación en un lenguaje libre de contexto, el idioma resultante también será un lenguaje libre de contexto. Algunas de estas operaciones son: 

1. Operación Unión
2. Concatenación
3. Cierre Kleene
4. operación de inversión
5. homomorfismo
6. Homomorfismo inverso
7. Sustitución
8. operación de inicio o prefijo
9. Cociente con lenguaje regular
10. Operación de ciclo
11. Unión con el lenguaje regular
12. Intersección con el lenguaje regular
13. Diferencia con el lenguaje regular

El lenguaje libre de contexto no se cierra bajo alguna operación específica, no cerrado significa que después de hacer esa operación en un lenguaje libre de contexto, el lenguaje resultante ya no sigue siendo un lenguaje libre de contexto. 

Algunas de estas operaciones son: 

1. Intersección
2. Complementar
3. Subconjunto
4. Superconjunto
5. Unión infinita
6. Diferencia, Diferencia simétrica (xor, Nand, nor o cualquier otra operación que se reduzca a intersección y complemento

Propiedades de decisión : 
 

1. Prueba de Membresía: Decidible.
2. Prueba de vacío: decidible
3. Prueba de finitud: Decidible

El resto, las propiedades de decisión son indecidibles en un lenguaje libre de contexto. 

Propiedad determinista: 
El lenguaje libre de contexto puede ser: 
 

1. DCFL-Determinista (que puede ser reconocido por autómatas pushdown deterministas) lenguaje libre de contexto
2. NDCFL: lenguaje libre de contexto no determinista (no puede ser reconocido por DPDA sino por NPDA).