Bộ giáo dục và đào tạo Trờng đại học vinh Nguyễn thị mỹ vinh nhóm con tối đại của một nửa nhóm và ngôn ngữ thử đợc địa phơng Luận văn thạc sĩ toán học Vinh - 2003 1 Bộ giáo dục và đào tạo Trờng đại học vinh Nguyễn thị mỹ vinh nhóm con tối đại của một nửa nhóm và ngôn ngữ thử đợc địa phơng Chuyên ngành : Đại số - Lý thuyết số Mã số : 1.01.03 Luận văn thạc sĩ toán học Ngời hớng dẫn khoa học: PGS -TS . Lê Quốc Hán Vinh - 2003 2 Mục lục Trang Mở đầu 4 Chơng 1. Nhóm con tối đại và tơng đẳng của các nửa nhóm 6 Đ1. Nhóm con tối đại của một nửa nhóm 6 Đ2. Tơng đẳng . Tơng đẳng Đuybrây và tơng đẳng Kroadô 8 Đ3. Nửa nhóm tự do 17 Chơng 2. Ngôn ngữ thử đợc địa phơng 20 Đ1. Ngôn ngữ phi ngữ cảnh 20 Đ2. Ngôn ngữ thử đợc địa phơng 25 Kết luận 33 Tài liệu tham khảo 34 Mở đầu 3 Nghiên cứu, tìm hiểu về lý thuyết ngôn ngữ hình thức là một điều thú vị, nó thực sự hấp dẫn nhiều ngời làm toán vì bằng công cụ đại số ngời ta đã đa đ- ợc những kết quả có ứng dụng trong thực tiễn - một điều không phải bao giờ cũng thực hiện đợc . Trong [1], [5], [6], [7] các tác giả đã nghiên cứu các ngôn ngữ hình thức mà vị nhóm cú pháp của nó là một nhóm và đã thu đợc một số kết quả đáng quan tâm Trong luận văn này, chúng tôi khảo sát một lớp ngôn ngữ thử đợc địa ph- ơng, đó là ngôn ngữ mà vị nhóm cú pháp của nó không phải là nhóm và các nhóm con tối đại của vị nhóm cú pháp là tầm thờng và thu đợc nhiều kết quả đáng chú ý về dáng điệu ngôn ngữ , vị nhóm cú pháp , ôtômát tối tiểu đoán nhận ngôn ngữ đó . Luận văn gồm : Phần mở đầu, Chơng 1, Chơng 2 và Phần kết luận . Chơng 1 : Trình bày những kiến thức cơ bản về lý thuyết nhóm con tối đại và lý thuyết tơng đẳng trên nửa nhóm để làm cơ sở cho việc trình bày các chơng sau . Trong tiết 1, chúng tôi đa ra các kết quả về nhóm con tối đại của nửa nhóm với các kết quả đáng chú ý trong mệnh đề 1.1 và mệnh đề 1.2 . Trong tiết 2 chúng tôi nhắc các kiến thức liên quan đến tơng đẳng và ngôn ngữ hình thức là tơng đẳng Đuybrây và tơng đẳng Kroadô( Định nghĩa 1.8 và định nghĩa 1.19). Tiết 3 trình bày các vấn đề liên quan đến nửa nhóm tự do, với kết quả đáng lu ý là tiêu chuẩn để một nửa nhóm con của nửa nhóm tự do là nửa nhóm tự do ( Mệnh đề 1.35). Trong chơng 2 : Tiết 1 chúng tôi nêu những tính chất đáng chú ý về ôtômát - văn phạm và vị nhóm của ngôn ngữ hình thức tổng quát và lớp ngôn ngữ phi ngữ cảnh( Xem định nghĩa 2.14), đồng thời nêu đợc mối liên hệ giữa lớp ngôn ngữ chính qui và lớp ngôn ngữ phi ngữ cảnh ( Mệnh đề 2.15) . Tiết 2 nghiên cứu về ngôn ngữ thử đợc địa phơng trên 3 phơng diện : Dáng điệu ngôn ngữ, vị nhóm cú pháp , và ôtômát tối tiểu đoán nhận ngôn ngữ đó (thể hiện chủ 4 yếu trong định lý 2.17). Việc khảo sát văn phạm của lớp ngôn ngữ này là một bài toán mở mà sẽ có nhiều hứa hẹn . Một phần kết quả đó là Ngôn ngữ thử đ ợc địa phơng đã gửi đăng trong Tạp chí khoa học của Đại học Vinh. Các ký hiệu dùng trong luận văn là ký hiệu thông thờng và các kết quả trình bày theo thứ tự chơng thứ tự kết quả . Ví dụ định lý 1.3 là chơng 1, định lý thứ 3. Luận văn đợc hoàn thành dới sự hớng dẫn tận tâm, nhiệt tình của thầy giáo PGS - TS. Lê Quốc Hán . Nhân dịp này, tác giả xin đợc bày tỏ lòng biết ơn sâu sắc đến Thầy - ng- ời đã đặt bài toán và dành cho tác giả sự giúp đỡ tận tình, chu đáo . Tác giả cũng rất biết ơn PGS. Ngô Sỹ Tùng, TS .Nguyễn Thành Quang, GS Nguyễn Quốc Thi , PGS Nguyễn Quý Di, các thầy giáo, cô giáo trong tổ Đại số đã giúp đỡ động viên, chỉ bảo tác giả hoàn thành luận văn này . Cũng nhân dịp này, tác giả xin gửi lời cảm ơn tới Ban giám hiệu nhà tr- ờng , Ban chủ nhiệm khoa Toán, khoa Sau Đại học và các phòng ban liên quan đã tạo điều kiện cho tác giả trong thời gian học tập và nghiên cứu tại trờng Đại học Vinh. Tác giả rất mong nhận đợc sự góp ý chỉ bảo của các thầy cô giáo và các bạn . Vinh, tháng 11/2003 Tác giả Chơng I. 5 nhóm con tối đại và tơng đẳng của các nửa nhóm Đ1.Nhóm con tối đại trong nửa nhóm Giả sử S là một nửa nhóm với phần tử đơn vị 1. Nếu p và q là các phần tử thuộc S sao cho pq=1, thì ta gọi p là nghịch đảo bên trái của q , còn q là nghịch đảo bên phải của p.( Ta bỏ từ đối với 1 ) Phần tử khả nghịch bên phải [trái] thuộc S đợc định nghĩa là phần tử thuộc S có một nghịch đảo bên phải [ trái] thuộc S . Vậy nếu pq=1 thì p khả nghịch bên phải , còn q khả nghịch bên trái , phần tử khả nghịch thuộc S là một phần tử vừa khả nghịch bên trái vừa khả nghịch bên phải . Mệnh đề 1.1 Giả sử S là một nửa nhóm với phần tử đơn vị 1 . i) Tập P |Q| tất cả các phần tử khả nghịch bên phải |trái| của S là một nửa nhóm con với luật giản ớc phải | trái | và chứa 1. ii) Tập U tất cả các phần tử khả nghịch thuộc S là một nhóm con của S và U = P Q. Mỗi phần tử khả nghịch có một phần tử nghịch đảo hai phía duy nhất thuộc U và không có nghịch đảo bên trái và bên phải nào thuộc tập đó . iii) Mỗi nhóm con của S chứa 1 đều đợc chứa trong U. Chứng minh : i) Nếu pq = pq = 1 thì (pp)(qq) =1; điều đó chứng tỏ rằng P và Q là các nửa nhóm con của nửa nhóm S . Rõ ràng chúng chứa 1 . Nếu ap = bp, trong đó a, b S và pP, thì P có nghịch đảo bên phải q, và a=a1=apq = bpq = b1 = b . Tơng tự Q là nửa nhóm với luật giản ớc bên trái . ii) Hiển nhiên U= P Q và vì vậy U là nửa nhóm con của nửa nhóm S. Nếu uU thì tồn tại các phần tử x, yS sao cho xu=uy=1 . Giả sử x và y là các phần tử tuỳ ý nh vậy thuộc S . Thế thì x = x1 = xuy = 1y = y . Do đó mọi phần tử nghịch đảo bên trái của u bằng phần tử nghịch đảo bên phải tuỳ ý , và vì vậy u có phần tử nghịch đảo hai 6 phía duy nhất u và không có các phần tử nghịch đảo bên phải và bên trái khác . Từ các đẳng thức uu = uu = 1 suy ra uU, thành thử U là một nhóm . iii) Giả sử G là một nhóm con tuỳ ý của nửa nhóm S, chứa 1 và aG. Giả sử a -1 là phần tử nghịch đảo của a thuộc G . Từ các đẳng thức aa - 1 = a -1 a = 1 suy ra aU, vì vậy G U. Một nửa nhóm không phải bao giờ cũng chứa các nhóm con . Chẳng hạn, nửa nhóm xiclic vô hạn không chứa nhóm con nào . Dễ thấy rằng nửa nhóm S chứa nhóm con trong và chỉ trong trờng hợp nó chứa một luỹ đẳng . Nếu e là một luỹ đẳng của một nửa nhóm S thì eS gồm tất cả các phần tử a thuộc S nhận e làm đơn vị trái , tức là ea = a. Thật vậy, nếu a= ex với x nào đó thuộc S, thì ea = e 2 x = ex = a. Mệnh đề đảo là hiển nhiên . Tơng tự , Se gồm tất cả các phần tử thuộc nửa nhóm S nhận e làm đơn vị phải và eSe là tập tất cả các phần tử thuộc nửa nhóm S nhận e làm đơn vị hai phía . Dễ thấy rằng eSe = eS Se. Ngoài ra, eS [Se] là iđêan chính phải [ trái] của nửa nhóm S , sinh bởi e . Đặc biệt eS và Se là các nửa nhóm con của nửa nhóm S và do đó giao eSe của chúng cũng là nửa nhóm con . Hơn nữa , eSe có đơn vị e , vì vậy ta có thể nói về nhóm các phần tử khả nghịch trong nửa nhóm eSe , nhóm đó ta kí hiệu là H e . Mệnh đề 1.2 Giả sử e là một luỹ đẳng tuỳ ý của nửa nhóm S và H e là nhóm các phần tử khả nghịch trong nửa nhóm eSe . Thế thì H e chứa mỗi nhóm con G của nửa nhóm S, mà G giao với H e . Chứng minh : Giả sử f là đơn vị của nhóm G. Trớc hết ta chứng tỏ rằng f = e. Theo giả thiết G H . Giả sử a là một phần tử thuộc giao đó . Nếu b và e là các phần tử nghịch đảo của a tơng ứng trong các nhóm G và H e thì : e = ea = eaf = eab = ab = f. Vì e là đơn vị hai phía của G, từ đó suy ra G eSe, theo mệnh đề 1.1(iii) ta kết luận G H. 7 Nhóm con G của nửa nhóm S đợc gọi là nhóm con tối đại của S , nếu nó không đợc chứa thực sự trong một nhóm con nào khác của S . Nếu e là đơn vị của nhóm con tối đại G của nửa nhóm S , thì G giao với H e vì eG H e . Từ đó, theo mệnh đề 1.2 ta có G H e nhng khi đó G = H e do tính tối đại của G. Đảo lại nếu e là luỹ đẳng của nửa nhóm S thì từ mệnh đề 1.2 ta suy ra rằng H e là nhóm con tối đại của S. Nh vậy, các nhóm H e trong mệnh đề 1.2 và chỉ có chúng là các nhóm con tối đại của nửa nhóm S . Từ mệnh đề 1.2 cũng suy ra rằng , nếu e và f là các luỹ đẳng khác nhau của nửa nhóm S, thì H e và H f không giao nhau . Ta có thể tởng tợng các nhóm con tối đại của nửa nhóm S nh các đảo trong biển cả . Đ2.Tơng đẳng . Tơng đẳng Đuybrây và tơng đẳng Kroadô trên nửa nhóm Tiết này, ta nhắc lại định nghĩa tơng đẳng, nửa nhóm thơng, định lý về đồng cấu, định nghĩa tơng đẳng Đuybrây, tơng đẳng Kroadô cùng các định lý khác. Định nghĩa 1.3. Ta nói quan hệ trên nửa nhóm S là ổn định bên phải (trái) nếu a b (a,bS) kéo theo ac bc ( ca cb) với mỗi cS . Một quan hệ tơng đơng ổn định bên phải ( trái ) ta sẽ gọi là tơng đẳng bên phải ( bên trái ) trên S . Tơng đẳng trên S là quan hệ tơng đơng vừa là tơng đẳng bên trái, vừa là t- ơng đẳng bên phải . Định nghĩa 1.4. Giả sử là một tơng đẳng trên nửa nhóm S và A, B là các phần tử tuỳ ý thuộc S/ , tức là các lớp tơng đơng của S theo mod Giả sử a 1 ,a 2 A, b 1 ,b 2 B Từ a 1 a 2 a 1 b 1 a 2 b 1 vì ổn định bên phải Từ b 1 b 2 a 2 b 1 a 2 b 2 vì ổn định bên trái . Theo tính chất bắc cầu của tơng đẳng ta kết luận a 1 b 1 a 2 b 2 . Do vậy, tích AB của lớp A và lớp B đợc chứa trong một lớp tơng đơng C nào đó. 8 Ta định nghĩa phép ( 0 ) trong S/ bằng cách đặt A o B = C. Tập S/ với phép toán ( o ) là một nửa nhóm mà ta gọi là nửa nhóm thơng của S theo mod. Ta ký hiệu a (aS) là lớp tơng đơng theo mod chứa a. Vì vậy : a o b = (ab) với a,bS. Nếu ký hiệu là ánh xạ tự nhiên từ nửa nhóm S lên S/ ta đợc a =(a) với aS và vì vậy (a) o (b) = (ab). Vậy là đồng cấu. Ta gọi là đồng cấu tự nhiên (hay chính tắc) từ nửa nhóm S lên nửa nhóm thơng S/ . Các lý luận trên chứng tỏ rằng mỗi nửa nhóm thơng của nửa nhóm S là một ảnh đồng cấu của nó . Định lý sau đây chứng tỏ rằng, đảo lại, mỗi ảnh đồng cấu của nửa nhóm S đẳng cấu với một nửa nhóm thơng nào đó của nó . Định lý 1.5. Giả sử là một đồng cấu từ nửa nhóm S lên nửa nhóm S và giả sử = -1 o tức là a b (a, b S) (a) = (b) . Thế thì là một tơng đẳng trên S và tồn tại đẳng cấu từ nửa nhóm S/ lên S sao cho = , trong đó là đồng cấu tự nhiên từ S lên S/ . Chứng minh : Nếu a b và cS thì :(ac) = (a)(c) = (b)(c) = (bc), từ đó ac bc. Tơng tự ca cb . Mà hiển nhiên là một quan hệ tơng đơng trên S nên nó là tơng đẳng . Đối với mỗi phần tử AS/ , ta đặt (A) = (a 1 ) trong đó a 1 A . Để chứng tỏ là một ánh xạ ( từ S/ vào S ) ta chú ý rằng nếu a 2 A thì a 1 a 2 và do đó (a 1 ) = (a 2 ) vì là ánh xạ S lên S nên là ánh xạ S/ lên S. Ta chứng tỏ là đồng cấu . Giả sử A,B S/ và aA, bB Thế thì abA o B do vậy (A o B) = (ab) = (a)(b) = (A)(B). là ánh xạ một - một . Thật vậy giả sử (A) = (B) và ta lấy aA, bB . Thế thì (a) = (A) = (B) = (b) . Từ đó ab và vì vậy a=b Vậy là đẳng cấu từ S/ lên S. 9 Nếu aAS/ thì (a) = A . Thành thử (a) = (A) = [(a)] =()(a) . Điều này đúng với mọi aS nên ta kết luận = . Định lý 1.6. ( Định lý về đồng cấu cảm sinh ) Giả sử 1 , 2 là các đồng cấu từ nửa nhóm S tơng ứng lên các nửa nhóm S 1 , S 2 sao cho 1 -1 o 1 2 -1 o 2 . Thế thì tồn tại một đồng cấu duy nhất từ nửa nhóm S 1 , lên nửa nhóm S 2 sao cho 1 = 2 . Chứng minh: Giả sử a 1 S 1 và a là một phần tử thuộc nửa nhóm S sao cho 1 (a) = a 1 . Đặt (a 1 ) = 2 (a), nếu 1 (b) = a 1 , (bS) thì (a,b) 1 -1 o 1 2 -1 o 2 suy ra (a,b) 2 - 1 o 2 . Từ đó 2 (a) = 2 (b) thành thử là một ánh xạ ( đơn trị ) . Hiển nhiên 1 = 2 . Ta chứng tỏ là đồng cấu : [ 1 (a) 1 (b)] = [ 1 (ab)] = 2 (ab) = 2 (a) 2 (b) = [ 1 (a)] [ 1 (b)] Tính duy nhất của là hiển nhiên . Thật vậy, nếu thỏa mãn hệ thức 1 = 2 thì buộc phải xác định nh đã làm ở trên . Hệ quả 1.7. [2] Nếu 1 , 2 là các tơng đẳng trên nửa nhóm S sao cho 1 2 thì S/ 1 S/ 2 Định nghĩa 1.8. Giả sử S là một nửa nhóm tuỳ ý và H là một tập con của S , với a S ( a tuỳ ý ) ta định nghĩa a [-1] H và Ha [-1] nh sau : a [-1] H = {xS | axH} Ha [-1] = {xS | xaH} Ta định nghĩa quan hệ 2 ngôi H nh sau : H = {(a,b) S ì S | a [-1] H = b [-1] H} và H * = {(a,b) S ì S | a [-1] H = b [-1] H } H là một tơng đẳng phải trên S , gọi là tơng đẳng phải chính trên S xác định bởi tập H hay còn gọi là tơng đẳng Đuybrây . * H là tơng đẳng phải bộ phận trên S mà ta còn gọi là tơng đẳng phải bộ phận chính trên S xác định bởi tập H. Bằng cách đối ngẫu , một tơng đẳng trái chính trên S xác định bởi tập H cho bởi công thức H = {(a,b) S ì S | Ha [-1] = Hb [-1] }. Định nghĩa 1.9. Đặt W H = {x S | x [-1] H=}. Khi đó W H gọi là thặng d phải 10 . ta một đặc trng đối xứng của các nửa nhóm con của một nửa nhóm tự do . Mệnh đề 1.35 : Nửa nhóm con T của một nửa nhóm tự do S là một nửa nhóm tự do khi và. 1. Nhóm con tối đại và tơng đẳng của các nửa nhóm 6 Đ1. Nhóm con tối đại của một nửa nhóm 6 Đ2. Tơng đẳng . Tơng đẳng Đuybrây và tơng đẳng Kroadô 8 Đ3. Nửa