Ngôn ngữ từ vô hạn và mã

- Nguyễn Thị Tý Ngôn Ngữ từ vô hạn và mã LUẬN VĂN THẠC SĨ KHOA HỌC NGÀNH CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: TS.
- 7 1.1.2 Đồng cấu.
- 8 1.1.3 Từ và ngôn ngữ.
- 10 1.2 Ngôn ngữ chính quy và Otomat hữu hạn.
- 11 1.2.1 Ngôn ngữ chính quy.
- 21 2.1.1 Mã và vị nhóm tự do.
- 41 3.1 Từ và ngôn ngữ từ vô hạn.
- 42 3.3 Thuật toán kiểm định ω-mã trên ngôn ngữ.
- 43 3.4 Thuật toán kiểm định ω-mã trên vị nhóm.
- Ngôn ngữ có độ trễ giải mã hữu hạn d.
- Cho đến nay, qua công trình tổng quan của Augros và Litovsky về các thuật toán kiểm định ω-mã, thuật toán tốt nhất kiểm định một ngôn ngữ chính quy X cho trước có là ω-mã có độ phức tạp thời gian 𝒪(n3) với n là cỡ của vị nhóm các phép chuyển dịch của otomat đơn định tối tiểu đoán nhận X.
- Trong luận văn này, với vị nhóm hữu hạn M bất kỳ thỏa X (vị nhóm các phép chuyển dịch nói trên chỉ là một trường hợp riêng), ta đề xuất một thuật toán mới sử dụng M để kiểm định X có là ω-mã không với độ phức tạp thời gian chỉ là 𝒪(n2).
- Cụ thể sẽ nhắc lại một số khái niệm về cấu trúc đại số cơ bản, đồng cấu, từ và ngôn ngữ.
- ngôn ngữ chính quy và otomat hữu hạn.
- Chương 2: Mã của các từ hữu hạn Chương này trình bày một số khái niệm và tính chất cơ bản của mã bao gồm mã và vị nhóm tự do, thủ tục kiểm tra tính chất mã, mối quan hệ giữa lý thuyết mã với đại số, thuật toán Sardinas - Patterson cải tiến để kiểm tra tính chất mã của ngôn ngữ chính quy, độ trễ giải mã.
- Chương 3: Mã của các từ vô hạn Chương 3 trình bày các khái niệm về từ và ngôn ngữ từ vô hạn, ω- mã, thuật toán kiểm định ω-mã trên ngôn ngữ, thuật toán kiểm định ω-mã trên vị nhóm, thuật toán kiểm định ω-mã trên đồ thị.
- Cụ thể sẽ nhắc lại một số khái niệm và tính chất cơ bản của đại số, ngôn ngữ hình thức và otomat.
- 1.1 Một số khái niệm 1.1.1 Cấu trúc đại số cơ bản Cho M là một tập.
- Một phép toán hai ngôi trên M là một ánh xạ T : M × M  M.
- 8 - Một tập khác rỗng M được gọi là vị nhóm nếu M là một nửa nhóm và có phần tử đơn vị.
- Vị nhóm con của M là tập con N, đóng kín đối với phép toán của M và chứa phần tử đơn vị của M , nghĩa là NN  N và 1M N.
- Một phần tử x của vị nhóm M được gọi là khả nghịch nếu tồn tại phần tử x.
- Một vị nhóm được gọi là nhóm nếu mỗi phần tử của nó đều khả nghịch.
- 1.1.2 Đồng cấu Một cách tổng quát, một đồng cấu giữa hai cấu trúc đại số là một ánh xạ bảo toàn các phép toán.
- Nghĩa là, một đồng cấu nửa nhóm là một ánh xạ  từ một nửa nhóm M vào một nửa nhóm N sao cho m1, m2 M (m1m2.
- (m1)(m2) Nếu M = N thì đồng cấu  gọi là tự đồng cấu.
- Nếu  là đơn ánh (t.ứng, toàn ánh, song ánh) thì gọi là đơn cấu (t.ứng, toàn cấu, đẳng cấu), một tự đồng cấu song ánh gọi là một tự đẳng cấu.
- Tương tự, một đồng cấu vị nhóm là một ánh xạ  từ một vị nhóm M vào một vị nhóm N thỏa mãn điều kiện trên và (1M.
- Đặc biệt, khi hai nửa nhóm M, N là nhóm thì mọi đồng cấu nửa nhóm từ M đến N là đồng cấu vị nhóm và là đồng cấu nhóm từ M đến N.
- Một đồng cấu.
- M  N là một đẳng cấu nếu tồn tại một đồng cấu.
- 9 - Một tương đẳng trên một vị nhóm M là một quan hệ tương đương θ trên M sao cho với mọi m, m.
- M  N là một đồng cấu vị nhóm thì quan hệ (hạt nhân.
- (m) là một tương đẳng trên M.
- Ngược lại, nếu θ là một tương đẳng trên vị nhóm M, tập thương M/θ với phép toán [x ]θ[y ]θ = [xy ]θ, ở đó [x ]θ ký hiệu lớp tương đương theo θ chứa x, là một vị nhóm thương của M với tương đẳng θ và ta có đồng cấu tự nhiên θ♮: M  M/θ cho bởi θ♮(m.
- Cho M là một vị nhóm.
- Ta có tính chất cơ bản sau đây Tính chất 1.1.1 (xem [3]) Cho M là một vị nhóm, P, K  M, P = K* và m  M.
- Ta có w  P−1(m−1K.
- Ta có w  (m.P)−1K  (p  P, k  K : w = (m.p)−1k  k = m.p.w).
- 10 - 1.1.3 Từ và ngôn ngữ Cho tập hợp các ký tự A gọi là bảng chữ cái.
- Một từ w trên A là một xâu hữu hạn các phần tử của A, w = (a1, a2.
- Một ngôn ngữ (hình thức) L là một tập hợp các từ của bảng chữ cái A nào đó.
- Do đó, ta có thể viết: w = a1a2.
- an) Mỗi phần tử a A được gọi là một chữ cái.
- Vì vậy, tập A* được trang bị cấu trúc của một vị nhóm và được gọi là vị nhóm tự do sinh bởi A.
- Do đó, ta có: A.
- Khi đó: aaAww Ta nói, từ w A* là một khúc con (factor) của một từ x A* nếu u, v  A* sao cho: x = uwv.
- Một từ w A* là một khúc đầu (prefix) của một từ x A* nếu v A* sao cho: x = wv.
- Tương tự, một từ w A* là một khúc đuôi (suffix) của một từ x A* nếu u A* sao cho: x = uw.
- 11 - Một phân tích của một từ w A* là một dãy {u1, u2.
- Với X  A*, ta biểu diễn X* là vị nhóm con sinh bởi X, với đơn vị là.
- xn  n  1, xi X } Vì vậy, ta có Giả sử X và Y là các ngôn ngữ trên A.
- Ta gọi thương trái (thương phải) của X với Y là ngôn ngữ Y–1X (tương ứng XY–1) được xác định bởi: Y–1X = {w A.
- 1.2 Ngôn ngữ chính quy và Otomat hữu hạn 1.2.1 Ngôn ngữ chính quy Cho A là bảng chữ cái hữu hạn.
- được gọi là các biểu thức sơ cấp trên A.
- Các biểu thức chính quy trên A là các biểu thức được định nghĩa đệ quy như sau.
- Các biểu thức sơ cấp trên A là các biểu thức chính quy trên A, X.
- Nếu E1 và E2 là các biểu thức chính quy trên A, thì các biểu thức E1 + E2, E1.E2 và E1* là các biểu thức chính quy.
- Nói cách khác, một biểu thức trên A được gọi là biểu thức chính quy nếu nó được xây dựng từ các biểu thức sơ cấp bằng cách dùng một số hữu hạn lần các phép toán hợp, phép tích ghép và phép lặp.
- Một ngôn ngữ chính quy trên A được biểu diễn bởi một biểu thức chính quy E trên A, ký hiệu L(E), được định nghĩa đệ quy như sau.
- Nếu E1 biểu diễn ngôn ngữ L1, E2 biểu diễn ngôn ngữ L2 thì L(E1+ E2.
- Ta nói rằng ngôn ngữ được định nghĩa L(E) như trên là giá trị của biểu thức chính quy E.
- Do đó, mỗi tập dạng {w}, w A*, là ngôn ngữ chính quy trên A.
- Như vậy, tập hợp các ngôn ngữ được biểu diễn bởi các biểu thức chính quy trên A trùng với tập hợp các ngôn ngữ chính quy khác rỗng trên A.
- Khi đó, ta có.
- Một ngôn ngữ chính quy là vô hạn khi và chỉ khi biểu thức chính quy biểu diễn nó có chứa phép lặp.
- Mọi tập hữu hạn các từ trong A* đều là các ngôn ngữ chính quy trên A.
- Như vậy từ định nghĩa suy ra: lớp các ngôn ngữ chính quy trên A là lớp bé nhất chứa các ngôn ngữ hữu hạn và ngôn ngữ trống, đóng đối với các phép hợp, phép tích ghép và phép lặp.
- Biểu diễn đại số của ngôn ngữ chính quy: Cho.
- M là đồng cấu vị nhóm (ta có thể xem đồng cấu vị nhóm  là toàn cấu vì nếu không thì ta thay M bởi vị nhóm con (A*) của M).
- L thì ta nói rằng L thỏa bởi đồng cấu vị nhóm.
- Vậy L thỏa bởi đồng cấu.
- Cho X, Y  A* là các ngôn ngữ.
- Ta thiết lập bổ đề kỹ thuật sau đây về tính thỏa được làm cơ sở xây dựng các thuật toán trên vị nhóm trong các chương tiếp theo.
- M là một toàn cấu vị nhóm thỏa X và Y và giả sử X = h−1(K.
- Thật vậy, với mọi w  X Y ta có h(w.
- Thật vậy, với mọi w  h−1(K L), ta có h(w.
- T và X = h−1(K ) ta có K.
- ta có h(w.
- Ta có.
- Y và ta có w  (X+)−1Y.
- Ta có tính chất sau: Định lý 1.2.2.
- (xem [11]) Cho L  A*, L là ngôn ngữ chính quy khi và chỉ khi L thỏa bởi một đồng cấu vị nhóm.
- M, với M là một vị nhóm hữu hạn.
- Khi đó, vị nhóm hữu hạn M được gọi là vị nhóm biểu diễn ngôn ngữ L.
- Từ định nghĩa của đồng cấu và định nghĩa của ngôn ngữ chính quy, ta có một số kết quả sau: Mệnh đề 1.2.2.
- Cho X, Y  A* là hai ngôn ngữ chính quy, và hai đồng cấu vị nhóm.
- Khi đó, ta luôn xây dựng được một đồng cấu (toàn cấu) vị nhóm.
- P, với P là một vị nhóm hữu hạn, thỏa đồng thời cả X và Y.
- Từ đó ta có thể viết: (C.
- Cho vị nhóm U với phần tử đơn vị là 1 và phần tử zero là 0 và cho ngôn ngữ X thỏa bởi một đồng cấu vị nhóm.
- M , ngôn ngữ Y.
- thỏa bởi đồng cấu vị nhóm.
- Khi đó, P là vị nhóm được sinh bởi (u), u A*.
- Cho X, Y  A* là hai ngôn ngữ chính quy.
- Nếu X và Y cùng thỏa bởi toàn cấu vị nhóm.
- P, với P là một vị nhóm hữu hạn, thì  cũng thỏa mọi L (X,Y), trong đó (X,Y) là lớp ngôn ngữ sinh bởi X, Y nhờ sử dụng hữu hạn các phép.
- Với mọi x X  Y, ta có (x) C hoặc (x) D.
- thỏa ngôn ngữ X  Y.
- Do đó  thỏa ngôn ngữ X–1Y

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