Propriété de fermeture CFL
Les langages sans contexte sont closed sous -
- Union
- Concatenation
- Fonctionnement Kleene Star
syndicat
Soit L 1 et L 2 deux langages sans contexte. Alors L 1 ∪ L 2 est également sans contexte.
Exemple
Soit L 1 = {a n b n , n> 0}. La grammaire correspondante G 1 aura P: S1 → aAb | ab
Soit L 2 = {c m d m , m ≥ 0}. La grammaire correspondante G 2 aura P: S2 → cBb | ε
Union de L 1 et L 2 , L = L 1 ∪ L 2 = {a n b n } ∪ {c m d m }
La grammaire G correspondante aura la production supplémentaire S → S1 | S2
Enchaînement
Si L 1 et L 2 sont des langages sans contexte, alors L 1 L 2 est également sans contexte.
Exemple
Union des langues L 1 et L 2 , L = L 1 L 2 = {a n b n c m d m }
La grammaire G correspondante aura la production supplémentaire S → S1 S2
Kleene Star
Si L est un langage sans contexte, alors L * est également sans contexte.
Exemple
Soit L = {a n b n , n ≥ 0}. La grammaire correspondante G aura P: S → aAb | ε
Kleene Star L 1 = {a n b n } *
La grammaire correspondante G 1 aura des productions supplémentaires S1 → SS 1 | ε
Les langages sans contexte sont not closed sous -
Intersection - Si L1 et L2 sont des langages sans contexte, alors L1 ∩ L2 n'est pas nécessairement sans contexte.
Intersection with Regular Language - Si L1 est un langage régulier et L2 est un langage sans contexte, alors L1 ∩ L2 est un langage sans contexte.
Complement - Si L1 est un langage sans contexte, alors L1 'peut ne pas être sans contexte.