Thuật toán kiểm tra tính chất mã bằng otomat hữu hạn

- 2 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT.
- GIỚI THIỆU VỀ OTOMAT VÀ ỨNG DỤNG.
- Một số khái niệm.
- Bảng chữ cái.
- Ngôn ngữ.
- Các phép toán trên ngôn ngữ.
- Vị nhóm.
- Otomat hữu hạn.
- Otomat hữu hạn đa định.
- Otomat hữu hạn đơn định.
- Một số cách biểu diễn otomat hữu hạn.
- Một số thuật toán trên otomat hữu hạn.
- Đồ thị hữu hạn.
- MỘT SỐ LỚP MÃ VÀ OTOMAT.
- 74 - 5 - DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Từ viết tắt Giải nghĩa -mã Mã của các từ định biên -mã Mã của các từ vô hạn Z-mã Mã zigzag LCS Xâu con chung dài nhất (Longest Common Subsequence) DFA Otomat hữu hạn đơn định (Deterministic Finite Automata) DFS Tìm kiếm theo chiều sâu (Depth First Search.
- Bảng chuyển trạng thái của otomat.
- Bảng chuyển của otomat.
- Bảng chuyển của otomat  trong Ví dụ 1.12.
- Bảng chuyển của otomat đơn định M trong Ví dụ 1.12.
- Đồ thị chuyển trạng thái của otomat1.
- Đồ thị chuyển trạng thái của otomat.
- Độ trễ giải mã hữu hạn d.
- Nhãn của đƣờng đi giữa hai trạng thái kế tiếp cùng dạng.
- đƣợ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 ngôn ngữ hình thức và lý thuyết biểu diễn thông tin nói chung, mã trong mối quan hệ với đại số, tổ hợp trên từ, lý thuyết ngôn ngữ hình thức và otomat hữu hạn.
- Đề tài của luận văn “Thuật toán kiểm tra tính chất mã bằng otomat hữu hạn” có ý nghĩa thực tiễn và thời sự cao, có khả năng phát triển cả về mặt lý thuyết và ứng dụng trong thực tế.
- Phƣơng pháp nghiên cứu Sử dụng phƣơng pháp và công cụ của đại số, otomat hữu hạn, lý thuyết về otomat để làm công cụ và phƣơng tiện sử dụng nghiên cứu.
- Đóng góp mới của luận văn Luận văn trình bày việc ứng dụng lƣỡng cực hoá otomat hữu hạn đầu vào - 9 - cho bài toán kiểm định tính chất mã của ω-mã và Z-mã, có độ phức tạp thời gian cỡ (n3) với đầu vào là otomat hữu hạn đơn định và n là số trạng thái của otomat.
- Với tiếp cận phƣơng pháp sử dụng otomat vào bài toán kiểm định tính chất mã, đề xuất thuật toán tính toán độ trễ cho -mã, với đầu vào là otomat hữu hạn, trình bày phƣơng pháp kiểm định ω-mã và Z-mã, với đầu vào là otomat hữu hạn, đề xuất kết quả mở rộng phƣơng pháp tính toán độ trễ giải mã của H.N.Vinh-N.Đ.Hân-P.T.Huy (2010) đối với một ngôn ngữ từ định biên.
- Ở đó ta nhắc lại một số khái niệm trong otomat hữu hạn, otomat đa định, đơn định hữu hạn.
- các cách biểu diễn otomat đồng thời nêu một số thuật toán cơ bản trên otomat hữu hạn, các khái niệm trong đại số, lý thuyết mã, lý thuyết ngôn ngữ hình thức, đồ thị hữu hạn, ngôn ngữ, từ các phép toán trên từ và ngôn ngữ.
- Chương 2: Một số lớp mã và otomat Trình bày các định nghĩa về các lớp mã nhƣ mã (thông thƣờng), -mã, -mã, Z-mã cùng với tính chất đặc trƣng của chúng, nêu các khái niệm trong máy biến đổi và otomat hữu hạn, đồng thời nêu một số thuật toán đối với máy biến đổi.
- Chương 3: Kiểm định -mã, ω-mã và Z-mã Chƣơng này trình bày các kết quả về tính toán độ trễ giải mã cho -mã, phƣơng pháp kiểm định ω-mã và Z-mã, với đầu vào là otomat hữu hạn.
- Từ các đề xuất: ứng dụng lƣỡng cực hoá otomat hữu hạn đầu vào.
- GIỚI THIỆU VỀ OTOMAT VÀ ỨNG DỤNG Chƣơng thứ nhất trình bày các kiến thức cơ sở cần thiết, đƣợc sử dụng trong các chƣơng tiếp theo của luận văn.
- Một số khái niệm 1.1.1.
- Bảng chữ cái Tập A khác rỗng hữu hạn hay vô hạn các ký hiệu đƣợc gọi là bảng chữ cái.
- Mỗi phần tử a  A đƣợc gọi là một chữ cái hay một ký hiệu.
- Dƣới đây là các bảng chữ cái 1.
- Từ (Xâu) Giả sử có bảng chữ cái A = {a1, a2.
- Tổng số vị trí của các ký hiệu xuất hiện trong xâu w đƣợc gọi là độ dài của từ w và ký hiệu là  w.
- Xâu không có chữ cái nào đƣợc gọi là từ rỗng và đƣợc ký hiệu là.
- Nhƣ vậy từ rỗng là từ thuộc mọi bảng chữ cái.
- b1b2…bm đƣợc gọi là bằng nhau và đƣợc ký hiệu là.
- 11 - Nếu w là một từ trên bảng chữ cái A, và AB thì w là từ trên bảng chữ cái B.
- Tập tất cả các từ trên bảng chữ cái A đƣợc ký hiệu là A*, còn tập tất cả các từ khác rỗng trên bảng chữ cái A đƣợc ký hiệu là A+.
- Về cấu trúc đại số thì A* là một vị nhóm tự do sinh bởi A với đơn vị là từ rỗng.
- là các từ trên bảng chữ cái A = {0,1} 2.
- beautiful, happy, holiday là các từ trên bảng chữ cái B = {a,b,c,…,z}.
- Xâu z gọi là xâu con chung của hai xâu x và y nếu z vừa là dãy con của x và vừa là dãy con của y.
- Xâu con chung của hai xâu x, y có độ dài lớn nhất gọi là xâu con chung dài nhất (LCS) của x và y.
- Ký hiệu LCS(x, y), L(x, y) lần lƣợt là tập các LCS và độ dài LCS của hai xâu x và y.
- Cho xâu x,y trên bảng chữ cái A, |x| =m, |y.
- b1b2…bn trên bảng chữ cái A, tích ghép của hai từ  và  ký hiệu.
- là từ w trên bảng chữ cái A đƣợc xác định.
- Từ ngƣợc của từ  ký hiệu là wR nhận đƣợc bằng cách viết ngƣợc lại các ký hiệu của từ w.
- Tiền tố (Prefix) và hậu tố (Suffix): Nếu w = uv thì u đƣợc gọi là tiền tố của w và v là hậu tố của w.
- Ngôn ngữ Cho bảng chữ cái A, mỗi tập con X A* đƣợc gọi là một ngôn ngữ hình thức (hay ngôn ngữ) trên bảng chữ cái A.
- Tập rỗng, ký hiệu.
- là một ngôn ngữ không gồm một từ nào và đƣợc gọi là ngôn ngữ rỗng.
- Vậy ngôn ngữ rỗng là ngôn ngữ trên mọi bảng chữ cái.
- Chú ý rằng ngôn ngữ rỗng: X.
- là khác với ngôn ngữ chỉ gồm một từ rỗng: X.
- A* là ngôn ngữ gồm tất cả các từ trên A, còn A+ là ngôn ngữ gồm tất cả các từ khác rỗng trên A.
- a, b, abb, aab, bbb, abab}, X2 = {anbnn  N} là hai ngôn ngữ trên bảng chữ A = {a,b}, X1 là ngôn ngữ hữu hạn trong khi X2 là ngôn ngữ vô hạn.
- Các phép toán trên ngôn ngữ Ngôn ngữ là một tập hợp, do đó tất cả các phép toán trên tập hợp đều có thể áp dụng cho ngôn ngữ.
- Ngoài ra ngôn ngữ còn có một số phép toán quan trọng khác.
- Giả sử X và Y là các ngôn ngữ trên bảng chữ cái A.
- Vị nhóm Vị nhóm M là tập hợp, đƣợc trang bị phép toán hai ngôi có tính chất kết hợp và phần tử trung hoà.
- Phép toán hai ngôi thƣờng gọi là phép nhân.
- Phần tử trung hoà là duy nhất, thƣờng gọi là phần tử đơn vị và ký hiệu là 1.
- Vị nhóm M gọi là vị nhóm giao hoán nếu phép nhân có tính chất giao hoán.
- Với vị nhóm M bất kỳ, tập (M.
- tập các tập con của M cũng có cấu trúc vị nhóm với phép toán hai ngôi đƣợc định nghĩa nhƣ sau: XY = {xy | xX, yY}, với X, YM và phần tử đơn vị là tập {1}.
- Tập con NM gọi là vị nhóm con của vị nhóm M nếu tập N là đóng với phép toán trên M và chứa phần tử đơn vị của M (NNN và 1 N).
- Nếu  là đơn ánh, toàn ánh, song ánh thì ta lần lƣợt gọi  là đơn cấu, toàn cấu và đẳng cấu tƣơng tứng.
- ,0) là vị nhóm giao hoán cùng với phần tử đơn vị 0.
- ,1) là vị nhóm giao hoán cùng với phần tử đơn vị 1.
- Otomat hữu hạn Otomat hữu hạn là một mô hình toán học của hệ thống với sự mô tả bởi các input và output.
- Tại mỗi thời điểm, hệ thống có thể đƣợc xác định ở một trong số hữu hạn các cấu hình nội bộ gọi là các trạng thái (states).
- Mỗi trạng thái của hệ thống thể hiện sự tóm tắt các thông tin liên quan đến những input đã chuyển qua và xác định các phép chuyển kế tiếp trên dãy input tiếp theo.
- Một cách không hình thức, một otomat hữu hạn gồm một tập hợp các trạng thái và các điều khiển dịch chuyển từ trạng thái này sang trạng thái khác khi nhận dữ liệu vào.
- Lý thuyết về otomat hữu hạn thƣờng đƣợc dùng đến nhiều cho việc thiết kế các công cụ xử lý chuỗi hiệu quả.
- Lý do quan trọng nhất cho việc nghiên cứu các hệ thống trạng thái hữu hạn là tính tự nhiên của khái niệm và khả năng ứng dụng đa dạng trong nhiều lĩnh vực thực tế.
- Otomat hữu hạn đƣợc chia thành 2 loại: Otomat đơn định và otomat không đơn định hay còn gọi là otomat đa định.
- Cả hai loại otomat hữu hạn đều có khả năng nhận dạng chính xác tập chính quy.
- Otomat hữu hạn đơn định có khả năng nhận dạng ngôn ngữ dễ dàng hơn otomat hữu hạn đa định, nhƣng thay vào đó thông thƣờng kích thƣớc của nó lại lớn hơn so với otomat hữu hạn đa định tƣơng ứng.
- Otomat hữu hạn đa định Cho A là bảng chữ cái hữu hạn.
- Một otomat đa định hữu hạn trên A là một bộ 5 thành phần.
- Q là một tập hữu hạn khác rỗng, đƣợc gọi là tập các trạng thái, trong đó q0  Q đƣợc gọi là trạng thái khởi đầu.
- I  Q là tập các trạng thái khởi đầu + T  Q là tập các trạng thái kết thúc + E  Q × A × Q là tập các cung xác định hàm chuyển trạng thái của otomat.
- Khi đó, ta gọi là đƣờng đi từ trạng thái qi đến trạng thái qj với nhãn a và đƣợc biểu diễn là: jaiqq.
- Một đƣờng đi trong otomat  là một dãy các cung kế tiếp: trong đó n gọi là độ dài của đƣờng đi P, từ w = a1a2…an tạo thành bởi các nhãn ai đƣợc gọi là nhãn của đƣờng đi P.
- q0 là trạng thái bắt đầu của P, qn là trạng thái kết thúc của P.
- Ta ký hiệu: nwqqP 0: Quy ƣớc rằng qQ đƣờng đi từ q đến q có độ dài 0.
- Một đƣờng đi nqqP 0:đƣợc gọi là đƣờng đi thành công nếu q0I, qnT.
- Tập tất cả các đƣờng đi thành công của otomat  đƣợc ký hiệu là L.
- và đƣợc gọi là ngôn ngữ đoán nhận bởi.
- Một trạng thái qi Q đƣợc gọi là trạng thái đạt được nếu có một đƣờng đi nqqP 0: với q0I.
- Hàm chuyển trạng thái (hàm chuyển.
- Q × A*→ Q, gọi là hàm chuyển mở rộng của otomat

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt