Bài giảng Lý thuyết ngôn ngữ - TS. Nguyễn Thị Uyên

Bài giảng Lý thuyết ngôn ngữ nhằm trình bày về 3 nội dung chính: tập hợp, quan hệ và đồ thị và cây. Bài giảng trình bày khoa học, súc tích và dễ hiểu giúp sinh viên tiếp thi bài nhanh.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết ngôn ngữ - TS. Nguyễn Thị Uyên 2/11/2014 TRƯỜNG ĐẠI HỌC VINH KHOA CÔNG NGHỆ THÔNG TIN -------------- -------------- ∽∽∽ ∽∽∽ ∽∽∽ ∽∽∽ BÀI GIẢNG LÝ THUYẾT NGÔN NGỮGiảng viên: ThS. Nguyễn Thị Uyên ThS.Khoa Công nghệ thông tin Chương 0 Bổ túc toán Nội dung I. Tập hợp II. Quan hệ III. Đồ thị và cây2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 3/17 1 2/11/2014I. Tập hợp (Set)• Tập hợp là tập các đối tượng không có sự lặp lại.• Mỗi đối tượng trong tập hợp được gọi là phần tử (element) của tập hợp đó.2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 4/17Biểu diễn tập hợp Tập hữu hạn: liệt kê từng phần tử Ví dụ: Tập hợp D xác định tập hợp các ngày trong tuần D = { Mon, Tues, Wed, Thurs, Fri, Sat, Sun } Các phần tử được viết cách nhau bởi dấu phẩy và đặt trong cặp dấu { và }. Thứ tự liệt kê các phần tử là không quan trọng Viết x ∈ A nghĩa là x thuộc A, Viết x ∉ A nghĩa là x không thuộc A2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 5/17Biểu diễn tập hợp Tập vô hạn: Chỉ ra một số đặc trưng của nó. Ví dụ: P = { y | y là số nguyên tố } X={xx>2} Một trường hợp đặc biệt của tập hợp là tập hợp rỗng (empty set). Tập hợp này không có chứa bất kỳ phần tử nào, ký hiệu bởi ∅ hoặc { }.2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 6/17 2 2/11/2014Tập con (subset) Tập hợp A là tập hợp con () của tập hợp B khi mọi phần tử của A đều thuộc B. Ký hiệu: A ⊆ B Ngược lại, A không là tập con của B (A ⊄ B ). Ví dụ { 1, 2, 4 } ⊆ { 1, 2, 3, 4, 5 } { 2, 4, 6 } ⊄ { 1, 2, 3, 4, 5 } Nhận xét: tập hợp ∅ ⊆ A, ∀A2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 7/17Tập bằng nhau Hai tập hợp A và B được gọi là bằng nhau (A = B) khi A ⊆ B và B ⊆ A Ví dụ : { 1, 2, 3, 4 } = { 2, 1, 4, 3 } {1, 2, 3, 4 } ≠ { 2, 1, 3, 5 }2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 8/17Tập lũy thừa Tập hợp tất cả các tập con của tập A được gọi là tập lũy thừa (power set) của A, ký hiệu: 2A. Ví dụ : Giả sử A = { 1, 2, 3 } Thì 2A = { ∅, 1, 2, 3, (1,2), (2,3), (3,1), (1,2,3) }2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 9/17 3 2/11/2014Phép toán 1. Phép hợp A ∪ B = {x | x ∈A hoặc x ∈B} 2. Phép giao A ∩ B = {x | x ∈A và x ∈B} 3. Phép trừ A B = {x | x ∈A nhưng x ∉B} 4. Tích Đecac A × B = {(a,b) | a ∈A và b∈B}2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 10/17Ví dụ Cho tập A = {1, 2} và B = {2, 3} 1. A ∪ B = {1, 2, 3} 2. A ∩ B = {2} 3. A B = {1} 4. A × B = {(1, 2 ), (1, 3), (2, 2), (2, 3)} 5. 2A = {∅, {1}, {2}, {1, 2}}2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 11/17II. Quan hệ Quan hệ 2 ngôi từ tập A đến tập B là một tập con của tập tích đề các A × B. Lưu ý: không nhất thiết tập A phải khác tập B Ví dụ: Cho tập S = { 0, 1, 2, 3} Quan hệ thứ tự nhỏ hơn trên S được xác định bởi tập L = {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)} Quan hệ bằng nhau trên S được xác định bởi tập: E = {(0, 0), (1, 1), (2, 2), (3, 3)}2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 12/17 4 2/11/2014Tính chất1. Phản xạ : nếu aRa là đúng ∀a ∈S2. Đối xứng : nếu aRb thì bRa3. Bắc cầu : nếu aRb và bRc thì aRc2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 13/17Quan hệ tương đương Một quan hệ R trên tập S có đủ các tính chất phản xạ, đối xứng và bắc cầu được gọi là quan hệ tương đương. Ví dụ: Cho tập S = { 0, 1, 2, 3} Quan hệ bằng nhau trên S E = {(0, 0), ...