Właściwość zamknięcia CFL
Języki bezkontekstowe to closed pod -
- Union
- Concatenation
- Operacja Kleene Star
Unia
Niech L 1 i L 2 będą dwoma językami bezkontekstowymi. Wtedy L 1 ∪ L 2 jest również bezkontekstowa.
Przykład
Niech L 1 = {a n b n , n> 0}. Odpowiednia gramatyka G 1 będzie miała P: S1 → aAb | ab
Niech L 2 = {c m d m , m ≥ 0}. Odpowiednia gramatyka G 2 będzie miała P: S2 → cBb | ε
Połączenie L 1 i L 2 , L = L 1 ∪ L 2 = {a n b n } ∪ {c m d m }
Odpowiednia gramatyka G będzie miała dodatkową produkcję S → S1 | S2
Powiązanie
Jeśli L 1 i L 2 są językami bezkontekstowymi, to L 1 L 2 jest również bezkontekstowe.
Przykład
Unia języków L 1 i L 2 , L = L 1 L 2 = {a n b n c m d m }
Odpowiednia gramatyka G będzie miała dodatkową produkcję S → S1 S2
Kleene Star
Jeśli L jest językiem bezkontekstowym, wówczas L * jest również bezkontekstowy.
Przykład
Niech L = {a n b n , n ≥ 0}. Odpowiednia gramatyka G będzie miała P: S → aAb | ε
Kleene Star L 1 = {a n b n } *
Odpowiednia gramatyka G 1 będzie miała dodatkowe produkcje S1 → SS 1 | ε
Języki bezkontekstowe to not closed pod -
Intersection - Jeśli L1 i L2 są językami bezkontekstowymi, to L1 ∩ L2 niekoniecznie są bezkontekstowe.
Intersection with Regular Language - Jeśli L1 jest językiem zwykłym, a L2 jest językiem bezkontekstowym, wówczas L1 ∩ L2 jest językiem bezkontekstowym.
Complement - Jeśli L1 jest językiem bezkontekstowym, to L1 'może nie być bezkontekstowy.