Propriedade de Fechamento CFL

Linguagens livres de contexto são closed sob -

  • Union
  • Concatenation
  • Operação Kleene Star

União

Sejam L 1 e L 2 duas linguagens livres de contexto. Então L 1 ∪ L 2 também é livre de contexto.

Exemplo

Seja L 1 = {a n b n , n> 0}. A gramática correspondente G 1 terá P: S1 → aAb | ab

Seja L 2 = {c m d m , m ≥ 0}. A gramática correspondente G 2 terá P: S2 → cBb | ε

União de L 1 e L 2 , L = L 1 ∪ L 2 = {a n b n } ∪ {c m d m }

A gramática G correspondente terá a produção adicional S → S1 | S2

Concatenação

Se L 1 e L 2 são linguagens livres de contexto, então L 1 L 2 também é livre de contexto.

Exemplo

União das línguas L 1 e L 2 , L = L 1 L 2 = {a n b n c m d m }

A gramática G correspondente terá a produção adicional S → S1 S2

Kleene Star

Se L é uma linguagem livre de contexto, então L * também é livre de contexto.

Exemplo

Seja L = {a n b n , n ≥ 0}. A gramática G correspondente terá P: S → aAb | ε

Kleene Star L 1 = {a n b n } *

A gramática correspondente G 1 terá produções adicionais S1 → SS 1 | ε

Linguagens livres de contexto são not closed sob -

  • Intersection - Se L1 e L2 são linguagens livres de contexto, então L1 ∩ L2 não é necessariamente livre de contexto.

  • Intersection with Regular Language - Se L1 é uma linguagem regular e L2 é uma linguagem livre de contexto, então L1 ∩ L2 é uma linguagem livre de contexto.

  • Complement - Se L1 for uma linguagem livre de contexto, então L1 'pode não ser livre de contexto.