Tài sản đóng CFL
Ngôn ngữ không có ngữ cảnh là closed dưới -
- Union
- Concatenation
- Hoạt động của Kleene Star
liên hiệp
Cho L 1 và L 2 là hai ngôn ngữ không có ngữ cảnh. Khi đó L 1 ∪ L 2 cũng không có ngữ cảnh.
Thí dụ
Cho L 1 = {a n b n , n> 0}. Văn phạm tương ứng G 1 sẽ có P: S1 → aAb | ab
Cho L 2 = {c m d m , m ≥ 0}. Văn phạm G 2 tương ứng sẽ có P: S2 → cBb | ε
Liên hiệp của L 1 và L 2 , L = L 1 ∪ L 2 = {a n b n } ∪ {c m d m }
Văn phạm tương ứng G sẽ có thêm sản phẩm S → S1 | S2
Kết nối
Nếu L 1 và L 2 là ngôn ngữ không có ngữ cảnh thì L 1 L 2 cũng không có ngữ cảnh.
Thí dụ
Liên hiệp các ngôn ngữ L 1 và L 2 , L = L 1 L 2 = {a n b n c m d m }
Văn phạm tương ứng G sẽ có sản lượng bổ sung S → S1 S2
Kleene Star
Nếu L là ngôn ngữ không có ngữ cảnh thì L * cũng không có ngữ cảnh.
Thí dụ
Cho L = {a n b n , n ≥ 0}. Văn phạm G tương ứng sẽ có P: S → aAb | ε
Kleene Star L 1 = {a n b n } *
Ngữ pháp tương ứng G 1 sẽ có thêm các sản phẩm S1 → SS 1 | ε
Ngôn ngữ không có ngữ cảnh là not closed dưới -
Intersection - Nếu L1 và L2 là ngôn ngữ không có ngữ cảnh, thì L1 ∩ L2 không nhất thiết là ngôn ngữ không có ngữ cảnh.
Intersection with Regular Language - Nếu L1 là ngôn ngữ thông thường và L2 là ngôn ngữ không có ngữ cảnh thì L1 ∩ L2 là ngôn ngữ không có ngữ cảnh.
Complement - Nếu L1 là ngôn ngữ không có ngữ cảnh thì L1 'có thể không có ngữ cảnh.