Propiedad de cierre de CFL
Los lenguajes libres de contexto son closed bajo -
- Union
- Concatenation
- Operación Kleene Star
Unión
Sean L 1 y L 2 dos lenguajes libres de contexto. Entonces L 1 ∪ L 2 también está libre de contexto.
Ejemplo
Sea L 1 = {a n b n , n> 0}. La gramática correspondiente G 1 tendrá P: S1 → aAb | ab
Sea L 2 = {c m d m , m ≥ 0}. La gramática correspondiente G 2 tendrá P: S2 → cBb | ε
Unión de L 1 y L 2 , L = L 1 ∪ L 2 = {a n b n } ∪ {c m d m }
La gramática correspondiente G tendrá la producción adicional S → S1 | S2
Concatenación
Si L 1 y L 2 son lenguajes libres de contexto, entonces L 1 L 2 también lo está.
Ejemplo
Unión de las lenguas L 1 y L 2 , L = L 1 L 2 = {a n b n c m d m }
La gramática correspondiente G tendrá la producción adicional S → S1 S2
Estrella de Kleene
Si L es un lenguaje sin contexto, entonces L * también lo está.
Ejemplo
Sea L = {a n b n , n ≥ 0}. La gramática correspondiente G tendrá P: S → aAb | ε
Estrella de Kleene L 1 = {a n b n } *
La gramática correspondiente G 1 tendrá producciones adicionales S1 → SS 1 | ε
Los lenguajes libres de contexto son not closed bajo -
Intersection - Si L1 y L2 son lenguajes libres de contexto, entonces L1 ∩ L2 no es necesariamente libre de contexto.
Intersection with Regular Language - Si L1 es un idioma regular y L2 es un idioma sin contexto, entonces L1 ∩ L2 es un idioma sin contexto.
Complement - Si L1 es un lenguaje libre de contexto, entonces L1 'puede no estar libre de contexto.