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

Nội dung text: Bài giảng Ôtômát và ngôn ngữ hình thức - Chương 1: Kiến thức cơ sở

1. 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
2. Đá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
3. 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
4. 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
5. 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
6. 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
7. 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