Đề 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 Σ. | Taïp chí Kinh teá - Kyõ thuaät Kỹ thuật - Công nghệ MỘT SỐ BÀI TOÁN KHÔNG GIẢI ĐƯỢC ĐỐI VỚI NGÔN NGỮ TUYẾN TÍNH Nguyễn Xuân Dũng* TÓM TẮT Việc nghiên cứu về tính khả giải của các bài toán (hoặc các lớp bài toán) đóng một vai trò rất quan trọng không chỉ đối với sự phát triển của Toán học nói riêng mà còn ảnh hưởng lớn đến sự phát triển của khoa học công nghệ nói chung. Trong bài này chúng tôi tiến hành 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à, chúng tôi 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 Σ. LA = { ui1 ui2 .uim aim aim−1 .ai1 | m ≥ 1 và 1 ≤ im ≤ n} LB = { vi1 vi2 .vim aim aim−1 .ai1 | m ≥ 1 và 1 ≤ im ≤ n} Bổ đề 1: Cho L1 và L2 là hai ngôn ngữ tuyến tính bất kỳ trên Σ và cho u, v là hai xâu bất kỳ. Khi đó L1 ∪ L2 và uL1v cũng là các ngôn ngữ tuyến tính trên Σ. Chứng minh: Ta chỉ cần chỉ ra các văn phạm tuyến tính sinh ra các ngôn ngữ đó. a. Không mất tổng quát ta có thể giả thiết rằng L1 = L(G1) và L2 = L(G2) Với G1 = (N1, Σ, P1, S1) và G2 = (N2, Σ, P2, S2) là các văn phạm tuyến tính và N1∩N2=. Ta sẽ xây dựng một văn phạm tuyến tính mới sinh ra ngôn ngữ L1 ∪ L2 như sau: G = (N1 ∪ N2 ∪ {S}, Σ, P1 ∪ P2 ∪ {S → S1 | S2}, S) với S là ký hiệu mới không thuộc tập N1 Định nghĩa 1: Văn phạm tuyến tính là văn phạm mà mỗi luật sinh của nó thuộc một trong các dạng sau: A → uBv, A → uB hoặc A → u với A, B là các ký hiệu không kết thúc và u, v là các xâu ký hiệu kết thúc. Định nghĩa 2: Cho A = u1, u2, , un và B = v1, v2, , vn là hai danh sách của các xâu trong Σ*. Cho K = { a1, a2, , an} là tập n ký hiệu khác nhau không có trong Σ. Ta định nghĩa GA = ({SA}, T, PA, SA) và GB = ({SB}, T, PB, SB) với T = Σ ∪ K và PA, PB được định nghĩa như sau:
