TAILIEUCHUNG - Thuật toán xác định tính chất mã của ngôn ngữ chính quy
Trong bài báo này, các tác giả trình bày một thuật toán mới mở rộng thuật toán Sardinas-Patterson xác định tính chất mã của một ngôn ngữ. Từ đó nhận được một thuật toán với độ phức tạp cỡ O(k) để nhận biết một ngôn ngữ chính quy cho trước là mã hay không, với k là chỉ số hữu hạn của tương đẳng cú pháp thỏa ngôn ngữ đó. | Tạp chí Tin học và Điều khiển học, , (2011), 1 - 8 THUẬT TOÁN XÁC ĐỊNH TÍNH CHẤT MÃ CỦA NGÔN NGỮ CHÍNH QUY NGUYỄN ĐÌNH HÂN1 , HỒ NGỌC VINH2 , PHAN TRUNG HUY3 , ĐỖ LONG VÂN4 1 Khoa Công nghệ thông tin, Trường Đại học Sư phạm Kỹ thuật Hưng Yên 2 Khoa 3 Công nghệ thông tin, Trường Đại học Sư phạm Kỹ thuật Vinh Khoa Toán - Tin ứng dụng, Trường Đại học Bách khoa Hà Nội 4 Viện Toán học, Viện Khoa học và Công nghệ Việt Nam Abstract. We present an extension of the test proposed by Sardinas and Patterson (1953) for deciding whether a set of words is a code. As a consequence, we obtain an effective algorithm that decides in O(k) time whether a given regular language is a code, where k is the finite index of the syntactic congruence of this language. Tóm tắt. Trong bài báo này, chúng tôi trình bày một thuật toán mới mở rộng thuật toán Sardinas-Patterson xác định tính chất mã của một ngôn ngữ. Từ đó nhận được một thuật toán với độ phức tạp cỡ O(k) để nhận biết một ngôn ngữ chính quy cho trước là mã hay không, với k là chỉ số hữu hạn của tương đẳng cú pháp thỏa ngôn ngữ đó. 1. MỞ ĐẦU Trong lý thuyết mã, bài toán xác định tính chất mã của ngôn ngữ là một bài toán cơ bản được đề cập trong nhiều công trình nghiên cứu. Năm 1953, Sardinas và Patterson đề xuất một phương pháp tính toán tổ hợp kiểm tra tính chất mã của một tập các từ cho trước. Cho đến nay, phương pháp này vẫn được sử dụng rộng rãi như một tiêu chuẩn kiểm tra tính chất mã của ngôn ngữ. Một số công trình nghiên cứu theo hướng mở rộng phương pháp đó cho các lớp mã mới như mã zigzag (M. Anselmo [1], và . Van, B. Lesa¨c, I. Litovsky [2]), e Pcodes (F. Blanchet-Sadri, M. Margaret [3]), T-V codes (. Tiplea và các tác giả khác ¸ [4]), mã với từ định biên (. Vinh, . Huy, . Vân [5]) và mã nhị phân (D. Macro [6]), hoặc để tính toán một số độ đo của mã như độ không nhập nhằng (. Huy, . Hân, . Chuẩn [7]) và độ trễ giải mã (. Vinh, . Hân, . Huy [8]). Một số tác giả đề xuất thuật .
đang nạp các trang xem trước
