Tài liệu TIN HỌC.Mã tích chờm

MÃ TÍCH CHỜM
Vũ Thành Nam (Trường Đại học Bách Khoa Hà Nội) - Hoàng Văn Linh
(Trường Cao đẳng Sư phạm Lạng Sơn)
1. Giới thiệu
Giả sử A là tập hữu hạn hoặc vô hạn các ký hiệu mà ta gọi là bảng chữ cái. Tập tất cả
các từ hữu hạn trên A bao gồm cả từ rỗng e được ký hiệu là A*, nửa nhóm tự do sinh bởi A là
tập A* -{e} = A+ với tích ghép các từ. Cho từ w, kí hiệu w là độ dài từ w. Mỗi tập con L của A*
được gọi là một ngôn ngữ trên A. Cho hai ngôn ngữ X và Y, ta định nghĩa tích của hai ngôn ngữ
X và Y là ngôn ngữ XY = {xy: xÎ X, y Î Y}. Ta có A* = A0ÈAÈA2È .ÈAnÈ ., ở đó A0 = {ε}, A1
= A và An = An–1A.
Từ w Î A* gọi là khúc con của từ x Î A* nếu tồn tại các từ u, v Î A*: x = uwv. Từ w gọi