Bài giảng Ôtômát và ngôn ngữ hình thức - Chương 1: Kiến thức cơ sở - Nguyễn Thị Thùy Linh

 TRƯỜNG ĐẠI HỌC ĐỒNG THÁP 
 KHOA SƯ PHẠM TOÁN - TIN Giới thiệu 
 BÀI GiẢNG MÔN HỌC • Lý thuyết ngôn ngữ hình thức và ôtômát đặt nền 
 tảng mạnh mẽ trên lý thuyết tập hợp, hàm, ánh 
 ÔTÔMÁT VÀ 
 xạ, quan hệ và lý thuyết đồ thị. 
 NGÔN NGỮ HÌNH THỨC 
 • Kỹ thuật mô phỏng các quá trình làm việc tương 
 tự trên máy tính. 
 Biên soạn : Ths.Nguyễn Thị Thùy Linh 
 E-mail : nttlinh@dthu.edu.vn 
 1 2 
 Mục tiêu NỘI DUNG MÔN HỌC 
• Nghiên cứu hai lý thuyết cơ sở trong lĩnh vực khoa học máy tính: 
 – Lý thuyết về ôtômát: lý thuyết cơ bản cho việc nghiên cứu Chương 1: Kiến thức cơ sở 
 các mô hình tính toán tự động để làm tiền đề cho sự phát 
 triển dạng máy tính số như hiện nay. Chương 2: Ngôn ngữ, văn phạm và ôtômát. 
 – Lý thuyết về ngôn ngữ hình thức (Formal languages): nền 
 tảng cho việc thấu hiểu khái niệm về ngôn ngữ nói chung (cả Chương 3: văn phạm chính quy và Ôtômát hữu hạn 
 ngôn ngữ lập trình lẫn ngôn ngữ tự nhiên), và các vấn đề cơ 
 bản về ngôn ngữ như cách xây dựng văn phạm sinh ra ngôn Chương 4: Văn phạm phi ngữ cảnh và Ôtômát đẩy xuống. 
 ngữ (xây dựng văn phạm cho ngôn ngữ lập trình, cho quá 
 trình phân tích cú pháp), dịch từ ngôn ngữ lập trình cấp cao Chương 5: Máy Turing. 
 sang ngôn ngữ máy 
 – Hai khía cạnh này có mối liên quan mật thiết với nhau trong 
 ứng dụng của khoa học máy tính. 
 3 4 
 1 
 Đánh giá môn học Chương 1: Kiến thức cơ sở 
• Thi tự luận cuối kỳ: hệ số 0.7 Kiến thức nền (nhắc lại) 
 – Hình thức: Bài tập 1. Lý thuyết tập hợp. 
 – Thời gian 90 phút, được sử dụng tài liệu 2. Các quan hệ. 
• Kiểm tra thường kỳ: hệ số 0.3 3. Đồ thị và cây. 
 – Kiểm tra bài tập tại lớp (50%) 
 – Tự học, tự nghiên cứu (50%) 
 5 6 
 Các ký pháp về tập hợp Các ký pháp về tập hợp (tt) 
 • x là phần tử của A, ta viết x A. 
 • x không là phần tử của A, ta viết x A. 
 • Nếu mọi phần tử của A đều là phần tử của B, 
 ta viết A  B. 
 • A = B  A  B và B  A. 
 7 8 
 2 
 Các phép toán trên các tập hợp Các phép toán trên các tập hợp (tt) 
 • Thí dụ : Cho A = {1, 2} và B = {2, 3} 
• A  B = {x| x A hoặc x B} • A  B = {1, 2, 3} 
• A  B = {x| x A và x B} • A  B = {2} 
• A – B = {x| x A và x B} • A – B = {1} 
• A x B, tích Đềcác của A và B, là tập hợp có thứ tự • A x B = {(1, 2), (1, 3), (2, 2), (2, 3)} 
 (a, b) sao cho a A và b B • 2A = {, {1}, {2}, {1, 2}} 
• 2A, tập lũy thừa của A, đó là tập hợp mọi tập con • Lưu ý: Nếu A và B lần lượt có n và m phần tử thì 
 của A. A x B có n x m phần tử 
 2A có 2n phần tử 
 2B có 2m phần tử 
 9 10 
 Các quan hệ Các tính chất của quan hệ 
• ĐN: Cho 2 tập hợp A và B. Một quan hệ Ta nói một quan hệ R trên tập A là: 
 giữa A và B, ký hiệu R, là một tập các cặp 
 • Phản xạ nếu aRa là đúng đối với a A. 
 (a, b) với a A và b B. Viết là R = 
 {(a,b) | a A, b B } • Bất phản xạ nếu aRa là sai đối với a A. 
• Trường hợp A = B ta nói đó là quan hệ trên • Truyền ứng (Bắc cầu) nếu aRb và bRc kéo 
 A. theo aRc 
• Nếu R là một quan hệ và (a, b) là một cặp • Đối xứng nếu aRb kéo theo bRa. 
 trong R thì ta thường viết aRb. • Phản đối xứng nếu aRb kéo theo bRa sai. 
 11 12 
 3 
 Các quan hệ tương đương Các quan hệ tương đương (tt) 
 • Một quan hệ R trên tập A được gọi là quan hệ tương • Thí dụ 1.4: Cho tập số tự nhiên N và R là một quan hệ 
 đương nếu nó là quan hệ phản xạ, đối xứng và bắc tương đương trên tập hợp N. Vậy R sẽ phân hoạch N ra 
 cầu. thành các lớp tương đương không rỗng và rời nhau. Đó 
 • Nếu R là quan hệ tương đương trên tập A thì R phân là các lớp nào? 
 hoạch A thành các lớp tương đương không rỗng và • Cách 1: nRm khi m và n có cùng tính chất chia hết cho 2. 
 rời nhau. Điều đó có nghĩa là: 
 R sẽ phân hoạch N thành hai lớp tương đương là tập các 
 A = A1  A2   trong đó với mọi i và j mà i j 
 thì: số chẵn và tập các số lẻ. 
 • Cách 2: nRm khi m và n có cùng tính chất là số nguyên 
 1. Ai  Aj =  
 2. Với mọi a và b cùng thuộc Ai, aRb là đúng. tố hoặc ngược lại. R sẽ phân hoạch N thành hai lớp 
 3. Với mọi a Ai và mọi b Aj, aRb là sai. tương đương là tập hợp số nguyên tố và tập hợp không 
 phải số nguyên tố. 
 13 14 
 Bao đóng của quan hệ Bao đóng của quan hệ (tt) 
• Cho một tập W những tính chất nào đó của các  Người ta còn định nghĩa một cách khác tập R+ 
 quan hệ. nhờ khái niệm lũy thừa quan hệ Ri. Ri được định 
• Ta gọi bao đóng W của một quan hệ R là quan hệ nghĩa (một cách đệ quy) như sau: 
 bé nhất R’ bao gồm R và các tính chất trong W. 
 1. aR1b khi và chỉ khi aRb. 
• Bao đóng bắc cầu của R, ký hiệu R+, được định 
 2. aRib khi và chỉ khi tồn tại c sao cho aRc và 
 nghĩa như sau: 
 cRi-1b với i>1. 
 1. Nếu (a, b) thuộc R, thì (a, b) thuộc R+. 
 + + 1 2
 2. Nếu (a, b) thuộc R+, và (b, c) thuộc R thì (a, c)  Tập R được định nghĩa là: R = R  R   
 R+.  aR0b khi và chỉ khi a = b. 
 +
 3. Không còn cặp nào khác trong R ngoài các cặp 
 thu được từ (1) và (2). 
 15 16 
 4 
 Bao đóng của quan hệ (tt) Bài tập 
• Bao đóng phản xạ và bắc cầu của R, ký hiệu • Cho R = { (1,2), (2,3), (2,4)} là qh 
 * * 0 +
 là R , được định nghĩa: R = R  R . trên tập {1,2,3,4}. Tìm R+ và R* 
• Ví dụ: Cho R = {(1, 2), (2, 2), (2, 3)} là một 
 quan hệ trên tập hợp {1, 2, 3}. Thế thì: • Cho R = {(a,b),(b,c),(c,a)} là 1 quan 
 + hệ trên {a,b,c}. Tìm R* 
 • R = {(1, 2), (2, 2), (2, 3), (1, 3)}. 
 • R* = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 
 3)}. 
 17 18 
 Đồ thị Đồ thị (tt) 
 Một đồ thị, ký hiệu G = (V, E), gồm  Ví dụ : Hãy vẽ đồ thị G(V,E) 
 một tập hữu hạn V các đỉnh và một V = {1, 2, 3, 4, 5} và 
 tập E các cặp nút gọi là các cạnh. E = {(n, m)| n + m = 4 hay n + m = 7} 
 Một đường đi trên đồ thị là một dãy 1 2 
 các nút v , v ,  v , k 1, sao cho có 
 1 2 k 3 
 một cạnh (v , v ) đối với mỗi i, 1 i 
 i i+1 5 
 k. Độ dài của đường đi là k-1. Nếu 4 
 v1 = vk thì đường được gọi là chu 
 19 20 
 trình. 
 5 
 Các khái niệm khác Đồ thị có hướng 
• Liên thông. 
  Một đồ thị định hướng, ký hiệu G = (V, E), gồm 
• Không liên thông. 
 một tập hữu hạn V các nút và một tập E các cặp 
• Chu trình. nút có thứ tự gọi là cung. Ta ký hiệu một cung từ v 
 tới w bởi v w. 
• Đỉnh cô lập 
• Đỉnh treo 
• Khuyên 1 2 3 4 
• Bậc của 1 đỉnh 
 21 22 
 Đồ thị có hướng (tt) Cây 
  Một cây (hay nói rõ hơn là cây định hướng có thứ 
 Một đường trong đồ thị có hướng là tự) là một đồ thị có hướng với các tính chất sau: 
 một dãy các nút v1, v2, , vk, k 1, 1. Có một nút, gọi là nút gốc, không có nút 
 sao cho với mọi i, 1 i k, có một trước. 
 2. Mỗi nút khác nút gốc có đúng một nút 
 cung từ vi tới vi+1. 
 trước. 
 Nếu v w là một cung thì v được gọi 3. Các nút sau của một nút đều được sắp 
 là nút trước của w và w được gọi là nút xếp thứ tự (từ trái qua phải). 
 sau của v.  Ví dụ: Cây sau diễn tả cấu trúc cú pháp của một câu 
 23 tiếng Việt: “An là sinh viên giỏi”. 24 
 6 
 Phân tích văn phạm Tiếng Việt Cây (tt) 
• 
• 
• Sinh viên | Lớp | Tôi | Cô ấy | bạn | An 
• 
• thì | là | đi | học | chạy 
• | 
• rất | quá 
• đẹp | giỏi | tốt 
 25 26 
 7