Một số bài toán không giải được đối với ngôn ngữ tuyến tính

Đề tài được tiến hành nhằm nghiên cứu về tính khả giải của một số bài toán trong lý thuyết ngôn ngữ hình thức. Cụ thể là, tác giả sẽ chứng minh các bài toán sau đây là không giải được đối với ngôn ngữ tuyến tính: Bài toán tương đương của hai ngôn ngữ tuyến tính bất kỳ, bài toán đồng nhất của một ngôn ngữ tuyến tính với một ngôn ngữ chính quy, bài toán liệu có hay không L = Σ*, đối với ngôn ngữ tuyến tính L cho trước trên bảng chữ cái Σ.