CHƯƠNG 1 MỘT SỐ KHÁI NIỆM CƠ SỞ Chương này trình bày các khái niệm cơ sở sẽ được sử dụng và kế thừa trong luận án như quan hệ hai ngôi, quan hệ thứ tự [3], otomat, ngôn ngữ, các phép toán trên ngôn ngữ và thuật toán trên otomat truyền thống [25]. Những khái niệm này sẽ được định nghĩa mở rộng cho phù hợp với mô hình otomat khoảng và phát triển các thuật toán tương ứng cũng như các ứng dụng trên mô hình otomat khoảng trong các chương sau của luận án. Quan hệ hai ngôi Định nghĩa 1. Giả sử X và Y là những tập hợp.
Một quan hệ hai ngôi từ X đến Y là một bộ phận R của tích Đề các X × Y, tức là R ⊆ X × Y. Với hai phần tử a ∈ X và b ∈ Y, ta nói a có quan hệ R với b nếu và chỉ nếu cặp ( a, b) ∈ R. Ta viết aRb. Cho quan hệ hai ngôi R từ X đến X (gọi là quan hệ hai ngôi trên X).
- Quan hệ R là phản xạ nếu ∀ a ∈ X : aRa. - Quan hệ R là đối xứng nếu ∀ a, b ∈ X, aRb ⇒ bRa. Quan hệ R là phản đối xứng nếu ∀ a, b ∈ X : aRb, bRa ⇒ a = b. - Quan hệ R là bắc cầu nếu ∀ a, b, c ∈ X : aRb, bRc ⇒ aRc.
- Quan hệ R là tương đương nếu R là phản xạ, đối xứng và bắc cầu. Khi đó R thường được ký hiệu là ∼. - Quan hệ R là quan hệ thứ tự nếu R là phản xạ, phản đối xứng và bắc cầu.1: Ánh xạ Nếu R là quan hệ thứ tự và ∀ a, b ∈ X : aRb hoặc bRa thì R là quan hệ thứ tự đầy đủ (toàn phần), trái lại thì nó chỉ là quan hệ thứ tự bộ phận. Nếu R là quan hệ thứ tự thì nó thường được ký hiệu là ≤.
Người ta viết a < b nghĩa là a ≤ b và a 6= b để thể hiện quan hệ thứ tự chặt. Tập S với quan hệ thứ tự ≤ mà với mọi phần tử của S đều có thể so sánh được với nhau thì S được gọi là một dàn theo quan hệ ≤. Để phục vụ cho việc thực hiện các tính toán trên tập hợp, ta định nghĩa các khái niệm ánh xạ và phép toán như sau: Định nghĩa 1. [2, 3] Giả sử X và Y là những tập hợp và f là một quan hệ hai ngôi trên tích Đề các X × Y.
Khi đó f được gọi là một ánh xạ nếu Dom( f ) = X. Lúc đó ta nói đã xác định một ánh xạ f từ X vào Y, viết là f : X → Y và phần tử y ký hiệu là f ( x ) lấy từ cặp ( x, y) ∈ f. Ta gọi phép toán hai ngôi (hay gọi tắt là phép toán) trên tập X là một ánh xạ f : X × X → X. Giá trị f ( x, y) của f tại ( x, y) được gọi là cái hợp thành của x và y.
Cái hợp thành của x và y thường được ký hiệu bằng cách viết x và y theo một thứ tự nhất định với một dấu đặc trưng phép toán đặt ở giữa x và y. Trong các dấu hay dùng nhiều nhất là + (viết theo lối cộng) và. Khi viết theo lối nhân, người ta thường bỏ qua dấu ., xy được hiểu là x.y nếu không gây nhầm lẫn. Trong chương này, nếu x, y ∈ S và S được trang bị phép toán hai ngôi viết theo lối nhân thì dấu phép toán cũng sẽ bị bỏ qua.
- Quan hệ = (bằng) trên tập số nguyên Z là quan hệ phản xạ, đối xứng và bắc cầu nên nó là quan hệ tương đương. - Quan hệ ≤ trên tập số nguyên Z là quan hệ bắc cầu vì ∀ a, b, c ∈ Z, a ≤ b, b ≤ c thì a ≤ c; phản đối xứng vì a ≤ b, b ≤ a suy ra a = b. Do a ≤ a là đúng nên ≤ phản xạ, đồng thời ≤ cũng là một quan hệ thứ tự đầy đủ do với ∀ a, b ∈ Z, ta đều có a ≤ b (đọc là a nhỏ hơn b) hoặc b ≤ a (đọc là b nhỏ hơn a). - Do mọi phần tử trong Z đều so sánh được theo quan hệ ≤ nên (Z, ≤) là một dàn.
Một tính chất quan trọng của quan hệ tương đương xác định trên một tập là nó chia tập đó thành các lớp tương đương. Lớp tương đương này gồm các tập khác rỗng, rời nhau và trong mỗi tập đó chỉ gồm các phần tử có quan hệ tương đương với nhau, đồng thời chúng không có quan hệ tương đương với các phần tử ở các tập khác (còn gọi là một phân hoạch). Nếu R là một quan hệ tương đương trên X và a ∈ X thì tập hợp C ( a) = { x ∈ X | xRa} được gọi là lớp tương đương của a đối với quan hệ tương đương R. Nhận thấy: • Do R là phản xạ nên a ∈ C ( a), tức là C ( a) 6= ∅.
• Do R là bắc cầu nên x, y ∈ C ( a) thì xRy. • Do R là đối xứng nên x ∈ C ( a) và yRx thì y ∈ C ( a) hay ∀ a, b ∈ X, C ( a) = C (b) hoặc C ( a) ∩ C (b) = ∅. Quan hệ modulo m (chia lấy phần dư cho m), ký hiệu bởi ≡m , trên tập số nguyên Z là một quan hệ tương đương do: - Phản xạ: i ≡m i. Đồng thời ≡m tạo ra m lớp tương đương: [0] = {.
Chỉ số của một quan hệ tương đương trên một tập là số lớp tương đương trong phân hoạch mà quan hệ tương đương đó xác lập. Trong ví dụ về quan hệ ≡m , chỉ số của ≡m chính là m. Tuy nhiên, số lớp tương đương có thể vô hạn, chẳng hạn trong quan hệ = trên tập số nguyên Z, mỗi lớp tương đương chỉ gồm một phần tử, tức là ta có các lớp tương đương [0], [1], [2],. và do đó chỉ số của quan hệ tương đương này là vô hạn.
Nửa nhóm, vị nhóm Định nghĩa 1. Giả sử cho tập S và một phép toán hai ngôi. Một bộ phận A của S được gọi là ổn định (với phép toán hai ngôi trong S) nếu và chỉ nếu ∀ x, y ∈ A thì xy ∈ A. Ta dễ thấy tập các số tự nhiên N ổn định với phép toán ” + ” nhưng không ổn định với phép toán ” − ” các số tự nhiên.
Giả sử cho tập S và một phép toán hai ngôi. - Phần tử e ∈ S được gọi là đơn vị trái của phép toán hai ngôi nếu ex = x với mọi x ∈ S. - Phần tử e ∈ S được gọi là đơn vị phải của phép toán hai ngôi nếu xe = x với mọi x ∈ S. Nếu e vừa là đơn vị trái, vừa là đơn vị phải thì e được gọi là phần tử đơn vị (hay phần tử trung lập, phần tử trung hòa).
Mặc dù đều đề cập đến một phần tử đơn vị trong tập hợp nhưng người ta hay dùng thuật ngữ phần tử 0 để nói về phần tử đơn vị của phép cộng (viết theo lối cộng), còn người ta dùng thuật ngữ phần tử 1 để nói về phần tử đơn vị của phép nhân (viết theo lối nhân) để phân biệt chúng trong trường hợp một tập hợp được trang bị cả hai phép toán được viết theo lối cộng và lối nhân. Dễ nhận thấy số 0 là phần tử đơn vị của phép cộng, số 1 là phần tử đơn vị của phép nhân trong tập các số nguyên Z. Nếu một phép toán trong tập S có đơn vị trái e0 và đơn vị phải e00 thì e0 = e00. Phép toán hai ngôi trong một tập có nhiều nhất một phần tử đơn vị.
Một phép toán hai ngôi trong tập S là kết hợp nếu và chỉ nếu ( xy)z = x (yz) với mọi x, y, z ∈ S. Một tập hợp S cùng một phép toán kết hợp trong S được gọi là một nửa nhóm. Nửa nhóm S có phần tử đơn vị được gọi là một vị nhóm. Một nửa nhóm là giao hoán nếu phép toán của nó giao hoán.
Phép cộng cùng với tập Z là một nửa nhóm, đồng thời do có 0 là phần tử đơn vị nên (Z, +) chính là một vị nhóm. Phép cộng trong Z là giao hoán nên (Z, +) đồng thời là một vị nhóm giao hoán. Từ và ngôn ngữ Cho Σ là bảng hữu hạn các ký hiệu, gọi là bảng chữ cái. Một từ x thuộc bảng chữ cái Σ là một dãy các ký hiệu trong Σ viết liên tiếp nhau theo thứ tự từ trái sang phải.
Độ dài của từ x là số ký hiệu có trong x, được ký hiệu là | x |. Ta định nghĩa một từ đặc biệt, có độ dài là 0 gọi là từ rỗng, ký hiệu là ∧. Từ rỗng ∧ không được xây dựng từ bảng chữ cái nào và có thể được chứa trong ngôn ngữ xây dựng trên bảng chữ cái bất kỳ. Tập hợp tất cả các từ thuộc bảng chữ cái Σ được ký hiệu là Σ? và ngôn ngữ (xây dựng) trên bảng chữ cái Σ (hay ngôn ngữ của bảng chữ cái Σ) là một tập con của Σ?.
Ký hiệu Σ+ = Σ? − {∧} là ngôn ngữ xây dựng trên bảng chữ cái Σ nhưng không chứa từ rỗng. Mở rộng bảng chữ cái: Nếu L là một ngôn ngữ trên bảng chữ cái Σ thì nó cũng là ngôn ngữ trên bảng chữ cái chứa Σ nên ta luôn có thể giả thiết hai ngôn ngữ bất kỳ được xây dựng trên cùng bảng chữ cái để sử dụng cho các phép toán trên ngôn ngữ về sau. Ta có một số phép toán: 1. Tích ghép: - Nếu α là một từ trên bảng chữ cái Σ và ∧ là từ rỗng thì tích ghép của α và ∧ được định nghĩa là α • ∧ = ∧ • α = α.
bm là hai từ trên bảng chữ cái Σ thì tích ghép 21 z của α và β, ký hiệu là α • β được định nghĩa là a1 a2. Dễ nhận thấy phép tích ghép hai từ là không giao hoán, nhưng kết hợp và nó trung hòa với từ rỗng ∧. Tích ghép của hai ngôn ngữ L1 , L2 trên bảng chữ cái Σ, ký hiệu bởi L1 • L2 , là tập { x ∈ Σ∗ | ∃y ∈ L1 , z ∈ L2 , x = y • z}, trong đó y • z là phép tích ghép hai từ y và z.