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ửanhómvàvịnhóm ........................... 8
1.2 Từvàngônngữ............................... 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ảimã............................ 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ânphiên............................ 20
1.5.2 Mã của các từ định biên . . . . . . . . . . . . . . . . . . . . . . 22
1.6 Mãcủacáctừ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