Tài liệu Về văn phạm và ngôn ngữ hình thức

Header Page 1 of 161. TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN NGÔ THỊ TÚ UYÊN VỀ VĂN PHẠM VÀ NGÔN NGỮ HÌNH THỨC KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Toán Ứng dụng Hà Nội - 2016 Footer Page 1 of 161. Header Page 2 of 161. TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN NGÔ THỊ TÚ UYÊN VỀ VĂN PHẠM VÀ NGÔN NGỮ HÌNH THỨC KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Toán Ứng dụng Người hướng dẫn khoa học TS. KIỀU VĂN HƯNG Hà Nội - 2016 Footer Page 2 of 161. Header Page 3 of 161. Lời cảm ơn Trước khi trình bày nội dung chính của khóa luận tốt nghiệp, em xin bày tỏ lòng biết ơn sâu sắc tới T.S Kiều Văn Hưng đã tận tình hướng dẫn để em có thể hoàn thành đề tài này. Em cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô giáo trong khoa Toán, Trường Đại học Sư phạm Hà Nội 2 đã dạy bảo em tận tình trong suốt quá trình học tập tại khoa. Nhân dịp này em cũng xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè đã luôn bên em, động viên, giúp đỡ em trong suốt quá trình học tập và thực hiện đề tài thực tập này. Hà Nội, ngày 04 tháng 05 năm 2016 Sinh viên Ngô Thị Tú Uyên i Footer Page 3 of 161. Header Page 4 of 161. Lời cam đoan Tôi xin cam đoan rằng số liệu và kết quả nghiên cứu trong khóa luận này là trung thực và không trùng lặp với các đề tài khác. Tôi cũng xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện khóa luận này đã được cảm ơn và các thông tin thu trích dẫn trong khóa luận đã được chỉ rõ nguồn gốc. Hà Nội,ngày 04 tháng 05 năm 2015 Sinh viên Ngô Thị Tú Uyên ii Footer Page 4 of 161. Header Page 5 of 161. Mục lục Lời mở đầu iii Danh mục các kí hiệu và chữ viết tắt v 1 NGÔN NGỮ HÌNH THỨC 1 1.1 1.2 1.3 Các khái niệm cơ bản về ngôn ngữ hình thức . . . . . . . 2 1.1.1 Bảng chữ cái . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Từ . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.3 Ngôn ngữ . . . . . . . . . . . . . . . . . . . . . . 4 Các phép toán trên từ . . . . . . . . . . . . . . . . . . . 5 1.2.1 Phép nhân ghép . . . . . . . . . . . . . . . . . . . 5 1.2.2 Phép lấy từ ngược . . . . . . . . . . . . . . . . . 7 1.2.3 Phép chia từ . . . . . . . . . . . . . . . . . . . . . 8 Các phép toán trên ngôn ngữ . . . . . . . . . . . . . . . 9 1.3.1 Phép hợp . . . . . . . . . . . . . . . . . . . . . . 9 1.3.2 Phép giao . . . . . . . . . . . . . . . . . . . . . . 9 1.3.3 Phép lấy phần bù . . . . . . . . . . . . . . . . . . 11 1.3.4 Phép nhân ghép . . . . . . . . . . . . . . . . . . . 12 1.3.5 Phép lặp . . . . . . . . . . . . . . . . . . . . . . . 14 i Footer Page 5 of 161. Header Page 6 of 161. Khóa luận tốt nghiệp Đại học NGÔ THỊ TÚ UYÊN 1.3.6 Phép lấy ngôn ngữ ngược . . . . . . . . . . . . . 15 1.3.7 Phép chia ngôn ngữ . . . . . . . . . . . . . . . . . 16 2 VĂN PHẠM 2.1 18 Văn phạm và ngôn ngữ sinh bởi văn phạm . . . . . . . . 19 2.1.1 Định nghĩa văn phạm . . . . . . . . . . . . . . . . 19 2.1.2 Ngôn ngữ sinh bởi văn phạm . . . . . . . . . . . . 21 2.1.3 Phân loại văn phạm theo Chomsky . . . . . . . . 24 Các tính chất của văn phạm và ngôn ngữ . . . . . . . . . 27 2.2.1 Một số tính chất của văn phạm và dẫn xuất . . . 27 2.2.2 Tính đóng của lớp ngôn ngữ sinh bởi văn phạm . 32 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . 53 2.2 ii Footer Page 6 of 161. Header Page 7 of 161. Khóa luận tốt nghiệp Đại học NGÔ THỊ TÚ UYÊN Lời mở đầu Sự phát triển của thế giới ngày càng gắn liền với sự phát triển bùng nổ của khoa học máy tính. Một trong những lý thuyết cơ sở của môn khoa học này là lý thuyết về văn phạm và ngôn ngữ hình thức. Về ngôn ngữ hình thức. Ngôn ngữ là phương tiện để giao tiếp, sự giao tiếp có thể hiểu là giao tiếp giữa con người với con người, giao tiếp giữa người và máy, hay giao tiếp giữa máy với máy. Ngôn ngữ để giao tiếp giữa người với người là ngôn ngữ tự nhiên như ta đã biết, ví dụ tiếng Việt, tiếng Anh, Tiếng Trung . . . Còn ngôn ngữ giao tiếp giữa người với máy, giữa máy với nhau là ngôn ngữ hình thức. Vậy tại sao cần sử dụng ngôn ngữ hình thức mà không phải ngôn ngữ tự nhiên? Ngôn ngữ hình thức được xây dựng thế nào? Nó có tính chất gì? . . . Những câu hỏi này sẽ được trả lời trong Chương 1: Ngôn ngữ hình thức. Về văn phạm.Với mục đích sản sinh ( hay đoán nhận) ngôn ngữ, văn phạm được dùng như một cách thức hiệu quả để biểu diễn ngôn ngữ. Vậy văn phạm trong khoa học máy tính là gì? Ngôn ngữ sinh bởi văn phạm này khác ngôn ngữ tự nhiên như thế nào? Văn phạm có những tính chất gì? . . . Những câu hỏi này sẽ được trả lời trong Chương 2: Văn phạm. Tác giả luận văn chân thành cảm ơn T.S Kiều Văn Hưng đã tận tình hướng dẫn tác giả đọc các tài liệu, tập dượt nghiên cứu và góp ý chi tiết về cách trình bày một số kết quả trong luận văn. Tác giả chân thành cảm ơn các thầy cô giáo Khoa Toán trường Đại Footer Page 7 of 161. iii Header Page 8 of 161. Khóa luận tốt nghiệp Đại học NGÔ THỊ TÚ UYÊN học Sư phạm Hà Nội 2, đặc biệt là tổ Ứng dụng, đã tạo điều kiện thuận lợi cho tác giả trong quá trình học Đại học và thực hiện bản khóa luận này. Hà Nội, ngày 04 tháng 05 năm 2016 Tác giả khóa luận Ngô Thị Tú Uyên Footer Page 8 of 161. iv Header Page 9 of 161. Khóa luận tốt nghiệp Đại học NGÔ THỊ TÚ UYÊN Danh mục các kí hiệu và chữ viết tắt N tập số tự nhiên x∈M x thuộc tập M x∈ /M x không thuộc tập M ∀x với mọi x ∃x tồn tại x M ⊂ N M là một tập con thực sự của N M ⊆ N M là một tập con của N 2 Footer Page 9 of 161. Kết thúc chứng minh v Header Page 10 of 161. Chương 1 NGÔN NGỮ HÌNH THỨC Ngôn ngữ tự nhiên Ngôn ngữ giao tiếp giữa người với người gọi là ngôn ngữ tự nhiên , như tiếng Anh, tiếng Trung, tiếng Việt, . . . Các quy tắc cú pháp của ngôn ngữ tự nhiên nói chung rất phức tạp, nhưng các yêu cầu nghiêm ngặt về mặt ngữ nghĩa thì lại thiếu chặt chẽ, chẳng hạn cùng một từ hay một câu ta có thể hiểu chúng theo những nghĩa khác nhau tùy theo từng ngữ cảnh cụ thể. Do đó ngôn ngữ tự nhiên không thích hợp để dùng giao tiếp giữa người với máy, hoặc giữa máy với máy. Ngôn ngữ hình thức Để có sự giao tiếp giữa người với máy, hay giữa máy với nhau, cần phải có một loại ngôn ngữ với các quy tắc cú pháp chặt chẽ hơn so với ngôn ngữ tự nhiên, với một từ hay một câu thì ngữ nghĩa của chúng phải là duy nhất và không phụ thuộc vào ngữ cảnh. Những ngôn ngữ như thế được gọi là ngôn ngữ hình thức. Footer Page 10 of 161. 1 Header Page 11 of 161. Khóa luận tốt nghiệp Đại học 1.1 1.1.1 NGÔ THỊ TÚ UYÊN Các khái niệm cơ bản về ngôn ngữ hình thức Bảng chữ cái Định nghĩa 1.1. Tập Σ khác rỗng gồm hữu hạn các kí hiệu được gọi là bảng chữ cái. Mỗi phần tử a ∈ Σ được gọi là một chữ cái hay một kí hiệu. Ví dụ 1.1. Dưới đây là các bảng chữ cái thông thường: 1. Σ= {0, 1} 2. Σ= {a, b, c,. . . , z} 1.1.2 Từ Định nghĩa 1.2. Giả sử có bảng chữ cái Σ= {a1 , a2 ,. . . ,an }, một dãy hữu hạn các chữ cái α = ai1 ai2 . . . ait , với aij ∈ Σ (1 ≤ j ≤ t) được gọi là một từ hay một xâu trên Σ. Trong một từ, một chữ cái có thể xuất hiện nhiều lần. Tổng số vị trí của các kí hiệu xuất hiện trong từ α được gọi là độ dài của từ α, và kí hiệu là |α|. Từ không có kí tự nào được gọi là từ rỗng, và được kí hiệu là ε. Rõ ràng |ε| = 0 , và nó thuộc mọi bảng chữ cái. Footer Page 11 of 161. 2 Header Page 12 of 161. Khóa luận tốt nghiệp Đại học NGÔ THỊ TÚ UYÊN Hai từ α = a1 a2 . . . an và β = b1 b2 . . . bn được gọi là bằng nhau, kí hiệu là α = β, nếu n = m (tức là α và β có độ dài bằng nhau) và ai = bi với mọi i = 1, 2, . . . , n. Nếu α là một từ trên bảng chữ cái Σ1 , và Σ1 ⊆ Σ2 thì α cũng là từ trên bảng chữ cái Σ2 . Tập mọi từ trên bảng chữ cái Σ được kí hiệu là Σ∗ , tập mọi từ khác rỗng trên bảng chữ cái Σ được kí hiệu là Σ+ . Như vậy: Σ+ = Σ∗ \{ε} và Σ∗ = Σ+ ∪ {ε}. Dễ thấy rằng các tập Σ+ và Σ∗ là vô hạn. Về cấu trúc đại số thì Σ∗ là một vị nhóm tự do sinh bởi Σ với phần tử đơn vị là từ rỗng (ε), còn Σ+ là một nửa nhóm tự do sinh bởi Σ. Có thể chứng minh được rằng các tập Σ∗ và Σ+ là vô hạn đếm được. Ví dụ 1.2. . 1. Ta có: ε, 0, 01, 101, 1010, 110010, . . . là các từ trên bảng chữ cái Σ = {0, 1}. 2. Các xâu ε, computer, language, grammar, . . . là các từ trên bảng chữ cái Σ = {a, b, . . . , z} 3. |101| = 3, |computer| = 8 4. Σ1 = {0, 1}, Σ2 = {0, 1, . . . , 9} α = 1010 ∈ Σ1 , Σ1 ⊂ Σ2 ⇒ α ∈ Σ2 Footer Page 12 of 161. 3 Header Page 13 of 161. Khóa luận tốt nghiệp Đại học 1.1.3 NGÔ THỊ TÚ UYÊN Ngôn ngữ Định nghĩa 1.3. Cho bảng chữ cái Σ, mỗi tập L ⊆ Σ∗ được gọi là một ngôn ngữ trên bảng chữ cái Σ. Như vậy, ngôn ngữ có thể hữu hạn hoặc vô hạn từ, và tương ứng được gọi là ngôn ngữ hữu hạn hoặc ngôn ngữ vô hạn. Nếu L là ngôn ngữ trên bảng chữ cái Σ1 , mà Σ1 ⊆ Σ2 thì L cũng là ngôn ngữ trên Σ2 . Ngôn ngữ không gồm một từ nào, gọi là ngôn ngữ rỗng, kí hiệu là ∅. Vậy ngôn ngữ rỗng là ngôn ngữ trên mọi bảng chữ cái, và là một ngôn ngữ hữu hạn. Chú ý: Ngôn ngữ rỗng L = ∅ khác với ngôn ngữ chỉ gồm một từ rỗng L = {ε}. Ngôn ngữ L = ∅ không có từ nào, còn ngôn ngữ L = {ε} có một từ duy nhất là ε. Ví dụ 1.3. . 1. Σ∗ là ngôn ngữ gồm tất cả các từ trên bảng chữ cái Σ. Σ+ là ngôn ngữ gồm tất cả các từ khác rỗng trên bảng chữ cái Σ. 2. Ngôn ngữ bao gồm các từ có n số 0 đứng trước n số 1, với n = 0, 1, . . . là: L = {ε, 01, 0011, 000111, . . .} = {0n 1n | n = 0, 1, . . .}. 3. Tập tất cả các từ trên Σ = {0, 1} mà số các số 0 và số các số 1 bằng nhau: L = {ε, 01, 10, 0011, 0101, 1001, . . .} là một ngôn ngữ trên Σ. 4. L1 = {ε, a, b, aa, ab, abb, bbb}, L2 = {an bn | n ∈ N} là hai ngôn ngữ trên bảng chữ cái Σ = {a, b}. L1 là ngôn ngữ hữu hạn, L2 là ngôn Footer Page 13 of 161. 4 Header Page 14 of 161. Khóa luận tốt nghiệp Đại học NGÔ THỊ TÚ UYÊN 0 ngữ vô hạn.L1 , L2 cũng là ngôn ngữ trên bảng chữ cái Σ = {a, b, c}. 1.2 Các phép toán trên từ Các phép toán sau đây thực hiện trên các từ của cùng một bảng chữ cái Σ, tạo nên các từ mới cũng thuộc bảng chữ cái đó. 1.2.1 Phép nhân ghép Định nghĩa 1.4. Phép nhân ghép (hay tích ghép) của hai từ α = a1 a2 . . . am và β = b1 b2 . . . bn trên bảng chữ cái Σ, là từ γ = a1 a2 . . . am b1 b2 . . . bn trên bảng chữ cái Σ. Kí hiệu: γ = α.β (hay γ = αβ). Tính chất: Từ định nghĩa 2.1 ta thấy • Từ rỗng là phần tử đơn vị với phép nhân ghép, tức là ωε = εω = ω, đúng với mọi từ ω. • Phép nhân ghép có tính chất kết hợp, nghĩa là với mọi từ α, β, γ thì (αβ)γ = α(βγ). • Kí hiệu ω n (với n ∈ N) được dùng theo nghĩa quen thuộc     ε    ωn = ω      ω n−1 ω Footer Page 14 of 161. 5 khi n = 0, khi n = 1, khi n > 1. Header Page 15 of 161. Khóa luận tốt nghiệp Đại học NGÔ THỊ TÚ UYÊN • Đối với phép nhân ghép,thì hàm độ dài có một số tính chất hình thức của logarit, tức là với mọi từ α, β và mọi số tự nhiên n thì |αβ| = |α| + |β| |αn | = n|α| |ε| = 0 Một vài khái niệm liên quan • Đối với các từ ω, t1 , ϕ, t2 trên bảng chữ cái Σ mà ω = t1 ϕt2 thì ∗ ϕ∗ (∗ không phải là một kí hiệu của Σ) gọi là một vị trí của ϕ trên Σ. • Xâu ϕ được gọi là một từ con trong ω nếu tồn tại ít nhất một vị trí của ϕ trong ω. • Nếu t1 = ε, tức là ω = ϕt2 thì ϕ được gọi là tiền tố (phần đầu) của từ ω, nếu t2 = ε, tức là ω = t1 ϕ thì ϕ được gọi là hậu tố (phần cuối) của từ ω. Dễ thấy rằng từ rỗng ε là tiền tố, là hậu tố và là từ con của một từ ω bất kì trên bảng chữ cái Σ. • Trường hợp |ϕ| = 1, tức là ϕ chỉ gồm một kí hiệu, ví dụ ϕ = a ∈ Σ, thì ∗ a∗ được gọi là một vị trí của a trong từ ω, cũng được gọi là một điểm trong ω. • Số vị trí của kí hiệu a trong từ ω được kí hiệu là Ia (ω), hay |ω|a hoặc đơn giản hơn là ω|a . Ví dụ 1.4. . 1. Trên bảng chữ cái Σ = {a, b, . . . , z} có từ α = super, β = set thì tích αβ = superset cũng là một từ trên bảng chữ cái Σ. Footer Page 15 of 161. 6 Header Page 16 of 161. Khóa luận tốt nghiệp Đại học NGÔ THỊ TÚ UYÊN 2. Cho Σ = {a, b, c}, khi đó từ ω = abcbcb chứa 2 vị trí của bcb, đó là a∗ bcb∗ cb và abc∗ bcb∗ , ϕ = bcb là một từ con của ω. Từ ω chứa một vị trí của kí hiệu a, đó là ∗ a∗ bcbcb. 3. Từ ω = 011001 trên bảng chữ cái Σ = {0, 1}, có độ dài 6, trong đó 01 là tiền tố, 1001 là hậu tố của ω. 1.2.2 Phép lấy từ ngược Định nghĩa 1.5. Giả sử có từ khác rỗng ω = a1 a2 . . . am−1 am trên bảng chữ cái Σ, khi đó từ am am−1 . . . a2 a1 được gọi là từ ngược ( hay từ soi gương ) của từ ω, được kí hiệu là ω R , hay ωˆ. Khi ω = ε ta quy ước εR = ε. Tính chất: Phép lấy từ ngược có các tính chất sau: • (ω R )R = ω • (αβ)R = β R αR • |αR | = |α|. Ví dụ 1.5. 1. Cho từ ω = 1100101 trên bảng chữ cái Σ = {0, 1} thì ω R = 1010011 và (ω R )R = (1010011)R = 1100101 = ω, ta có |1100101| = |1010011| = 6. 2. Cho các từ α = oto, β = madamimadam (Madam, I’m Adam) trên bảng chữ cái Σ1 = {a, b, c, . . . , z} thì αR = α = oto, β R = β = madamimadam. γ = 0n 10n trên bảng chữ cái Σ2 = {0, 1} thì γ R = γ = 0n 10n , n ∈ N. Footer Page 16 of 161. 7 Header Page 17 of 161. Khóa luận tốt nghiệp Đại học 1.2.3 NGÔ THỊ TÚ UYÊN Phép chia từ Là phép ngắt bỏ tiền tố hoặc hậu tố của một từ. Ta có các định nghĩa sau: Định nghĩa 1.6. Phép chia trái của từ α cho từ β (hay thương bên trái của α và β) cho kết quả là phần còn lại của từ α sau khi ngắt bỏ tiền tố β trong từ α, và được kí hiệu là β \α . Định nghĩa 1.7. Phép chia phải của từ α cho từ γ (hay thương bên phải của từ α và γ) cho kết quả là phần còn lại của từ α sau khi ngắt bỏ hậu tố γ trong từ α và được kí hiệu là α /γ . Tính chất: Phép chia từ có các tính chất sau: • ε \α = α • α \α = α /ε = α /α = ε • Nếu α = β · γ thì β \α = γ, còn α /γ = β • (β \α )R = αR / • (α /γ )R =γ R \α βR R Ví dụ 1.6. Cho các từ α = 123456789, β = 123, γ = 789 trên bảng chữ cái Σ = {1, 2, . . . , 9} khi đó ta có 1. β \α = 456789 và α /γ = 123456 2. (β \α )R = (456789)R = 987654 = Footer Page 17 of 161. 987654321 8 /321 = αR /β R Header Page 18 of 161. Khóa luận tốt nghiệp Đại học 1.3 NGÔ THỊ TÚ UYÊN Các phép toán trên ngôn ngữ Vì mỗi ngôn ngữ là một tập hợp, nên ta có các phép toán đại số tập hợp như: phép giao, phép hợp, phép lấy phần bù,. . . trên các ngôn ngữ. 1.3.1 Phép hợp Định nghĩa 1.8. Hợp của hai ngôn ngữ L1 và L2 trên bảng chữ cái Σ, kí hiệu là L1 ∪ L2 , là một ngôn ngữ trên bảng chữ cái Σ, đó là tập từ: L = {ω ∈ Σ∗ | ω ∈ L1 hoặc ω ∈ L2 } Định nghĩa phép hợp có thể mở rộng cho một số hữu hạn các ngôn ngữ, tức là hợp của các ngôn ngữ L1 , L2 , . . . , Ln trên bảng chữ cái Σ, là tập hợp từ: n S Li = {ω ∈ Σ∗ | ω ∈ Li , với i nào đó, 1 ≤ i ≤ n} i=1 Tính chất: Phép hợp các ngôn ngữ có các tính chất sau: • Tính giao hoán: L1 ∪ L2 = L2 ∪ L1 • Tính kết hợp: (L1 ∪ L2 ) ∪ L3 = L1 ∪ (L2 ∪ L3 ) • Vói mọi ngôn ngữ L trên Σ thì L ∪ ∅ = ∅ ∪ L = L và L ∪ Σ∗ = Σ∗ ∪ L = Σ∗ 1.3.2 Phép giao Định nghĩa 1.9. Giao của hai ngôn ngữ L1 và L2 trên bảng chữ cái Σ, kí hiệu là L1 ∩ L2 , là một ngôn ngữ trên bảng chữ cái Σ, đó là tập từ: Footer Page 18 of 161. 9 Header Page 19 of 161. Khóa luận tốt nghiệp Đại học NGÔ THỊ TÚ UYÊN L = {ω ∈ Σ∗ | ω ∈ L1 và ω ∈ L2 } Định nghĩa phép giao có thể mở rộng cho một số hữu hạn các ngôn ngữ, tức là giao của các ngôn ngữ L1 , L2 , . . . , Ln trên bảng chữ cái Σ, là tập từ: n T L = {ω ∈ Σ∗ | ω ∈ Li , với mọi i, 1 ≤ i ≤ n} i=1 Tính chất: Phép giao các ngôn ngữ có tính chất sau: • Tính giao hoán: L1 ∩ L2 = L2 ∩ L1 • Tính kết hợp: (L1 ∩ L2 ) ∩ L3 = L1 ∩ (L2 ∩ L3 ) • Tính phân phối với phép hợp: (L1 ∩ L2 ) ∪ L3 = (L1 ∪ L3 ) ∩ (L2 ∪ L3 ). (L1 ∪ L2 ) ∩ L3 = (L1 ∩ L3 ) ∪ (L2 ∩ L3 ). • Với mọi ngôn ngữ L trên Σ thì: L ∩ ∅ = ∅ ∩ L = ∅ và L ∩ Σ∗ = Σ∗ ∩ L = L. Ví dụ 1.7. Cho các ngôn ngữ L1 = {ε, 0, 1, 00, 11},L2 = {00, 01, 10, 11}, L3 = {ε, 0, 1, 01, 10} trên bảng chữ cái Σ = {0, 1}, khi đó ta có: L1 ∪ L2 = {ε, 0, 1, 00, 01, 10, 11} L1 ∩ L2 = {00, 11} (L1 ∩ L2 ) ∪ L3 = {ε, 0, 1, 00, 01, 10, 11} L1 ∪ L3 = {ε, 0, 1, 00, 01, 10, 11} L2 ∪ L3 = {ε, 0, 1, 00, 01, 10, 11} (L1 ∪ L2 ) ∩ (L2 ∪ L3 ) = {ε, 0, 1, 00, 01, 10, 11} = (L1 ∩ L2 ) ∪ L3 Footer Page 19 of 161. 10 Header Page 20 of 161. Khóa luận tốt nghiệp Đại học 1.3.3 NGÔ THỊ TÚ UYÊN Phép lấy phần bù Định nghĩa 1.10. Ngôn ngữ phần bù của ngôn ngữ L trên bảng chữ cái Σ, kí hiệu là CΣ L (hay đơn giản là CL, nếu không gây nhầm lẫn), là một ngôn ngữ trên bảng chữ cái Σ, đó là tập từ: CΣ L = {ω ∈ Σ∗ | ω ∈ / L} Tính chất: Phép lấy phần bù các ngôn ngữ có các tính chất sau: • CΣ {ε} = Σ+ , CΣ Σ+ = {ε}. • CΣ ∅ = Σ∗ , CΣ Σ∗ = ∅. • C(CL1 ∪ CL2 ) = L1 ∩ L2 . • C(CL1 ∩ CL2 ) = L1 ∪ L2 . Ví dụ 1.8. Trên bảng chữ cái Σ = {0, 1} cho các ngôn ngữ L1 = {ω ∈ Σ∗ | với ω là các từ bắt đầu bằng số 0} L2 = {ω ∈ Σ∗ | với ω là các từ kết thúc bằng số 0} Khi đó L1 ∩ L2 = {ω ∈ Σ∗ | với ω là các từ bắt đầu và kết thúc bằng số 0} CL1 = {ω ∈ Σ∗ | với ω là các từ bắt đầu bằng số 1} CL2 = {ω ∈ Σ∗ | với ω là các từ kết thúc bằng số 1} CL1 ∪CL2 = {ω ∈ Σ∗ | với ω là các từ bắt đầu hoặc kết thúc bằng số 1} C(CL1 ∪ CL2 ) = {ω ∈ Σ∗ | với ω là các từ không bắt đầu và không kết thúc bằng số 1} = {ω ∈ Σ∗ | với ω là các từ bắt đầu và kết thúc bằng số 0} = L1 ∩ L2 Footer Page 20 of 161. 11