1. (a) Đúng, vì mọi ngôn ngữ thông thường đều không có ngữ cảnh, mọi ngôn ngữ không có ngữ cảnh đều có thể phân biệt đượcvà mọi ngôn ngữ có thể phân biệt được đều có thể nhận dạng Turing.
Tại sao các ngôn ngữ không có ngữ cảnh lại là yếu tố quyết định?
Một vấn đề không thể quyết định không có thuật toán để xác định câu trả lời cho một đầu vào nhất địnhSự mơ hồ của các ngôn ngữ không có ngữ cảnh: Với một ngôn ngữ không có ngữ cảnh, không có máy Turing nào sẽ luôn dừng lại trong khoảng thời gian hữu hạn và đưa ra câu trả lời liệu ngôn ngữ có mơ hồ hay không.
Liệu tập hợp con của ngôn ngữ không có ngữ cảnh có thể quyết định được không?
2 Câu trả lời. Σlàkhông có ngữ cảnh (thực sự là thường xuyên) và nó có rất nhiều tập con. Nếu L là ngôn ngữ không có ngữ cảnh có kích thước vô hạn, thì có các tập con J của L là có thể quyết định được và một số là không thể quyết định. Ví dụ: tập hợp con trống có thể phân biệt được.
CFL có phải là quyết định không?
CFL: Nó là quyết định cho vấn đề tính không, vấn đề hữu hạn và vấn đề thành viên.
Có bao nhiêu ngôn ngữ không có ngữ cảnh?
(1) Có vô số ngôn ngữ không có ngữ cảnh. Điều này đúng bởi vì mọi mô tả của một ngôn ngữ không có ngữ cảnh đều có độ dài hữu hạn, vì vậy có vô số mô tả như vậy. (2) Số lượng ngôn ngữ không đếm được.
