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:
- Operación Unión
- Concatenación
- Cierre Kleene
- operación de inversión
- homomorfismo
- Homomorfismo inverso
- Sustitución
- operación de inicio o prefijo
- Cociente con lenguaje regular
- Operación de ciclo
- Unión con el lenguaje regular
- Intersección con el lenguaje regular
- 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:
- Intersección
- Complementar
- Subconjunto
- Superconjunto
- Unión infinita
- Diferencia, Diferencia simétrica (xor, Nand, nor o cualquier otra operación que se reduzca a intersección y complemento
- Prueba de Membresía: Decidible.
- Prueba de vacío: decidible
- 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:
- DCFL-Determinista (que puede ser reconocido por autómatas pushdown deterministas) lenguaje libre de contexto
- NDCFL: lenguaje libre de contexto no determinista (no puede ser reconocido por DPDA sino por NPDA).
Publicación traducida automáticamente
Artículo escrito por PinakiBanerjee0 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA