Nửa nhóm và vị nhóm
Nửa nhóm S là một tập hợp có phép toán hai ngôi kết hợp, ký hiệu theo lối nhân Một nửa nhóm con T của S là tập con của S với phép toán cảm sinh, tạo thành nửa nhóm Nửa nhóm S được gọi là vị nhóm nếu tồn tại phần tử đơn vị, ký hiệu là S1 Vị nhóm con của S là nửa nhóm con chứa phần tử đơn vị của S.
Ví dụ 1.1 M = 0{ 1}, là vị nhóm nhân với phần tử đơn vị là 1
Ví dụ 1.2 Với vị nhóm M bất kỳ, ta tr ang bị cấu trúc vị nhóm cho tập tất cả các tập conP( )M của M bằng cách định nghĩa, vớiX, Y ⊂M,
Phần tử đơn vị là{ }1
Từ và ngôn ngữ
Ví dụ 1.3 Từ các vị nhóm M, N ta có vị nhóm M×N là tích trực tiếp củaM và
N M, ( ) n là tích trực tiếp của lần vị nhómn M.
Ánh xạ ϕ: S → T được gọi là đồng cấu nửa nhóm nếu với mọi a, b ∈ S, ϕ(ab) = ϕ(a)ϕ(b) và ϕ(1_S) = 1_T, trong đó 1_S và 1_T là đơn vị của nửa nhóm S và T Đồng cấu được xem là ϕ đơn cấu nếu nó là đơn ánh Một đồng cấu từ vị nhóm vào chính nó được gọi là tự đồng cấu.
Cho M là một vị nhóm Với x, y∈M, ta có x −1 y = {z∈M x.z| = }y và xy −1 = {z∈M x| =z.y}.
Với S, T ⊆M, ta định nghĩa các phép cắt trái, phải của bởiS T
Ta có tính chất cơ bản sau đây
Tính chất 1.1 Cho M là một vị nhóm, P, K ⊆ M, P = K ∗ và m ∈ M Khi đó
Chứng min h Chứng minh P −1 (m −1 K) ⊆(m.P) −1 K Ta có w∈P −1 (m −1 K) ⇔ ∃ ∈( p P, k ∈K w: =p −1 (m −1 k) ⇔k=m.p.w).
ChoA là một bảng chữ Một từ w trên bảng chữ A là một dãy hữu hạn các phần tử củaA w= (a 1 , a 2 , , a n ),a i ∈A.
Tập tất cả các từ trên bảng chữ Ađược ký hiệu là A ∗ và được trang bị phép nhân
(tích) ghép có tính chất kết hợp
10 1 CƠ SỞ LÝ THUYẾT MÃ
Để tiện lợi, ta ký hiệu w = a1a2 an thay cho w = (a1, a2, , an) Một phần tử a ∈ A được gọi là chữ cái rỗng, ký hiệu là ε, và đóng vai trò là phần tử đơn vị trong phép nhân ghép Tập hợp ε A* có cấu trúc vị nhóm, và A* được gọi là vị nhóm tự do trên A Tập hợp tất cả các từ không rỗng trên A được ký hiệu là A+ và được xác định là A+ = A* - {ε} Độ dài của từ w = a1a2 an được ký hiệu là |w|, với quy ước |ε| = 0 Ánh xạ w → |w| là một đồng cấu từ A* đến vị nhóm cộng Đối với N ≥ 0, ta ký hiệu
Một từ w ∈ A ∗ được coi là khúc con của từ x ∈ A ∗ nếu tồn tại các từ u, v ∈ A ∗ sao cho x = uwv Quan hệ “là một khúc con của” tạo thành một thứ tự bộ phận trên A ∗ Một khúc con w của x được gọi là khúc con thực sự nếu w khác x Từ w ∈ A ∗ cũng có thể là khúc đầu hoặc khúc đuôi của x nếu tồn tại một từ u ∈ A ∗ sao cho x = wu (hoặc x = uw) Quan hệ “là một khúc đầu của” và “là một khúc đuôi của” cũng xác lập thứ tự bộ phận trên A ∗ Chúng ta ký hiệu w ≤p x (và w ≤s x) khi w là khúc đầu (hoặc khúc đuôi) của x, và w
