Luận án Tiến sĩ Công nghệ thông tin: Bài toán kiểm định mã và phân bậc ngôn ngữ theo độ không nhập nhằng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:116

Thêm vào BST

Báo xấu

28
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu của luận án là nghiên cứu những lớp ngôn ngữ gần mã thông qua nghiên cứu về độ không nhập nhằng của ngôn ngữ xem như một yếu tố phản ánh sự “gần nhau” của một ngôn ngữ với một mã, và thiết lập phân bậc ngôn ngữ dựa trên độ không nhập nhằng của chúng. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Công nghệ thông tin: Bài toán kiểm định mã và phân bậc ngôn ngữ theo độ không nhập nhằng

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Nguyễn Đình Hân BÀI TOÁN KIỂM ĐỊNH MÃ VÀ PHÂN BẬC NGÔN NGỮ THEO ĐỘ KHÔNG NHẬP NHẰNG LUẬN ÁN TIẾN SỸ CÔNG NGHỆ THÔNG TIN Hà Nội - 2012
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Nguyễn Đình Hân BÀI TOÁN KIỂM ĐỊNH MÃ VÀ PHÂN BẬC NGÔN NGỮ THEO ĐỘ KHÔNG NHẬP NHẰNG Chuyên ngành: Khoa học máy tính Mã số: 62.48.01.01 LUẬN ÁN TIẾN SỸ CÔNG NGHỆ THÔNG TIN Người hướng dẫn khoa học: 1. GS.TSKH. Đỗ Long Vân 2. PGS.TS. Phan Trung Huy Hà Nội - 2012
LỜI CAM ĐOAN Tôi xin cam đoan các kết quả tôi trình bày trong luận án là hoàn toàn mới, chưa từng được công bố trong bất kỳ một công trình khoa học của ai khác. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa vào luận án. Hà Nội, ngày 16 tháng 8 năm 2012 Nguyễn Đình Hân
LỜI CẢM ƠN Luận án được hoàn thành tại Viện Toán ứng dụng và Tin học, Trường Đại học Bách Khoa Hà Nội, dưới sự hướng dẫn của GS.TSKH. Đỗ Long Vân và PGS.TS. Phan Trung Huy. Tác giả xin gửi lời cảm ơn sâu sắc tới hai thầy, trong suốt thời gian qua đã hướng dẫn, chỉ bảo tận tình để tác giả hoàn thiện được luận án này. Tác giả chân thành cảm ơn các thành viên của Seminar “Toán rời rạc và Tổ hợp”, Viện Toán học về những nhận xét và ý kiến trao đổi rất hữu ích, góp phần nâng cao chất lượng trình bày của luận án. Tác giả trân trọng gửi lời cảm ơn tới Ban lãnh đạo Viện Toán ứng dụng và Tin học, và Viện Đào tạo Sau Đại học, các thầy cô giáo cùng toàn thể các bạn đồng nghiệp tại Trường Đại học Bách Khoa Hà Nội về sự giúp đỡ chân tình, vô tư mà tác giả nhận được trong quá trình thực hiện luận án. Tác giả xin bày tỏ lòng biết ơn đến Ban Giám hiệu Trường Đại học Sư phạm Kỹ thuật Hưng Yên, gia đình, các thầy cô giáo và các bạn đồng nghiệp Khoa Công nghệ Thông tin, Phòng Quản lý Khoa học và Đối ngoại trong thời gian vừa qua đã giúp đỡ, tạo điều kiện thuận lợi và không ngừng ủng hộ tác giả.
MỤC LỤC DANH MỤC BẢNG, HÌNH VẼ 1 MỞ ĐẦU 2 1 CƠ SỞ LÝ THUYẾT MÃ 8 1.1 Nửa nhóm và vị nhóm . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2 Từ và ngôn ngữ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Otomat và ngôn ngữ chính quy . . . . . . . . . . . . . . . . . . . . . . 12 1.3.1 Otomat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.2 Ngôn ngữ chính quy . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Mã của các từ hữu hạn . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.4.1 Mã và các tính chất đại số của mã . . . . . . . . . . . . . . . . 16 1.4.2 Độ trễ giải mã . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.4.3 Tiêu chuẩn kiểm định mã . . . . . . . . . . . . . . . . . . . . . 19 1.5 Mã luân phiên và mã của các từ định biên . . . . . . . . . . . . . . . . 20 1.5.1 Mã luân phiên . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.5.2 Mã của các từ định biên . . . . . . . . . . . . . . . . . . . . . . 22 1.6 Mã của các từ vô hạn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.6.1 Từ và ngôn ngữ từ vô hạn . . . . . . . . . . . . . . . . . . . . . 24 1.6.2 ω-mã . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.6.3 Z-mã . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2 KIỂM ĐỊNH MÃ VÀ MÃ MỞ RỘNG 26 2.1 Thuật toán kiểm định mã và ♦-mã . . . . . . . . . . . . . . . . . . . . 26 2.1.1 Tiêu chuẩn Sardinas-Patterson cải tiến . . . . . . . . . . . . . . 26 2.1.2 Thuật toán kiểm định mã trên vị nhóm . . . . . . . . . . . . . . 33 2.1.3 Thuật toán kiểm định ♦-mã . . . . . . . . . . . . . . . . . . . . 36 2.2 Thuật toán kiểm định ω-mã . . . . . . . . . . . . . . . . . . . . . . . . 40 2.2.1 Thủ tục kiểm định ω-mã trên ngôn ngữ . . . . . . . . . . . . . . 40 2.2.2 Thuật toán kiểm định ω-mã trên vị nhóm . . . . . . . . . . . . 44 2.2.3 Thuật toán kiểm định ω-mã trên đồ thị . . . . . . . . . . . . . . 46 2.3 Thuật toán kiểm định Z-mã . . . . . . . . . . . . . . . . . . . . . . . . 51 2.3.1 Thủ tục kiểm định Z-mã trên ngôn ngữ . . . . . . . . . . . . . 51 2.3.2 Thuật toán kiểm định Z-mã trên vị nhóm . . . . . . . . . . . . 57 2.3.3 Thuật toán kiểm định Z-mã trên đồ thị . . . . . . . . . . . . . 61
ii MỤC LỤC 3 ĐỘ KHÔNG NHẬP NHẰNG CỦA NGÔN NGỮ 66 3.1 Tính chất không nhập nhằng của ngôn ngữ . . . . . . . . . . . . . . . . 66 3.1.1 Tích không nhập nhằng và mã . . . . . . . . . . . . . . . . . . . 67 3.1.2 Xác định độ không nhập nhằng kiểu 1 . . . . . . . . . . . . . . 69 3.1.2.1 Thủ tục xác định độ không nhập nhằng kiểu 1 . . . . 69 3.1.2.2 Thuật toán xác định độ không nhập nhằng kiểu 1 . . . 72 3.1.3 Xác định độ không nhập nhằng kiểu 2 . . . . . . . . . . . . . . 74 3.1.3.1 Thủ tục xác định độ không nhập nhằng kiểu 2 . . . . 74 3.1.3.2 Thuật toán xác định độ không nhập nhằng kiểu 2 . . . 79 3.2 Phân bậc ngôn ngữ theo tính không nhập nhằng . . . . . . . . . . . . . 81 3.2.1 Phân bậc kiểu 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.2.2 Phân bậc kiểu 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.3 Độ trễ giải mã . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.3.1 Độ trễ giải mã và độ không nhập nhằng . . . . . . . . . . . . . 83 3.3.2 Xác định độ trễ giải mã . . . . . . . . . . . . . . . . . . . . . . 84 3.3.2.1 Thủ tục xác định độ trễ giải mã cho ngôn ngữ . . . . . 84 3.3.2.2 Thuật toán tìm độ trễ giải mã cho ngôn ngữ chính quy 90 3.3.3 Thuật toán xác định độ trễ giải mã của ♦-mã . . . . . . . . . . 92 4 MỘT SỐ ỨNG DỤNG 94 4.1 Hệ mật đa trị và nhập nhằng . . . . . . . . . . . . . . . . . . . . . . . 94 4.2 Bài toán tương ứng Post và ứng dụng . . . . . . . . . . . . . . . . . . . 97 4.2.1 Bài toán tương ứng Post trên lớp ngôn ngữ từ định biên . . . . 97 4.2.2 Kỹ thuật bẫy cửa sập . . . . . . . . . . . . . . . . . . . . . . . . 103 KẾT LUẬN 104 TÀI LIỆU THAM KHẢO 106 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ 109
DANH MỤC BẢNG, HÌNH VẼ 1.1 Một overlap của hai từ liên hợp x và y . . . . . . . . . . . . . . . . . . 11 1.2 Một X-phân tích của từ w . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 Khởi đầu một phân tích kép của từ w . . . . . . . . . . . . . . . . . . . 17 2.1 Một hướng cải tiến tiêu chuẩn kiểm định mã Sardinas-Patterson . . . . 27 2.2 Các ngôn ngữ X của Ví dụ 2.6 và 2.7 . . . . . . . . . . . . . . . . . . . 33 3.1 Minh họa một trường hợp tính toán các tập Ui , Vi+1 . . . . . . . . . . . 69 4.1 Cấu trúc điều khiển B . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 4.2 Từ tuyệt mật w . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 4.1 Bảng nhân bí mật B × B . . . . . . . . . . . . . . . . . . . . . . . . . . 99 4.3 Chi tiết cấu trúc từ tuyệt mật w . . . . . . . . . . . . . . . . . . . . . 101 4.2 Bảng kê xác suất tìm được nghiệm của bài toán . . . . . . . . . . . . . 102
MỞ ĐẦU Mã có vai trò thiết yếu trong nhiều lĩnh vực như xử lý thông tin, nén dữ liệu, truyền thông và mật mã. Đặc biệt, theo sự tiến bộ của khoa học máy tính, nhu cầu sử dụng mã trong biểu diễn, bảo mật thông tin ngày càng cấp thiết về thực tiễn, đòi hỏi những công trình nghiên cứu cả chiều sâu và chiều rộng. Trong số đó phải kể đến các bài toán trong lĩnh vực của lý thuyết mã và ứng dụng. Ta biết rằng khái niệm mã khởi nguồn từ lý thuyết thông tin do Shannon đề xuất năm 1949. Trong khuôn khổ lý thuyết này, sự phát triển của lý thuyết mã dẫn tới các nghiên cứu về mã có độ dài cố định liên quan đến các bài toán phát hiện lỗi và sửa lỗi trong truyền thông dữ liệu. Đến năm 1955, Sch¨ utzenberger đề xuất hướng nghiên cứu về mã có độ dài biến đổi sử dụng các phương pháp tổ hợp và đại số. Từ đó, nhiều công trình nghiên cứu đã nảy sinh, phát triển và nhận được những kết quả phong phú, lý thú trong cả lý thuyết và ứng dụng. Lý thuyết mã ngày nay là một bộ phận không thể thiếu của khoa học máy tính, công nghệ thông tin và truyền thông..., có liên hệ chặt chẽ với các lý thuyết tổ hợp trên từ, lý thuyết otomat, ngôn ngữ hình thức và lý thuyết nửa nhóm. Bài toán kiểm định mã và bài toán nghiên cứu các đặc tính của mã hay các ngôn ngữ hình thức trong mối quan hệ với mã là những bài toán được nhiều nhà khoa học quan tâm nghiên cứu vì vai trò sâu sắc và rất cơ bản của chúng trong sự phát triển của lý thuyết mã nói riêng, của ngôn ngữ hình thức và lý thuyết biểu diễn thông tin nói chung. Khái niệm mã được xem xét trong luận án là mã có độ dài biến đổi. Ta có thể hình dung một mã là một ngôn ngữ của các từ hữu hạn sao cho tích ghép của các từ của nó có thể được “giải mã” một cách duy nhất. Tích ghép có hai dạng: trường hợp của mã là tích ghép hữu hạn và trường hợp của ω-mã, Z-mã là tích ghép vô hạn. Từ đó có thể thấy rằng bài toán kiểm định một ngôn ngữ cho trước có là mã (ω-mã, Z-mã) không, là bài toán rất cơ bản của lý thuyết mã. Sử dụng phương pháp tổ hợp trên từ để kiểm tra một ngôn ngữ cho trước có thỏa mãn định nghĩa của mã không, Sardinas và Patterson (1953) đã đưa ra một tiêu chuẩn kiểm định mã, còn gọi là tiêu chuẩn Sardinas-Patterson cho lớp ngôn ngữ tổng quát. Ta để ý rằng, trong lĩnh vực của Toán học, tiêu chuẩn Sardinas-Patterson được xem là câu trả lời cho bài toán đặt ra. Tuy nhiên, nhiều nghiên cứu sâu trong các lĩnh vực của Tin học, Tổ hợp, Tính toán... lại đòi hỏi tính kiến thiết với các thuật toán chi tiết. Về nguyên tắc, theo phương pháp của Sardinas và Patterson, các thuật toán như vậy chỉ có thể nhận được khi số cấu hình tổ hợp cần kiểm tra là hữu hạn. Đây là trường hợp của các ngôn ngữ đoán nhận được, hoặc tương đương là các ngôn ngữ chính quy. Thuật toán kiểm định mã hiệu quả cho lớp ngôn ngữ chính quy hữu hạn đã được đề
MỞ ĐẦU 3 xuất bởi Rodeh (1982) với độ phức tạp thời gian là O(nm), ở đó n là tổng số từ mã của ngôn ngữ và m là tổng độ dài của chúng. Đối với lớp ngôn ngữ chính quy tổng quát, để thiết lập thuật toán, ta phải kết hợp với chúng các công cụ otomat hoặc vị nhóm hữu hạn. Khi đó ngôn ngữ đầu vào được giả thiết là đoán nhận được bởi một otomat hữu hạn hoặc thỏa bởi một đồng cấu đại số. Nếu đầu vào cho bởi một otomat hữu hạn, thuật toán kiểm định mã tốt nhất được biết là của Robert (1996) có độ phức tạp thời gian là O(n2 ), với n là tổng số trạng thái và số cung của otomat đó. Trường hợp đầu vào là một đồng cấu đại số thì thuật toán là chưa được biết và câu hỏi tất yếu (câu hỏi 1) là: Có tồn tại một thuật toán hiệu quả kiểm định mã không? Câu hỏi tương tự (câu hỏi 2) cũng được nêu ra khi ta xem xét bài toán kiểm định ω-mã. Đối với Z-mã thì cho đến nay, ta mới biết đến tiêu chuẩn toán học kiểu Sardinas- Patterson của nhóm tác giả Đỗ Long Vân, Nguyễn Hương Lâm và Phan Trung Huy (1993), còn sự tồn tại một thuật toán kiểm định Z-mã thì chưa được biết. Mặt khác, với các hình thức mã mở rộng, chẳng hạn một số mã mới cũng được nhóm nghiên cứu của tác giả phát triển gần đây như mã luân phiên và ♦-mã, thì câu hỏi (câu hỏi 3) là: Thuật toán kiểm định mã có thể mở rộng, hoặc cải biên để áp dụng cho Z-mã và các mã này không? Từ những vấn đề và câu hỏi được đặt ra như trên, hướng nghiên cứu cải tiến thuật toán kiểm định mã và mã mở rộng là rất cần thiết và có ý nghĩa thời sự. Do đó, mục tiêu thứ nhất của luận án là, dựa trên các thành tựu của đại số, lý thuyết otomat và lý thuyết đồ thị, thiết lập các thuật toán kiểm định mới, chất lượng tốt hơn cho mã và các thuật toán kiểm định cho các lớp mã khác gồm ♦-mã, ω-mã và Z-mã. Đối với vấn đề kiểm định mã đặt ra trong câu hỏi 1, nếu tiếp cận theo phương pháp kinh điển của Sardinas và Patterson thì theo tính chất đoán nhận ngôn ngữ bởi một đồng cấu đại số, ta sẽ nhận được một thuật toán cỡ hàm mũ vì trong thủ tục tính toán, ta không tránh khỏi việc phải xem xét tất cả các tập con của vị nhóm hữu hạn đoán nhận ngôn ngữ đầu vào. Trong luận án, nhờ một kỹ thuật loang dần trong lý thuyết đồ thị, chúng tôi chứng minh một kết quả quan trọng cho phép nhận được một tiêu chuẩn mới cải tiến từ tiêu chuẩn Sardinas-Patterson để kiểm định mã. Từ đó cho phép giảm số bước tính toán của thủ tục xuống cỡ tuyến tính theo kích thước của vị nhóm đã cho. Kết quả nhận được là một thuật toán có độ phức tạp về mặt thời gian là một đa thức bậc hai hiệu quả, trả lời khẳng định cho câu hỏi đặt ra. Liên quan đến câu hỏi 2, năm 1986, Staiger đã đề xuất một tiêu chuẩn đại số cho việc kiểm định ω-mã trên cơ sở của tiêu chuẩn Sardinas-Patterson. Từ kết quả này, Augros và Litovsky (1999) đã phát triển một thuật toán dựa trên otomat hữu hạn để kiểm định một ngôn ngữ chính quy có là ω-mã không với độ phức tạp thời gian là O(n3 ), n là kích thước của vị nhóm các phép chuyển dịch của otomat tối tiểu đoán nhận ngôn ngữ đó. Với vị nhóm hữu hạn bất kỳ thỏa ngôn ngữ đầu vào (vị nhóm các phép chuyển dịch nói trên chỉ là một trường hợp riêng), chúng tôi đề xuất một tiêu
4 MỞ ĐẦU chuẩn mới kiểm định ω-mã và dựa trên đồ thị hữu hạn có tô màu cung, thiết lập một thuật toán kiểm định ω-mã có độ phức tạp thời gian chỉ là O(n2 ), với n là kích thước của vị nhóm đã cho. Chúng tôi cũng mở rộng các kết quả nói trên, thiết lập các thuật toán mới, hiệu quả kiểm định ♦-mã và Z-mã, để trả lời câu hỏi 3. Một bài toán cơ bản của ngôn ngữ hình thức có liên quan đến lý thuyết mã là bài toán nghiên cứu dựa trên đặc điểm phân tích không nhập nhằng của một từ thành dãy các từ đặc biệt thuộc một ngôn ngữ đã cho, mà mã là một trường hợp riêng. Từ đó, tính không nhập nhằng trở thành một đối tượng được nghiên cứu trong mối liên hệ với lý thuyết mã. Vì đặc tính không nhập nhằng liên quan đến phương pháp biểu diễn thông tin một cách duy nhất nên bài toán nghiên cứu về phân tích không nhập nhằng sẽ đưa đến một hướng nghiên cứu mở rộng của lý thuyết mã. Khái niệm không nhập nhằng xuất hiện khá thường xuyên trong lý thuyết khoa học máy tính. Chẳng hạn otomat không nhập nhằng, văn phạm không nhập nhằng hay các phép toán không nhập nhằng trên ngôn ngữ. Khi đó, không nhập nhằng thể hiện tính duy nhất của quan hệ tồn tại một đường đi trong otomat, một dẫn xuất trong văn phạm hay một phân tích của từ thuộc ngôn ngữ. Định nghĩa của mã ngụ ý mã là không nhập nhằng. Chi tiết hơn, ta biết rằng một mã X tùy ý là không nhập nhằng. Nghĩa là bất kỳ một thông điệp nào được mã hóa thành các từ của X sẽ được giải mã theo một cách duy nhất. Tuy nhiên, tính duy nhất không đảm bảo việc giải mã được thực hiện dễ dàng. Ví dụ, nếu các chữ cái x, y, z trong một thông điệp được mã hóa lần lượt thành các từ b, ba, aa của X, thì việc giải mã không thể quyết định thông điệp baaa . . . khởi đầu bởi b hay ba. Điều này phản ánh khía cạnh nhập nhằng của mã, liên quan đến độ trễ giải mã là một loại độ khó của quá trình giải mã được đề xuất bởi Gilbert và Moore (1959). Biểu diễn mã thực chất là biểu diễn thông tin một cách duy nhất. Thật ngạc nhiên, trong khi các nghiên cứu về tính không nhập nhằng và độ trễ giải mã của mã khá sôi động, có nhiều kết quả được thiết lập và ứng dụng mạnh mẽ trong lĩnh vực mật mã, biểu diễn tri thức và nhiều lĩnh vực khác, thì tính không nhập nhằng của ngôn ngữ nói chung không là mã chưa được nghiên cứu. Các vấn đề và câu hỏi được đưa ra sau đây cho thấy tính cấp thiết phải có các nghiên cứu về chủ đề này. Thứ nhất, phân lớp mã là một hướng nghiên cứu quan trọng của lý thuyết mã. Chẳng hạn, liên quan đến cấu trúc tạo dựng của mã, mã prefix có thể được xây dựng một cách đơn giản, còn cấu trúc của mã tổng quát vẫn còn là vấn đề mở. Phân lớp mã theo độ trễ giải mã cho phép ta mở rộng những khái niệm của mã prefix (có độ trễ 0) cho trường hợp mã tổng quát. Tuy nhiên phân bậc này bỏ qua các lớp ngôn ngữ không là mã, tạo ra một khoảng trống trong nghiên cứu lý thuyết mã hóa thông tin và ứng dụng. Từ đó, phát sinh một câu hỏi (câu hỏi 4) là: Có tồn tại một phân bậc mịn của toàn bộ các ngôn ngữ theo tính không nhập nhằng không? Hai là, trong lĩnh vực mật mã, nguyên lý chung là không có hệ mật tồn tại lâu dài
MỞ ĐẦU 5 trước sự tấn công, do đó luôn có nhu cầu thiết lập các hệ mật mới. Trong các hệ mật, mã là đối tượng bị tấn công. Khi đó, câu hỏi (câu hỏi 5) được đặt ra là: Nếu ta sử dụng ngôn ngữ không phải là mã thì có nâng cao được hiệu quả an toàn chống tấn công cho các hệ mật không? Nghiên cứu sâu về tính không nhập nhằng của ngôn ngữ còn đặt ra nhiệm vụ phải thiết lập các thuật toán tính toán các loại độ đo nhập nhằng và không nhập nhằng đã được đề cập, ở đây là độ trễ giải mã và độ không nhập nhằng của ngôn ngữ. Mặc dù các tiêu chuẩn cho một ngôn ngữ có độ trễ giải mã hữu hạn đã được đưa ra bởi nhiều tác giả, chẳng hạn của Vũ Thành Nam (2007) cho mã và Devolder và các tác giả khác (1994) cho ω-mã, thuật toán hiệu quả tính độ trễ giải mã vẫn chưa được biết. Hơn nữa, thiết lập các thuật toán tính độ trễ giải mã cho các lớp mã mới, thuật toán tính độ không nhập nhằng của ngôn ngữ theo hai kiểu khác nhau, mối quan hệ giữa chúng và mối quan hệ của chúng với độ trễ giải mã là những vấn đề hoàn toàn mới. Vì vậy, mục tiêu thứ hai của luận án là nghiên cứu những lớp ngôn ngữ gần mã thông qua nghiên cứu về độ không nhập nhằng của ngôn ngữ xem như một yếu tố phản ánh sự “gần nhau” của một ngôn ngữ với một mã, và thiết lập phân bậc ngôn ngữ dựa trên độ không nhập nhằng của chúng. Cuối cùng nhưng không kém quan trọng, mục tiêu thứ ba của luận án là, từ những kết quả được thiết lập mới trong luận án, đề xuất một số sơ đồ ứng dụng. Các kết quả nhận được của luận án đã trả lời khẳng định các câu hỏi 4 và 5, đồng thời giải quyết các nhiệm vụ nghiên cứu về tính không nhập nhằng được đặt ra ở phần trên. Cụ thể, đặc trưng ranh giới của sự nhập nhằng và không nhập nhằng của một ngôn ngữ bởi độ không nhập nhằng và phân lớp ngôn ngữ theo độ không nhập nhằng này, chúng tôi nhận được một phân bậc vô hạn rất mịn của toàn bộ các ngôn ngữ. Trong đó, mã thuộc lớp ngôn ngữ đặc biệt nằm trong phân bậc này. Đây là một bức tranh tổng thể về lý thuyết, khởi đầu cho các nghiên cứu nhằm phát hiện những tính chất mới của các lớp mã và ngôn ngữ gần mã. Hai độ đo không nhập nhằng khác nhau được đề xuất cho ngôn ngữ và những kết quả đã thiết lập cho thấy khả năng có thể ứng dụng những lớp ngôn ngữ không là mã cho mã hóa thông tin. Khi đó, độ không nhập nhằng k của ngôn ngữ được sử dụng, với 0 ≤ k ≤ ∞, đóng vai trò là một độ khó mới liên quan đến quá trình giải mã. Việc xác định đúng giá trị k sẽ gây khó khăn cho đối phương khi thực hiện thám mã. Bằng việc sử dụng các phương pháp và công cụ đại số, tổ hợp trên từ, các phương pháp truyền thống của lý thuyết otomat hữu hạn và đồ thị, các kết quả chính của luận án được trình bày chi tiết trong các chương, từ Chương 2 đến Chương 4 của luận án với cấu trúc như sau. Chương 1 được dành cho việc trình bày các khái niệm cần thiết làm cơ sở lý thuyết thiết lập các kết quả mới ở các chương sau.
6 MỞ ĐẦU Chương 2 chứa đựng các kết quả liên quan tới kiểm định mã và mã mở rộng. Mở đầu là một tiêu chuẩn mới kiểm định mã mà thực chất là tiêu chuẩn Sardinas-Patterson cải tiến được đề xuất và chứng minh. Trên cơ sở tiêu chuẩn này, bốn thuật toán kiểm định có cùng độ phức tạp thời gian O(n2 ) được thiết lập, với n là kích thước của vị nhóm thỏa ngôn ngữ đầu vào. Cụ thể đó là: − Thuật toán 2.2 kiểm định mã cho trường hợp ngôn ngữ chính quy, trên cơ sở của Định lý 2.1. − Thuật toán 2.3 kiểm định ♦-mã cho trường hợp ♦-ngôn ngữ chính quy, trên cơ sở của Định lý 2.4. − Thuật toán 2.4 kiểm định ω-mã cho trường hợp ngôn ngữ chính quy, trên cơ sở của các Định lý 2.6 và 2.7. − Thuật toán 2.5 kiểm định Z-mã cho trường hợp ngôn ngữ chính quy, trên cơ sở của các Định lý 2.11, 2.12 và 2.13. Thuật toán 2.2 nhận được nhờ sử dụng phương pháp đại số kết hợp với một cấu trúc dữ liệu đặc biệt kiểu stack trên vị nhóm hữu hạn. Thuật toán 2.3 có phương pháp tiếp cận tương tự ngoại trừ một số tính chất đại số mở rộng được thiết lập cho lớp ♦-ngôn ngữ. Đối với ω-mã và Z-mã, để có các Thuật toán 2.4 và 2.5, phương pháp đại số kết hợp với phương pháp đồ thị được giới thiệu. Ở đó các kỹ thuật được trình bày chi tiết gồm kỹ thuật chuyển biểu diễn đại số của bài toán sang biểu diễn đồ thị và kỹ thuật kiểm định chu trình đặc biệt trên đồ thị hữu hạn có tô màu cung. Các điều kiện tương đương cho các bài toán được chứng minh đầy đủ cùng với độ phức tạp thời gian của từng bước thực hiện được tính toán chi tiết. Chương 3 trình bày các khái niệm và kết quả mới làm rõ một khoảng trống trong nghiên cứu lý thuyết mã hóa thông tin và ứng dụng. Đó là lớp các ngôn ngữ rất lớn đặc trưng bởi độ không nhập nhằng, nằm giữa lớp mã và lớp ngôn ngữ được định nghĩa bởi tích không nhập nhằng. Các đặc trưng tổ hợp và đại số của ngôn ngữ lần lượt được thiết lập làm cơ sở đề xuất các thuật toán xác định các độ đo nhập nhằng và không nhập nhằng của chúng. Trong một số trường hợp đặc biệt, ta còn sử dụng công cụ otomat hữu hạn kết hợp với ngôn ngữ để diễn tả các thuật toán. Ngoài hai phân bậc ngôn ngữ theo hai kiểu độ không nhập nhằng, các kết quả chính được thiết lập là: − Thuật toán 3.1 xác định độ không nhập nhằng kiểu 1 cho lớp ngôn ngữ chính quy, trên cơ sở của Định lý 3.1. − Thuật toán dựa trên otomat hữu hạn xác định độ không nhập nhằng kiểu 2 cho lớp ngôn ngữ chính quy, trên cơ sở của các Định lý 3.2 và 3.3. − Thuật toán dựa trên otomat hữu hạn xác định độ trễ giải mã cho mã thuộc lớp ngôn ngữ chính quy, trên cơ sở của các Định lý 3.4 và 3.5.
MỞ ĐẦU 7 − Thuật toán tổ hợp xác định độ trễ giải mã cho ♦-mã thuộc lớp ♦-ngôn ngữ chính quy, trên cơ sở của các Định lý 3.6 và 3.7. Thuật toán 3.1 là thuật toán kiểu Sardinas-Patterson cải tiến mà ta thiết lập trong Chương 2. Độ phức tạp thời gian của nó là O(n2 ). Các thuật toán còn lại đều có độ phức tạp thời gian cỡ hàm mũ theo n, với n là kích thước của vị nhóm thỏa ngôn ngữ đầu vào. Đây là đánh giá thô theo tính chất đoán nhận ngôn ngữ bởi một đồng cấu đại số. Các thuật toán hiệu quả hơn sẽ được xem xét như một hướng nghiên cứu tiếp theo của luận án. Chương 4 dành cho việc trình bày một số sơ đồ ứng dụng. Kết quả cụ thể như sau: − Đối với lớp ngôn ngữ k-không nhập nhằng kiểu 1, đề xuất một hệ mật có tính đa trị và nhập nhằng sử dụng các ngôn ngữ có độ nhập nhằng cao. − Đối với lớp ngôn ngữ từ định biên, đề xuất một sơ đồ bảo mật và một hướng nghiên cứu mở rộng để xây dựng các hệ mật mới dựa trên bẫy cửa sập là một dẫn xuất của bài toán không quyết định được PCP. Các kết quả chính của luận án đã được công bố trong các công trình 1 - 16 (xem Danh mục các công trình đã công bố, hoặc đã qua phản biện và đã được chấp nhận đăng của luận án) và đã được trình bày tại: − Seminar “Toán rời rạc và Tổ hợp”, Phòng Cơ sở Toán học của Tin học, Viện Toán học. − Seminar khoa học, Bộ môn Toán Tin, Viện Toán ứng dụng và Tin học, Trường Đại học Bách Khoa Hà Nội. − Hội thảo quốc gia lần thứ XII “Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông”, Biên Hòa, 5 - 6/8/2009. − Hội thảo quốc gia lần thứ XIII “Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông”, Hưng Yên, 19 - 20/8/2010. − Hội nghị toàn quốc lần thứ III về Ứng dụng toán học, Hà Nội, 23 - 25/12/2010. − Hội thảo quốc gia lần thứ XIV “Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông”, Cần Thơ, 7 - 8/10/2011. − Hội thảo quốc tế IEEE-RIVF 2012, Thành phố Hồ Chí Minh, 27/2 - 1/3/2012. − Hội thảo quốc tế ACIIDS 2012, Kaohsiung, Taiwan, 19 - 21/3/2012.
Chương 1 CƠ SỞ LÝ THUYẾT MÃ Trong chương này, chỉ những khái niệm cơ bản liên quan được sử dụng trong luận án mới được đề cập. Nội dung kiến thức về đại số, ngôn ngữ và mã của các từ hữu hạn trình bày trong các mục, từ Mục 1.1 đến Mục 1.4, được tham khảo và trích dẫn từ các tài liệu [4; 5; 6; 7; 9; 13; 16; 18; 21; 27; 28]. Bên cạnh đó, luận án còn giới thiệu một số lớp mã dựa trên các hình thức tích mới có tính thời sự làm cơ sở để thiết lập các thuật toán mới, hiệu quả cho các lớp mã này trong các chương tiếp theo. Nội dung kiến thức về mã luân phiên và mã của các từ định biên trình bày trong Mục 1.5 là một hướng nghiên cứu mới trong lý thuyết mã, được đề xuất gần đây trong các công trình [14; 15; 23; 35; 36; 37; 38]. Kiến thức về ngôn ngữ và mã của các từ vô hạn xem như một sự mở rộng các khái niệm trong lý thuyết mã truyền thống cho trường hợp vô hạn, được tổng hợp từ các tài liệu [3; 10; 11; 13; 19; 20; 24; 29; 31; 32; 33; 34], là nội dung của Mục 1.6. Trong luận án, tập các số tự nhiên được ký hiệu là N. Lực lượng của một tập hợp X được ký hiệu là Card(X). Các bảng chữ đều được giả thiết là hữu hạn nếu không nói gì khác. 1.1 Nửa nhóm và vị nhóm Ta nhắc lại rằng một nửa nhóm S là một tập hợp được trang bị một phép toán hai ngôi kết hợp, nếu không nói gì thêm ta sẽ ký hiệu theo lối nhân. Một nửa nhóm con (t.ư. nhóm con) T của S là một tập con của S cùng với phép toán cảm sinh làm cho T trở thành nửa nhóm (t.ư. nhóm). Nửa nhóm S là một vị nhóm nếu S có đơn vị. Đơn vị của vị nhóm S là duy nhất và được ký hiệu là 1S . Một vị nhóm con của vị nhóm S là một nửa nhóm con có chứa đơn vị của S. Ví dụ 1.1 M = {0, 1} là vị nhóm nhân với phần tử đơn vị là 1. Ví dụ 1.2 Với vị nhóm M bất kỳ, ta trang bị cấu trúc vị nhóm cho tập tất cả các tập con P(M) của M bằng cách định nghĩa, với X, Y ⊂ M, XY = {x.y | x ∈ X, y ∈ Y }. Phần tử đơn vị là {1}.
1.2 Từ và ngôn ngữ 9 Ví dụ 1.3 Từ các vị nhóm M, N ta có vị nhóm M × N là tích trực tiếp của M và N, M (n) là tích trực tiếp của n lần vị nhóm M. Cho các nửa nhóm (vị nhóm) S và T . Ánh xạ ϕ : S → T được gọi là một đồng cấu nửa nhóm (t.ư. vị nhóm) nếu với mọi a, b ∈ S, ϕ(ab) = ϕ(a)ϕ(b) (t.ư. ϕ(ab) = ϕ(a)ϕ(b) và ϕ(1S ) = 1T với 1S là đơn vị của S, 1T là đơn vị của T ). Đồng cấu ϕ được gọi là đơn cấu (t.ư. toàn cấu, đẳng cấu) nếu ϕ là đơn ánh (t.ư. toàn ánh, song ánh). Một đồng cấu từ vị nhóm S vào chính nó thì được gọi là một tự đồng cấu. Cho M là một vị nhóm. Với x, y ∈ M, ta có x−1 y = {z ∈ M | x.z = y} và xy −1 = {z ∈ M | x = z.y}. Với S, T ⊆ M, ta định nghĩa các phép cắt trái, phải của S bởi T T −1 S = {u ∈ M | ∃t ∈ T : t.u ∈ S} và ST −1 = {u ∈ M | ∃t ∈ T : u.t ∈ S}. Ta có tính chất cơ bản sau đây Tính chất 1.1 Cho M là một vị nhóm, P, K ⊆ M, P = K ∗ và m ∈ M. Khi đó P −1(m−1 K) = (m.P )−1 K. Chứng minh. Chứng minh P −1 (m−1 K) ⊆ (m.P )−1 K. Ta có w ∈ P −1(m−1 K) ⇔ (∃p ∈ P, k ∈ K : w = p−1 (m−1 k) ⇔ k = m.p.w). Vì vậy w = (m.p)−1 k ∈ (m.P )−1 K. Chứng minh (m.P )−1 K ⊆ P −1(m−1 K). Ta có w ∈ (m.P )−1 K ⇔ (∃p ∈ P, k ∈ K : w = (m.p)−1 k ⇔ k = m.p.w). Vì vậy w = p−1 (m−1 k) ∈ P −1 (m−1 K). 1.2 Từ và ngôn ngữ Cho A là một bảng chữ. Một từ w trên bảng chữ A là một dãy hữu hạn các phần tử của A w = (a1 , a2 , . . . , an ), ai ∈ A. Tập tất cả các từ trên bảng chữ A được ký hiệu là A∗ và được trang bị phép nhân (tích) ghép có tính chất kết hợp (a1 , a2 , . . . , an )(b1 , b2 , . . . , bm ) = (a1 , a2 , . . . , an , b1 , b2 , . . . , bm ).
10 1 CƠ SỞ LÝ THUYẾT MÃ Vì vậy, để thuận tiện ta viết w = a1 a2 · · · an thay cho w = (a1 , a2 , . . . , an ). Một phần tử a ∈ A được gọi là một chữ cái. Từ rỗng được ký hiệu là ε đóng vai trò là phần tử đơn vị trong phép nhân ghép. Do đó, tập A∗ có cấu trúc vị nhóm và A∗ được gọi là vị nhóm tự do trên A. Tập tất cả các từ khác rỗng trên A được ký hiệu là A+ . Ta có A+ = A∗ − {ε}. Độ dài |w| của từ w = a1 a2 · · · an với ai ∈ A là n. Quy ước |ε| = 0. Ánh xạ w 7→ |w| là một đồng cấu từ A∗ đến vị nhóm cộng N. Với n ≥ 0, ta ký hiệu A
1.2 Từ và ngôn ngữ 11 Hình 1.1 Một overlap của hai từ liên hợp x và y Ta có  X ∗ − {ε} nếu ε ∈ / X, X+ = X ∗ nếu ε ∈ X. Một phân tích của một từ w ∈ A∗ theo các từ của X cho bởi đẳng thức w = x1 x2 · · · xn , xi ∈ X, i ≥ 1. Khi đó, ta cũng nói w có một X-phân tích. Theo định nghĩa, mỗi từ w ∈ X ∗ có ít nhất một X-phân tích. Để dễ hình dung, ta thường biểu diễn một X-phân tích w = x1 x2 · · · xn bằng hình sau. Hình 1.2 Một X-phân tích của từ w Cho X, Y ⊆ A∗ là các ngôn ngữ. Tích của X và Y , thương trái, thương phải của X bởi Y là các ngôn ngữ được định nghĩa ở mục trước với vị nhóm M = A∗ . Với u, v ∈ M, ta sẽ viết uv thay cho u.v. Khi đó XY = {xy|x ∈ X, y ∈ Y }, Y −1 X = {w ∈ A∗ | yw ∈ X, y ∈ Y }, XY −1 = {w ∈ A∗ | wy ∈ X, y ∈ Y }. Ký hiệu u−1 X, Xu−1 được sử dụng khi tập Y chỉ có một phần tử Y = {u}. Tính chất 1.2 Cho X, Y, Z ⊆ A∗ là các ngôn ngữ. Khi đó X −1 (Y ∪ Z) = X −1 Y ∪ X −1 Z. Chứng minh. Chứng minh X −1 (Y ∪Z) ⊆ X −1 Y ∪X −1 Z. Với w bất kỳ, w ∈ X −1 (Y ∪Z), tồn tại x ∈ X sao cho xw ∈ Y ∪ Z. Từ xw ∈ Y hoặc xw ∈ Z ta có w ∈ X −1 Y hoặc w ∈ X −1 Z. Vậy w ∈ X −1 Y ∪ X −1 Z. Chứng minh X −1 Y ∪ X −1 Z ⊆ X −1 (Y ∪ Z). Với w bất kỳ, w ∈ X −1 Y ∪ X −1 Z, tồn tại x ∈ X sao cho xw ∈ Y hoặc xw ∈ Z. Từ xw ∈ Y ∪ Z ta có w ∈ X −1 (Y ∪ Z).
12 1 CƠ SỞ LÝ THUYẾT MÃ Tính chất 1.3 Cho X, Y, Z ⊆ A∗ là các ngôn ngữ. Ta có (Y ∪ Z)−1 X = Y −1 X ∪ Z −1 X. Chứng minh. Chứng minh (Y ∪Z)−1 X ⊆ Y −1 X∪Z −1 X. Với w bất kỳ, w ∈ (Y ∪Z)−1 X, tồn tại u ∈ Y ∪ Z sao cho uw ∈ X. Nếu u ∈ Y thì uw ∈ X và w ∈ Y −1 X. Nếu u ∈ Z thì uw ∈ X và w ∈ Z −1 X. Vậy, w ∈ Z −1 X ∪ Z −1 X. Chứng minh Y −1 X ∪ Z −1 X ⊆ (Y ∪ Z)−1 X. Với w bất kỳ, w ∈ Y −1 X ∪ Z −1 X. Nếu w ∈ Y −1 X, thì tồn tại y ∈ Y sao cho yw ∈ X. Nếu w ∈ Z −1 X, thì tồn tại z ∈ Z sao cho zw ∈ X. Tức là, tồn tại u ∈ Y ∪ Z sao cho uw ∈ X. Vậy, w ∈ (Y ∪ Z)−1 X. 1.3 Otomat và ngôn ngữ chính quy 1.3.1 Otomat Cho A là một bảng chữ, một otomat trên A là một bộ A = (Q, A, F) gồm một tập hữu hạn các trạng thái Q và tập các cung F ⊆ Q × A × Q, mỗi cung có dạng (p, a, q) với p là đỉnh đầu, q là đỉnh cuối và a là nhãn của cung. Ta còn biểu diễn một otomat với tập trạng thái khởi đầu I ⊆ Q và tập trạng thái kết thúc T ⊆ Q bởi (Q, A, F, I, T ) hoặc ngắn gọn (Q, I, T ) khi A và F cố định. Otomat A = (Q, A, F) là hữu hạn nếu tập trạng thái Q hữu hạn. Một đường đi trong otomat A là một dãy c = (f1 , f2 , . . . , fn ) các cung liền nhau fi = (qi , ai , qi+1 ), 1 ≤ i ≤ n. Số n được gọi là độ dài của đường đi c. Từ w = a1 a2 · · · an là nhãn của đường c. Trạng thái q1 là điểm đầu và trạng thái qn+1 là điểm cuối của c. Để thuận tiện khi tham chiếu đến đường đi c, ta sử dụng ký hiệu c : q1 −→ qn+1 . w Quy ước, với mỗi trạng thái q ∈ Q, có một đường đi độ dài 0, nhãn ε, từ q đến q. Một đường đi c : i −→ t là đường đi thành công nếu i ∈ I và t ∈ T . Ngôn ngữ đoán nhận được bởi A, ký hiệu là L(A), được định nghĩa là tập các nhãn của các đường đi thành công: L(A) = {w ∈ A∗ | ∃c : i − w → t, i ∈ I, t ∈ T }. Một otomat A = (Q, I, T ) là đơn định nếu Card(I)=1 và nếu (p, a, q), (p, a, r) ∈ F ⇒ q = r. Vì vậy, với mỗi p ∈ Q và a ∈ A, có nhiều nhất một trạng thái q ∈ Q sao cho p −→ q. Với p ∈ Q và a ∈ A, ta định nghĩa a  q nếu (p, a, q) ∈ F, p.a = ∅ nếu (p, a, q) ∈ / F.
1.3 Otomat và ngôn ngữ chính quy 13 Hàm bộ phận Q × A −→ Q định nghĩa như trên được mở rộng cho từ bằng cách đặt, với mọi q ∈ Q, p.ε = p, và, với w ∈ A∗ và a ∈ A, p.wa = (p.w).a. Hàm định nghĩa như trên được gọi là hàm chuyển của A. Khi đó, với I = {i} ta có L(A) = {w ∈ A∗ | i.w ∈ T }. 1.3.2 Ngôn ngữ chính quy Lớp các ngôn ngữ chính quy trên A∗ (trên A+ ) được ký hiệu là RecA∗ (RecA+ ). Ta biết rằng RecA∗ là lớp các ngôn ngữ sinh bởi các ngôn ngữ {a}, với a là một chữ cái thuộc A, các phép toán Boole (∪, ∩, −), phép nhân ghép và phép lặp *, và cũng là lớp các ngôn ngữ đoán nhận được bởi otomat hữu hạn, RecA+ = {L ∈ RecA∗ | L ⊆ A+ }. Ta có Mệnh đề 1.1 ([5]) Lớp các ngôn ngữ chính quy trên A∗ đóng đối với phép toán Boole: phép hợp (∪), phép giao (∩), phép lấy phần bù (−). Cho X ⊆ A∗ là một ngôn ngữ chính quy. Ta định nghĩa một otomat hữu hạn đặc biệt A(X) = (Q, i, T ) như sau. Các trạng thái của A(X) là các tập khác rỗng u−1 X với u ∈ A∗ . Trạng thái khởi đầu là X = ε−1 X, và các trạng thái kết thúc có chứa từ rỗng. Hàm chuyển cho một trạng thái Y = u−1 X và một chữ cái a ∈ A được cho bởi → a−1 Y . a Y − Đây là một hàm bộ phận và ta có L(A(X)) = X. Ta biết rằng theo [5], otomat A(X) được gọi là otomat tối tiểu của X theo nghĩa đơn định, có số trạng thái ít nhất mà đoán nhận X. Cho A = (Q, i, T ) là một otomat đơn định. Ta xem xét tập F của các hàm bộ phận từ Q đến Q. Các hàm này được viết về phía bên phải: nếu q ∈ Q và m ∈ F khi đó ảnh của q bởi m được ký hiệu là qm. Hàm hợp được định nghĩa bởi
14 1 CƠ SỞ LÝ THUYẾT MÃ q(mn) = (qm)n. Khi đó, F lập thành một vị nhóm. Xét ϕ là một ánh xạ cho tương ứng mỗi từ w ∈ A∗ một hàm bộ phận từ Q đến Q định nghĩa bởi qϕ(w) = q.w. Khi đó, ánh xạ ϕ là một đồng cấu từ A∗ đến vị nhóm F, và vị nhóm ϕ(A∗ ) của F được gọi là vị nhóm các phép chuyển dịch của otomat A. Một đồng cấu ϕ từ A∗ đến một vị nhóm M được gọi là thỏa ngôn ngữ X ⊆ A∗ nếu tồn tại B ⊆ M, B = ϕ(X) sao cho ϕ−1 (B) = X. Khi đó, ta cũng nói X thỏa bởi M và X cho bởi một bộ ba (ϕ, M, B). Cho X, Y ⊆ A∗ là các ngôn ngữ. Ta thiết lập bổ đề kỹ thuật sau đây về tính thỏa được làm cơ sở xây dựng các thuật toán trên vị nhóm trong các chương tiếp theo. Bổ đề 1.1 Giả sử h : A∗ → M là một toàn cấu vị nhóm thỏa X và Y và giả sử X = h−1 (K), Y = h−1 (L), h(X + ) = T với K, L, T ⊆ M. Khi đó X ∪ Y = h−1 (K ∪ L), X ∩ Y = h−1 (K ∩ L), X − Y = h−1 (K − L), X −1 Y = h−1 (K −1 L), XY −1 = h−1 (KL−1 ), (X + )−1 Y = h−1 (T −1 L), Y (X + )−1 = h−1 (LT −1 ). Chứng minh. Giả sử X = h−1 (K), Y = h−1 (L), K, L ⊆ P , ta chứng minh X ∪ Y = h−1 (K ∪ L). Trước hết, ta chứng minh X ∪ Y ⊆ h−1 (K ∪ L). Thật vậy, với mọi w ∈ X ∪ Y , ta có h(w) ∈ K hoặc h(w) ∈ L. Vậy X ∪ Y ⊆ h−1 (K ∪ L). Ngược lại, ta chứng minh h−1 (K ∪ L) ⊆ X ∪ Y . Thật vậy, với mọi w ∈ h−1 (K ∪ L), ta có h(w) ∈ K ∪ L. Nghĩa là w ∈ X ∪ Y . Vậy h−1 (K ∪ L) ⊆ X ∪ Y . Ta chứng minh tương tự cho các quan hệ X ∩Y = h−1 (K ∩L), X −Y = h−1 (K −L), X −1 Y = h−1 (K −1 L) và XY −1 = h−1 (KL−1 ). Từ giả thiết h(X + ) = T và X = h−1 (K) ta có K + = T . Để chứng minh (X + )−1 Y = h−1 (T −1 L), ta chứng minh (X + )−1 Y ⊆ h−1 (T −1 L) và h−1 (T −1 L) ⊆ (X + )−1 Y . Trước hết, ta chứng minh (X + )−1 Y ⊆ h−1 (T −1 L). Thật vậy, với mọi w ∈ (X + )−1 Y , tồn tại x1 , x2 , . . . , xn ∈ X, y ∈ Y sao cho x1 x2 · · · xn w = y. Từ đó suy ra h(x1 ).h(x2 ) · · · h(xn ).h(w) = h(y) ∈ L. Hơn nữa, từ h(xi ) ∈ K suy ra h(w) ∈ (K + )−1 L. Vậy w ∈ h−1 (T −1 L). Ngược lại, ta chứng minh h−1 (T −1 L) ⊆ (X + )−1 . Đặt w ∈ h−1 (T −1 L), ta có h(w) ∈ T −1 L = (K + )−1 L ⇔ ∃α ∈ K + : α.h(w) ∈ L.