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

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!
Nội dung trích xuất từ tài liệu:
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ẬCNGÔ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ẬCNGÔ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 ĐOANTô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 ƠNLuận án được hoàn thành tại Viện Toán ứng dụng và Tin học, Trường Đạihọ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ànthiệ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ụngvà 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 đồngnghiệp Khoa Công nghệ Thông tin, Phòng Quản lý Khoa học và Đối ngoạitrong 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ỤCDANH MỤC BẢNG, HÌNH VẼ 1MỞ ĐẦU 21 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ã . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 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ị . . . . . . . . . . . . . 61ii MỤC LỤC3 ĐỘ 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 . ...