Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Cao đẳng - Đại học Sư phạm Luận văn một số vấn đề về tính không lặp trong tổ hợp trền từ...

Tài liệu Luận văn một số vấn đề về tính không lặp trong tổ hợp trền từ

.PDF
49
78
109

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 NGUYỄN THỊ HUỆ MỘT SỐ VẤN ĐỀ VỀ TÍNH KHÔNG LẶP TRONG TỔ HỢP TRÊN TỪ LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán Ứng dụng HÀ NỘI - 2018 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 NGUYỄN THỊ HUỆ MỘT SỐ VẤN ĐỀ VỀ TÍNH KHÔNG LẶP TRONG TỔ HỢP TRÊN TỪ LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán Ứng dụng Mã số: 8 46 01 12 Người hướng dẫn khoa học: TS.TRẦN VĨNH ĐỨC HÀ NỘI - 2018 Lời cảm ơn Luận văn được hoàn thành tại trường Đại học sư phạm Hà Nội 2 dưới sự hướng dẫn của TS. Trần Vĩnh Đức. Tác giả xin bày tỏ lòng biết ơn sâu sắc tới TS Trần Vĩnh Đức. Thầy đã tận tình hướng dẫn và giải đáp những thắc mắc, giúp đỡ tác giả hoàn thành luận văn này. Tác giả xin chân thành cảm ơn tới các thầy cô giáo phòng Sau đại học, các thầy cô giáo khoa Toán cũng như các thầy cô giáo giảng dạy lớp thạc sĩ K20 chuyên ngành Toán Ứng dụng trường Đại học Sư phạm Hà Nội 2 đã đem hết tâm huyết và sự nhiệt tình để giảng dạy, trang bị cho tác giả nhiều kiến thức cơ sở và giúp đỡ tác giả trong suốt quá trình học tập. Tác giả xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè, đồng nghiệp đã luôn quan tâm, động viên và tạo mọi điều kiện thuận lợi cho tác giả trong quá trình học tập và hoàn thành luận văn. Hà Nội, ngày 25 tháng 10 năm 2018 Tác giả Nguyễn Thị Huệ 1 Lời cam đoan Tôi xin cam đoan, dưới sự hướng dẫn của TS. Trần Vĩnh Đức, luận văn thạc sĩ chuyên ngành Toán ứng dụng với đề tài " Một số vấn đề về tính không lặp trong tổ hợp trên từ " được hoàn thành bởi chính sự nhận thức của bản thân tác giả. Trong suốt quá trình nghiên cứu thực hiện luận văn, tác giả đã kế thừa những thành tựu của các nhà khoa học với sự trân trọng và biết ơn. Hà Nội, ngày 25 tháng 10 năm 2018 Tác giả Nguyễn Thị Huệ 2 Mục lục Lời cảm ơn 1 Lời cam đoan 2 MỞ ĐẦU 3 Chương 1 Từ và ngôn ngữ 1.1 Định nghĩa và tính chất cơ bản . . . . . . . . . . . . . . . . . . . . . 1.2 Các tính chất cơ bản của từ . . . . . . . . . . . . . . . . . . . . . . . 6 6 9 Chương 2 Phương trình từ 2.1 Định nghĩa phương trình từ . . . . . . . . . . . . . . . . . . . . . . . 2.2 Tính chất cơ bản của phương trình từ . . . . . . . . . . . . . . . . . . 2.3 Một số phương pháp giải phương trình từ . . . . . . . . . . . . . . . 16 16 17 17 Chương 3 Từ không lặp 3.1 Định nghĩa từ lặp, từ không lặp . . . . . . . . . . . . . . 3.2 Từ vô hạn 2+ -free trên một bảng chữ cái gồm hai chữ cái 3.3 Từ vô hạn 2-free trên bảng chữ cái gồm ba chữ cái . . . 3.4 Một vài kết quả của từ không lặp bình phương . . . . . . 26 26 27 30 40 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Tài liệu tham khảo 45 Phụ lục 45 Python code 45 3 MỞ ĐẦU 1. Lý do chọn đề tài Tổ hợp trên các từ có liên hệ với nhiều lĩnh vực của toán học hiện đại cũng như với khoa học máy tính. Các kết quả của tổ hợp trên từ có nhiều ứng dụng trong nhiều lĩnh vực khác nhau như: Lôgic, Số học, Nửa nhóm, Otomat,... Một trong những nghiên cứu quan trọng của tổ hợp trên từ là tính lặp của từ. Bài báo quan trọng đầu tiên về tổ hợp trên các từ là bài báo của A.Thue vào đầu thế kỉ 20. Năm 1906, A.Thue đã giới thiệu bài báo cáo về các từ không lặp bình phương. Trong suốt 70 năm sau đó, ngày càng có nhiều người quan tâm đến từ không lặp bình phương và những từ không lặp nói chung. Một số ví dụ về ứng dụng của tính lặp trên từ được chỉ ra dưới đây. Đầu tiên, người ta quan sát thấy rằng từ vô hạn square-free, overlap-free, cube-free thực sự như những ví dụ điển hình hoặc phản ví dụ cho một số trường hợp và trong nhiều lĩnh vực khác nhau. Trong động lực học chúng được Morse giới thiệu vào năm 1921. Sau đó, một số người khác sử dụng cho lý thuyết nhóm. Người ta cũng đề cập đến ứng dụng cho ngôn ngữ hình thức: Đó là Brzozowski và Gabrillian sử dụng từ không lặp cho ngôn ngữ hình thức. J.Goldstine cũng sử dụng dãy từ Morse để chỉ ra tính chất bao hàm của một số ngôn ngữ. Trong luận văn này, với tên gọi: Một số vấn đề về tính không lặp trong tổ hợp trên từ, luận văn sẽ làm chi tiết hơn cho người đọc hai kết quả quan trọng của Thue, đó là: 1. Tồn tại từ (dài) vô hạn 2+ - free trên một bảng chữ cái gồm hai chữ cái, và 2. Tồn tại từ (dài) vô hạn 2 - free trên một bảng chữ cái gồm ba chữ cái. Và sau đó, luận văn cũng sẽ đưa ra một vài kết quả thú vị gần đây liên quan đến từ không lặp bình phương. 2. Mục đích nghiên cứu • Tìm hiểu các kết quả quan trọng của tổ hợp trên từ. • Đưa ra một số ứng dụng của từ không lặp. 3. Nhiệm vụ nghiên cứu Nghiên cứu khái niệm, tính chất của từ, đưa ra một số phương pháp để giải phương trình từ, làm rõ cho người đọc hai kết quả quan trọng trên từ của Thue về từ không 4 lặp và đưa ra một số kết quả thú vị gần đây liên quan đến tính chất lặp của từ. 4. Đối tượng và phạm vi nghiên cứu • Đối tượng nghiên cứu: Từ không lặp trong tổ hợp trên từ. • Phạm vi nghiên cứu: - Nghiên cứu về từ và những tính chất cơ bản của từ - Nghiên cứu những tính chất cơ bản của phương trình từ - Nghiên cứu về từ không lặp của Thue. - Nghiên cứu những kết quả gần đây của các từ không lặp bình phương 5. Phương pháp nghiên cứu • Đọc và tổng hợp tài liệu về tổ hợp trên từ. • Những kết quả đưa ra gần đây của tổ hợp trên từ. 6. Những đóng góp của luận văn Hệ thống hóa và chi tiết hơn các khái niệm, tính chất của từ. Luận văn sẽ làm rõ hơn hai kết quả quan trọng của A.Thue về từ không lặp. Và đưa ra một số kết quả thú vị gần đây liên quan đến tính chất lặp của từ. 5 Chương 1 Từ và ngôn ngữ 1.1 Định nghĩa và tính chất cơ bản Mục này trình bày một số định nghĩa và tính chất cần thiết cho các chương sau. Tài liệu tham khảo chính là [1]. Bảng chữ cái A là một tập hữu hạn khác rỗng, các phần tử của bảng chữ được gọi là ký tự hoặc chữ cái. Ví dụ bảng chữ cái A = {a, b}. Một từ trên bảng chữ cái A là một dãy ký tự lấy từ A. Ví dụ dãy w = (a, b, a, a, b) là một từ trên bảng chữ A = {a, b}. Thông thường ta bỏ qua dấu ngoặc và các dấu phảy cho gọn. Ví dụ, từ w = (a, b, a, a, b) được viết là w = abaab. Từ có thể hữu hạn hoặc vô hạn (sang bên phải). Từ có độ dài vô hạn được gọi là ω-từ. Số chữ cái trong từ w được gọi là độ dài của w và viết là |w|. Số chữ a trong từ w được ký hiệu là P |w|a . Dễ thấy |w| = a∈A |w|a . Từ có độ dài 0 được gọi là từ rỗng và ký hiệu là 1. Ta ký hiệu A∗ , A+ và Aω tương ứng là tập mọi từ hữu hạn, tập mọi từ hữu hạn khác rỗng, tập mọi từ vô hạn trên bảng chữ A. Ví dụ, với A = {a, b}, ta có A∗ = {1, a, b, aa, ab, ba, bb, aaa, aab, . . . } Xét hai từ u và v trên bảng chữ A, ta định nghĩa phép ghép hay tích của u và v là từ w thu được bằng cách viết liên tiếp dãy u trước, sau đó đến dãy v. Cụ thể, với u = a1 a2 . . . an và v = b1 b2 . . . bm từ w là w = a1 . . . an b1 . . . bm . Rõ ràng, phép toán ghép · này có tính kết hợp và từ rỗng là đơn vị của phép toán này. Do đó, (A∗ , ·) và (A+ , ·) tương ứng có cấu trúc vị nhóm và cấu trúc nửa nhóm. Hơn nữa, hai cấu trúc này là tự do theo nghĩa sau đây. Một nửa nhóm (hoặc vị nhóm) S được gọi là tự do nếu nó có một tập hợp con B sao cho mỗi phần của S có thể được biểu diễn duy nhất như là tích của các phần tử trong B. Tập B này được gọi là tập sinh tự do của S, hoặc một cơ sở của S. 6 Cho w, u ∈ A∗ , a ∈ A và L, K ⊂ A∗ . Một từ u là một thừa số của w (tương ứng thừa số trái/tiền tố, thừa số phải/hậu tố) nếu tồn tại các từ x và y thỏa mãn w = xuy (tương ứng w = uy, w = xu). Chúng được gọi là thừa số thực sự nếu chúng khác w. Ta viết u ≤ w (u < w) biểu thị rằng u là một tiền tố (tiền tố thực sự) của w. Tập tất cả các tiền tố của w được ký hiệu là pref(w), prefk (w) là tập tiền tố của w có độ dài k. Tương tự, ta có ký hiệu tương ứng cho tập hậu tố là suf(w) và sufk (w). Nếu u ≤ w tồn tại duy nhất một y sao cho w = uy. Ở đây y được gọi là thương trái của w bởi u và nó được ký hiệu là u−1 w. Trong trường hợp này u không phải là tiền tố của w, u−1 w là không xác định, vì vậy hàm số (u, w) 7→ u−1 w trở thành xác định một phần. Tương tự ta có định nghĩa cho thương phải của wu−1 . Nếu w = a1 . . . an trong đó ai ∈ A thì phép lấy ngược của w được viết là: R w = an . . . a1 . Một phân tích của một từ w là một dãy bất kỳ các từ u1 , . . . , un sao cho w = u1 . . . un . (1.1) (1.1) là L-phân tích nếu tất cả ui ∈ L. Ta ký hiệu L∗ = {u1 . . . un |n ≥ 0, ui ∈ L}, L+ = {u1 . . . un |n ≥ 1, ui ∈ L}. Tập L∗ và L+ tướng ứng là các vị nhóm con và nửa nhóm con của A∗ , chúng còn được gọi là vị nhóm con và nửa nhóm con sinh ra bởi L. Chú ý rằng với mỗi w trong L∗ có ít nhất một L-phân tích, và nếu phân tích đó là duy nhất thì L∗ được gọi là tập tự do và L là cơ sở. Ở đây L được gọi là một code. Phân tích được mô tả bởi hình sau đây: hoặc Hình sau nghĩa là w = xz = zy = ztz. 7 Hai từ x và y là hai từ liên hợp nếu tồn tại các từ u và v thỏa mãn x = uv và y = vu, hoặc tương tự, chúng có quan hệ với nhau qua một phép hoán vị vòng c : A∗ → A∗ được định nghĩa như sau:  c(1) c(w) =1 + = pref−1 1 (w)wpref1 (w) với w ∈ A , tức là x = ck (y) với một giá trị k nào đó. Chú ý rằng ở hình thứ 2 trang 2 x và y là hai từ liên hợp. Ta ký hiệu quan hệ của phép liên hợp bởi ∼; đây rõ ràng là một quan hệ tương đương. Đặt w = a1 . . . an với ai ∈ A. Số p là một chu kỳ của w nếu ai = ai+p , i = 1, . . . , n − p. Để minh họa cho chu kì ta có hình vẽ sau đây: trong đó u = prefp (w). Chu kỳ nhỏ nhất được ký hiệu bởi p(x). Các phần tử trong lớp liên hợp của prefp(w) (w) được gọi là nghiệm vòng của w. Ví dụ 1: Một từ có thể có nhiều chu kỳ. Ví dụ như từ abababa và aabaabbaabaa có các chu kỳ tương ứng là 2, 4, 6 và 7, 10, 11. Hơn nữa, bất kỳ một số lớn hơn hoặc bằng độ dài của w cũng luôn là một chu kỳ của w. Một từ w 6= 1 được gọi là từ nguyên thủy nếu nó không phải là lũy thừa với số mũ nguyên thực sự (khác 1) của bất kỳ nghiệm vòng nào của w. Sau đây, ta sẽ đi trình bày một số tính chất cơ bản của từ. Một đồng cấu h : A∗ → B ∗ (hoặc A+ → B + ) là ánh xạ h : A∗ → B ∗ (hoặc A+ → B + ) thỏa mãn: h(ww0 ) = h(w)h(w0 ), ∀w, w0 ∈ A∗ . Từ định nghĩa, ta có: • h(1) = 1 và • h là hoàn toàn xác định bởi các từ h(a), a ∈ A. Đồng cấu h được gọi là: • 1-free nếu h(a) 6= 1 với mọi a ∈ A, 8 • Tuần hoàn nếu ∃z thỏa mãn h(a) ∈ z ∗ với mọi a ∈ A, • Đẳng cấu nếu |h(a)| = |h(b)| với mọi a, b ∈ A, • Tiền tố ( hoặc hậu tố) nếu không một từ nào trong h(A) là một tiền tố ( hoặc hậu tố) của một từ khác, • Mã nếu h là đơn ánh. 1.2 Các tính chất cơ bản của từ Đầu tiên, ta sẽ nêu ra tính chất của từ nguyên thủy Định lý 1.1. Một từ w ∈ A+ là từ nguyên thủy khi và chỉ khi nó thỏa mãn ∀z ∈ A∗ : [w = z n ⇒ n = 1 và do đó w = z]. (1.2) Chứng minh. Rõ ràng, từ (1.2) ta suy ra w là từ nguyên thủy. Ta cần phải chứng minh chiều ngược lại. Gọi w là từ nguyên thủy và w = z n với n ≥ 2. Đặt r = prefp(w) (w). Trường hợp này có thể được minh họa như sau: Vì |r| là chu kỳ của w, |z| ≥ |r|. Hơn nữa, do w là từ nguyên thủy nên ta có z∈ / r∗ . Do vậy, so sánh tiền tố có độ dài là |r| của hai lần xuất hiện đầu tiên của z ta có thể viết r = ps = sp với p, s 6= 1. Từ Định lý 3 (ta sẽ đưa ra sau) ta có p và s là các lũy thừa của một từ khác rỗng, điều này mâu thuẫn với |r| là chu kỳ nhỏ nhất của w. Chú ý: Ta thường dùng điều kiện (1.2) để định nghĩa một từ nguyên thủy. Tồn tại hai lớp quan trọng các từ nguyên thủy, đó là từ unbordered và Lyndon. Một từ được gọi là từ unbordered nếu chu kỳ nhỏ nhất của nó bằng độ dài của từ đó. Nói một cách khác, w không có bất kỳ một từ khác rỗng nào vừa là tiền tố và hậu tố. Một từ được gọi là từ bordered nếu nó không phải là từ unbordered. Lưu ý rằng, một từ bordered có thể trùng với thừa số của một từ khác. Điều này không thể xảy ra với từ unbordered. 9 Ví dụ 2: Ta đưa ra một xây dựng đơn giản về cách một từ bất kỳ được tạo bởi ít nhất hai chữ cái có thể được mở rộng thành một từ unbordered. Xét một từ w, ta đặt u = wab|w| , trong đó a = pref1 (w) và b 6= a. Ta có minh họa như sau: Do cách chọn của a và b, mà ta có: - Không một hậu tố khác rỗng nào của u với độ dài nhỏ hơn hoặc bằng độ dài của w là một tiền tố của u; - Không một tiền tố nào của u với độ dài lớn hơn hoặc bằng độ dài của w là một hậu tố của u. Do đó u là từ unbordered. Từ Lyndon là những từ nguyên thủy nhỏ nhất trong lớp liên hợp theo thứ tự từ điển. Ta vừa xây dựng các thuật ngữ. Bây giờ ta sẽ đưa ra các kết quả tổ hợp cơ bản của từ. Định lý 1.2. Nếu các từ u, w, x và y trong A thỏa mãn uw = xy, thì tồn tại duy nhất một từ t thỏa mãn một trong các điều kiện sau i. u = xt và y = tw, hoặc ii. x = ut và w = ty. Chứng minh. Do tính đối xứng, ta có thể giả sử |u| ≥ |x|. Khi đó vì uw và xy là cùng một từ trong A, x là một tiền tố của u, tức là tồn tại t thỏa mãn u = xt. Hơn nữa, t là duy nhất nên ta có xy = uw = xtw. Mặt khác, đây là đơn vị của từ, vì vậy y = tw. Do vậy (i) đúng. Kết quả tiếp theo ta sẽ phân loại khi nào hai từ là giao hoán với nhau. Định lý 1.3. Cho u, v ∈ A∗ . Các điều kiện sau đây là tương đương: i. u và v là hai từ giao hoán, tức là uv = vu, ii. u và v thỏa mãn một quan hệ không tầm thường, iii. Tồn tại một từ t thỏa mãn u, v ∈ t∗ . 10 Chứng minh. Định lý là hiển nhiên nếu u hoặc v là rỗng. Vì vậy, ta giả sử u và v khác rỗng. (i) ⇒ (ii) Hiển nhiên, vì uv = vu là một quan hệ không tầm thường của u và v. (ii) ⇒ (iii) Áp dụng quy nạp theo |u| + |v|. Ta giả sử |u| ≥ |v|; trường hợp khác được chứng minh tương tự. Nếu |u| = |v| = 1, ra dễ dàng suy ra điều phải chứng minh. Bây giờ ta chọn α = β là một quan hệ không tầm thường của u và v, tức là α, β ∈ {u, v}+ và chúng là hai từ khác nhau trên {u, v}, nhưng α = β trong A∗ . (1.3) Vì α và β là hai từ khác nhau trên {u, v} nên ta có thể giả sử rằng α = uα1 và β = vβ1 với α1 , β1 ∈ {u, v}∗ (có thể ta phải xóa bỏ những tiền tố giống nhau của α và β (trong {u, v}∗ )). Từ (1.3) và Định lý 1.2, tồn tại một từ w sao cho u = vw. (1.4) Nếu w = 1 ta có điều phải chứng minh. Vì vậy, ta giả sử w 6= 1. Gọi α2 và β2 là những từ trên {v, w} thu được từ α và β bằng cách thay thế mỗi lần xuất hiện của u bởi vw. Khi đó, α2 và β2 là hai từ khác nhau trên {v, w} vì α2 bắt đầu bằng vw và β2 bắt đầu bằng vv. Mặt khác, rõ ràng là α2 = β2 trong A∗ , và vì |v| + |w| < |u| + |v| nên ta áp dụng giả thiết quy nạp và có được: tồn tại một từ t thỏa mãn v, w ∈ t∗ . Nhưng từ (1.4), điều tương tự cũng đúng cho u và v. Từ đó ta suy ra (iii) đúng. (iii) ⇒ (i) là điều hiển nhiên. Định lý 1.3 dẫn đến hai hệ quả thú vị sau. Hệ quả đầu tiên là một trường hợp của Định lý 1.3. Hệ quả 1.2.1. u, w ∈ A∗ là hai từ giao hoán khi và chỉ khi chúng là lũy thừa của cùng một từ. Hệ quả tiếp theo cho ta biểu diễn của từ. Hệ quả 1.2.2. Với mỗi w ∈ A+ tồn tại duy nhất một từ nguyên thủy ρ(w) thỏa mãn w = ρ(w)n với giá trị n ≥ 1 nào đó. Chứng minh. Từ Định lý 1.1 ta có tồn tại ít nhất một số n thỏa mãn w = ρ(w)n . Nếu w không phải là từ nguyên thủy ta viết w = z n với n ≥ 2. Nếu z không phải là từ nguyên thủy, ta lặp lại quá trình này đến khi tìm được ρ(w) thỏa mãn. Để chứng minh tính duy nhất ta giả sử ρ1 và ρ2 là hai từ nguyên thủy và w = n ρ1 = ρm 2 với n, m ≥ 1. Khi đó, ρ1 và ρ2 thỏa mãn một biểu thức không tầm thường, và vì vậy áp dụng Định lý 1.3 ta có ρ1 và ρ2 là các lũy thừa của cùng một từ. Nhưng từ Định lý 1.1, một từ nguyên thủy là lũy thừa của một từ chỉ khi m = n = 1. Do đó, ρ1 = ρ2 và ta có Hệ quả 2. 11 Từ ρ(w) trong Hệ quả 2 được gọi là căn nguyên thủy của w, và n là số mũ của w. Ví dụ 3: Một từ nguyên thủy ρ không thể là một thừa số của ρ2 theo một cách không tầm thường, tức là, nếu ρ2 = uρv thì ta cần u = 1 hoặc v = 1. Ta giả sử ngược lại: ρ2 = uρv với u, v 6= 1. Gọi p và s là những từ thỏa mãn us = ρ = pv. Điều này được minh họa bằng hình sau đây: Ta có uρv = ρρ = uspv, hoặc tương đương ρ = sp. Mặt khác, ρ có một tiền tố p và một hậu tố s, vì vậy ta có ρ = ps. Do đó ps = ρ = sp và từ Định lý 1.3 p và s là lũy thừa của cùng một từ, từ đó ρ = z n , với n ≥ 2; điều này là vô lý vì ρ là từ nguyên thủy. Trong Định lý 1.3 chúng ta đã phân loại từ hoán vị. Tiếp theo, ta phân loại khi nào hai từ là liên hợp với nhau. Định lý 1.4. Gọi u, v ∈ A+ . Khi đó các điều kiện sau là tương đương i. u và v là hai từ liên hợp, ii. Tồn tại một từ z thỏa mãn uz = zv, iii. Tồn tại các từ z, p và q thỏa mãn u = pq, v = qp, và z ∈ p(qp)∗ . Chứng minh. Hiển nhiên điều kiện (i) và (iii) tương đương. Vì vậy, ta chỉ cần chứng minh (ii) và (iii) tương đương. (iii) ⇒ (ii). Nếu u = pq, v = qp và y = p(qp)n với n ≥ 0 thì uz = pqp(qp)n = p(qp)n+1 p = p(qp)n qp = zv. (ii) ⇒ (iii). Giả sử uz = zv, khi đó với mọi n un z = un−1 uz = un−1 zv GTQN zv n−1 v = zv n . = Chọn n thỏa mãn n|u| ≥ |z| > (n − 1)|u|, và ta xét phương trình un z = zv n . 12 (1.5) Từ Định lý 1.2, z = un−1 p và zq = un với một từ p, q nào đó . Ta có un = zq = un−1 pq, (5a) thỏa mãn u = pq, do đó từ (1.5) và (5a) , v n = qz = q(pq)n−1 p = (pq)n , vì vậy v = qp. Chú ý, trong Định lý 1.4 ta có quan hệ liên hợp được phân loại theo hai cách sau: • Các phương trình trong (ii), và • Nghiệm của một phương trình trong (iii). Tiếp theo, ta chứng minh kết quả tuần hoàn cơ bản của từ và nó còn được gọi là Bổ đề tuần hoàn của Fine và Wilf (Periodicity Lemma of Fine and Wilf). Định lý 1.5. (Fine và Wilf, 1956) Cho u, v ∈ A+ . Khi đó các từ u và v là các lũy thừa của cùng một từ khi và chỉ khi uω và v ω có chung một tiền tố với độ dài |u| + |v| − gcd(|u|, |v|). Chứng minh. Trước tiên, ta chứng minh cho trường hợp gcd(|u|, |v|) = 1. Nếu gcd(|u|, |v|) 6= 1, |u| = dp và |v| = dq với gcd(p, q) = 1, coi u và v như là các phần tử của (Ad )+ , tức là trên bảng chữ cái Ad , trong đó các chữ cái là từ với độ dài d trong bảng chữ cái ban đầu. Trong bảng chữ cái rộng hơn, gcd(|u|, |v|) = 1, và nếu ta có thể chứng minh định lý trong trường hợp này thì ta có thể suy ra trong trường hợp tổng quát. Vì vậy, ta giả sử rằng |u| = p và |v| = q với gcd(p, q) = 1. Một chiều là hiển nhiên. Để chứng minh chiều ngược lại ta giả sử uω và v ω có một tiền tố chung với độ dài p + q − 1. Do tính đối xứng, ta cũng có thể giả sử p > q, ta có minh họa cho chứng minh bằng hình vẽ sau đây. 13 Ở đây, p và q ký hiệu cho độ dài của các từ u và v, vị trí của các từ uω và v ω được đánh số từ 1, . . . , p + q − 1. Đường nét đứt cho ta vị trí có thể được so sánh được của các từ uω và v ω . Cuối cùng, mũi tên miêu quá quá trình được định nghĩa như sau Mục đích của quá trình này là cố định các giá trị của vị trí mới sao cho nó giống như là giá trị đã cho của vị trí ban đầu i0 ∈ [1, . . . , q − 1]. Từ giả thiết ta có giá trị của vị trí được tính như sau: i0 7→ i0 + p 7→ i1 ≡ i0 + p (mod q), (1.6) trong đó i1 được giảm đến khoảng [1, . . . , q], và có cùng giá trị với i0 . Vì vậy, ta có quá trình tính i1 từ i0 . Vì gcd(p, q) = 1 nên i1 6= i0 . Nếu nó cũng khác với q thì ta sẽ lặp lại quá trình này và vị trí mới thu được là khác với vị trí trước đó. Thật vậy, nếu i0 + np ≡ i0 + mp(mod q), n, m ∈ [0, q − 1], thì ta cần n = m, vì gcd(p, q) = 1. Nếu quá trình này có thể được lặp lại q − 1 lần thì tất các cả vị trí trong miền màu xám sẽ được phủ và vì vậy có cùng giá trị với giá trị ban đầu trên i0 . Nhưng điều đó có nghĩa là v thuộc bảng chữ cái đơn phân, vì vậy u cũng như vậy và ta sẽ có điều phải chứng minh. Nhưng quá trình có thể được lặp lại q − 1 lần nếu ta chọn i0 thỏa mãn i0 + (q − 1)p ≡ q (mod q). (1.7) Trong trường hợp này tất cả các giá trị i0 + jp (mod q) với j = 0, . . . , q − 2 là khác q, và đây là điều kiện để ta có thể áp dụng quá trình. Rõ ràng giá trị i0 thỏa mãn phương trình (1.7) tồn tại. Hệ quả 1.2.3. Nếu một từ có hai chu kỳ p và q và nếu nó có độ dài ít nhất p + q− gcd(p, q) thì có cũng có chu kỳ gcd(p, q). Định lý 1.5 chỉ ra rằng hai từ là tuần hoàn tính từ ngoài cùng bên trái. Định lý này cũng có thể phát biểu khác đi: Một từ có một thừa số có hai biểu diễn tuần hoàn. Để phát biểu điều này ta ký hiệu l(u, v) là độ dài của thừa số chung lớn nhất của hai từ u và v. Khi đó ta có thể phát biểu Định lý 1.5 như sau: Hệ quả 1.2.4. Với bất kỳ hai từ u, v ∈ A+ ta có l(uω , v ω ) ≥ |u| + |v| − gcd(|u|, |v|) ⇒ ρ(u) ∼ ρ(v). Chứng minh. Giả thiết được minh họa như sau 14 trong đó |z| ≥ |u| + |v| − gcd(|u|, |v|). Rõ ràng, tồn tại liên hợp tương ứng u1 và v1 của u và v thỏa mãn z ≤ uω1 , v1ω . Vì vậy, từ Định lý 1.5, u1 và v1 là các lũy thừa của cùng một từ, gọi là t, vì vậy chúng cũng là các lũy thừa của từ nguyên thủy ρ(t) = ρ. Vì vậy, từ Hệ quả 2, ρ(u1 ) = ρ(v1 ) = ρ. Để chứng minh hệ quả trên ta cần mệnh đề sau đây: Mệnh đề: Nếu x là một từ nguyên thủy và x0 ∼ x, thì x0 cũng là một từ nguyên thủy. Ta có chứng minh của mệnh đề như sau. Nếu x0 = sn thì c(x0 ) = (c(s))n , trong đó c là hoán vị vòng trong trang 4, vì vậy, c(x0 ) cũng là một lũy thừa bậc n. Vì vậy x cũng như thế. Từ ban đầu ta có: u1 = ρn và v1 = ρm . Vì vậy, với cùng một lý luận như trong chứng minh mệnh đề ta có u = ρn1 , v = ρm 2 , trong đó ρ1 ∼ ρ ∼ ρ2 . Từ Mệnh đề ta có ρ1 và ρ2 là nguyên thủy và ρ(u) = ρ1 ∼ ρ2 = ρ(v). 15 Chương 2 Phương trình từ 2.1 Định nghĩa phương trình từ Trong chương này ta xét các khái niệm và những tính chất cơ bản của phương trình từ, trên cơ sở đó sẽ đưa ra một số phương pháp giải phương trình từ. Ta có một số thuật ngữ sau. Gọi A là một bảng chữ cái hữu hạn và X là một tập các biến (ẩn) với A ∩ X = ∅. Một phương trình (với X là tập các biến trên A) là một cặp (u, v) ∈ (A ∪ X)∗ × (A ∪ X)∗ , thường viết là u = v. Một nghiệm của phương trình u = v là một đồng cấu h : (X ∪ A)∗ → A∗ thỏa mãn h(u) = h(v) và h(a) = a, a ∈ A, tức là, xác định u và v. Tập tất cả các nghiệm của phương trình u = v được ký hiệu bởi Sol(u = v). Rõ ràng ký hiệu này mở rộng theo một cách tự nhiên (không nhất thiết phải hữu hạn) đến hệ phương trình. Ở trên ta cho phép phương trình bao gồm các hằng số. Một phương trình u = v là hằng số tự do nếu u, v ∈ X ∗ . Gọi E và E 0 là hai hệ phương trình (có cùng tập hữu hạn các ẩn). Ta nói E và E 0 là tương đương nếu Sol(E) = Sol(E 0 ). Hơn nữa, ta nói E là độc lập nếu với mỗi u = v ∈ E tồn tại môt nghiệm h thuộc Sol(u = v)\Sol(E\{u = v}). Cuối cùng, ta nói phương trình u = v là rút gọn nếu pref1 (u) 6= pref1 (v) và last1 (u) 6= last1 (v). Chú ý rằng nghiệm của phương trình là một |X|-véctơ trên A. Do vậy ta đang giải các phương trình trên vị nhóm tự do A∗ . Tuy nhiên đôi khi ta cũng quan tâm đến giải các phương trình này trên một nửa nhóm tự do A+ , tức là, ta cần h là một 1-free. Ví dụ 1. Xét phương trình e1 : xy = yx và e2 : xxyyxx = yyxyxyy. 16 Từ Định lý 1.3, cả hai phương trình chỉ có duy nhất nghiệm tuần hoàn, tức là x, y ∈ t∗ với một t nào đó. Tuy nhiên chúng không tương đương vì Sol(e1 ) = {(tn , tm )|t ∈ A∗ ; n, m ≥ 0}, Sol(e2 ) = {(t3n , t2n )|t ∈ A∗ ; n ≥ 0}. Ví dụ 2. Các phương trình xz = zy và xz 2 = z 2 x là tương đương. Điều này được suy ra từ chứng minh của Định lý 1.4 . 2.2 Tính chất cơ bản của phương trình từ Ta biết rằng phương trình có thể được sử dụng để phân loại các tính chất của từ: x ∈ (ab)∗ ⇔ xab = abx x và y giao hoán ⇔ xy = yx  x = pq, x và y liên hợp ⇔ xz = zy ⇔ y = qp. Trên cơ sở tính chất của từ, ta có thể đưa ra một số phương pháp giải phương trình từ như sau 2.3 Một số phương pháp giải phương trình từ I. Phương pháp độ dài. So sánh độ dài của các vế của một phương trình (hoặc của một hệ phương trình) ta có một phương trình tuyến tính (hoặc một hệ phương trình tuyến tính), điều này cho ta các nghiệm potential. Nghiệm của e2 trong Ví dụ 1 là một minh họa cho phương pháp này. Đôi khi phương pháp độ dài được sử dụng trong tiền tố hoặc hậu tố của phương trình: xyyx = uvvu ⇔  xy = uv, yx = vu. Thật vậy, ở đây vị trí giữa của hai vế có thể được tìm ra bằng phương pháp độ dài và nửa đầu tiên của phương trình phải trùng nhau. II. Tách phương trình. Đôi khi phương trình có thể được tách ra thành nhiều phương trình. Tiêu chuẩn để tách thường dựa trên phương pháp độ dài, nhưng đôi khi cũng là match những từ đã biết. Ví dụ, nếu ta biết rằng • x là từ unbordered, và • uxv = yxz với |u|, |v|, |y|, |z| ≤ |x|, 17 khi đó ta cần u = y và v = z. III. Khử ẩn số ngoài cùng Phương pháp này được sử dụng nhiều và nó dựa trên Định lý 1.1: Nếu ta có xα = yβ trong đó α, β ∈ {X ∪ A}∗ , ta viết x = yt(hoặc y = xt), thay nó vào phương trình ban đầu ta được ytα = yβ ⇔ tα = β. Ở đây ta hy vọng phương trình mới sẽ đơn giản hơn, và từ đó tìm ra nghiệm. Tuy nhiên điều này không phải lúc nào cũng đúng vì khi ta thay x vào tất cả các vị trí trong α và β thì tổng độ dài của phương trình có thể tăng lên. Phương pháp này cũng là phương pháp đổi biến X: X 7→ X ∪ {t}\{x}. IV. Sử dụng phương trình đã biết. Phương pháp II và III dẫn đến một phương trình mới, ở đó nghiệm có thể đã biết. Những phương trình cơ bản này là giao hoán xy = yx, hoặc liên hợp xz = zy, hoặc sử dụng Định lý Fine và Wilf để đưa ra kết luận về chu kỳ.  xy = uv Ví dụ 3: Xét cặp  trong trang trước. Phương pháp III cho ta có được yx = vu x = ut (hoặc u = tx) điều này dẫn đến v = ty và yut = tyu. Điều kiện thứ hai nghĩa là t và yu giao hoán, tức là, ta có thể viết t = (αβ)k , y = (αβ)i α và u = β(αβ)j , trong đó α, β ∈ A∗ và i, j, k ≥ 0. Điều này dẫn đến nghiệm tổng quát   x       = β(αβ)j+k   u      = β(αβ)j y = (αβ)i α hoặc v = (αβ)k+i α   x       = β(αβ)j   u      = β(αβ)j+k y = (αβ)i+k α , v = (αβ)i α trong đó i, j, k ≥ 0 và α, β ∈ A∗ . Ở đây nghiệm thứ hai nhận được từ tính đối xứng. 18
- Xem thêm -

Tài liệu liên quan

Tài liệu vừa đăng