Proprietà di chiusura CFL
Le lingue prive di contesto sono closed sotto -
- Union
- Concatenation
- Operazione Kleene Star
Unione
Siano L 1 e L 2 due linguaggi privi di contesto. Allora L 1 ∪ L 2 è anch'esso libero dal contesto.
Esempio
Sia L 1 = {a n b n , n> 0}. La grammatica corrispondente G 1 avrà P: S1 → aAb | ab
Sia L 2 = {c m d m , m ≥ 0}. La grammatica corrispondente G 2 avrà P: S2 → cBb | ε
Unione di L 1 e L 2 , L = L 1 ∪ L 2 = {a n b n } ∪ {c m d m }
La grammatica corrispondente G avrà la produzione aggiuntiva S → S1 | S2
Concatenazione
Se L 1 e L 2 sono linguaggi privi di contesto, anche L 1 L 2 è privo di contesto.
Esempio
Unione delle lingue L 1 e L 2 , L = L 1 L 2 = {a n b n c m d m }
La grammatica corrispondente G avrà la produzione aggiuntiva S → S1 S2
Kleene Star
Se L è un linguaggio libero dal contesto, anche L * è libero dal contesto.
Esempio
Sia L = {a n b n , n ≥ 0}. La grammatica corrispondente G avrà P: S → aAb | ε
Kleene Star L 1 = {a n b n } *
La grammatica corrispondente G 1 avrà produzioni aggiuntive S1 → SS 1 | ε
Le lingue prive di contesto sono not closed sotto -
Intersection - Se L1 e L2 sono linguaggi privi di contesto, allora L1 ∩ L2 non è necessariamente privo di contesto.
Intersection with Regular Language - Se L1 è una lingua normale e L2 è una lingua libera dal contesto, allora L1 ∩ L2 è una lingua libera dal contesto.
Complement - Se L1 è un linguaggio libero dal contesto, allora L1 'potrebbe non essere libero dal contesto.