Lý thuyết automata ngơn ngữ hình thức Automata Grammar Ngơn ngữ hình thức GIẢNG VIÊN: TS HÀ CHÍ TRUNG BỘ MƠN: KHMT KHOA CNTT, HVKTQS ĐT:0168.558.21.02 EMAIL: HCT2009@YAHOO.COM ©copyright by PhD C.T.Ha, Le Quy Don Technical University Bài Nhập môn Theory of automata and formal languagues – TA&FL (AL) MỤC ĐÍCH:  Trang bị hiểu biết chung môn học;  Khái quát lại số khái niệm, sở toán học làm sở học tập môn học YÊU CẦU:  Về nhà, sinh viên phải hệ thống lại kiến thức sở tốn liên quan kiến thức lập trình ©copyright by PhD C.T.Ha, Le Quy Don Technical University Bài Nhập môn TA&FL 1.1 Giới thiệu môn học TA&FL 1.2 Yêu cầu với môn học 1.3 Tài liệu tham khảo môn TA&FL 1.4 Bổ túc số khái niệm toán học 1.4.1 Tập hợp 1.4.2 Quan hệ 1.4.3 Phép chứng minh 1.4.4 Đồ thị Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 Bài Nhập môn TA&FL 1.1 Giới thiệu môn học TA&FL 1.2 Yêu cầu với môn học 1.3 Tài liệu tham khảo môn TA&FL 1.4 Bổ túc số khái niệm toán học 1.4.1 Tập hợp 1.4.2 Quan hệ 1.4.3 Phép chứng minh 1.4.4 Đồ thị Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 1.1 Giới thiệu môn học TA&FL  Ngơn ngữ hình thức (Formal Languages) mơn học sở ngành công nghệ thông tin:  Turing, Post Church, nghiên cứu xây dựng mơ hình tốn học cho máy tính tốn (30,40th–XXc.);  Chomsky với mục đích xây dựng mơ hình tốn cho ngơn ngữ tự nhiên (50th–XXc.)  Môn học trang bị cho người học kiến thức thuật tốn, ngơn ngữ thuật tốn, kỹ thuật xây dựng chương trình, xây dựng hệ thống tự động phương pháp tư liên quan đến khoa học máy tính  Kiến thức ngơn ngữ hình thức automat tảng cho nhiều lĩnh vực khoa học máy tính CNTT Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 1.1 Giới thiệu môn học TA&FL  Ứng dụng lý thuyết ngơn ngữ hình thức automata: Dùng xử lý từ vựng cú pháp ngôn ngữ tự nhiên;  Dùng xây dựng ngôn ngữ lập trình ctd;  Dùng nhận dạng (đối với mẫu nhận dạng có cấu trúc);  Dùng tin sinh học (Bio-informatics);  Dùng tính tốn phân tử (DNA Computing);  Dùng xử lý ảnh (nén ảnh Fractal, );  Dùng công nghệ phần mềm ( mã hóa liệu, mơ hình hố hệ thống động, tiến trình hệ thống…);  Trong lĩnh vực trí tuệ nhân tạo…  Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 1.1 Giới thiệu môn học TA&FL  Nội dung mơn học TA&FL: Cơ sở tốn học mơn TA&FL Văn phạm ngơn ngữ hình thức Automata hữu hạn ngơn ngữ hình thức Văn phạm quy tính chất Văn phạm phi ngữ cảnh Pushdown automata (automata đẩy xuống) Máy Turing Phần tập lý thuyết thực hành Automata ngôn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 Bài Nhập môn TA&FL 1.1 Giới thiệu môn học TA&FL 1.2 Yêu cầu với môn học 1.3 Tài liệu tham khảo môn TA&FL 1.4 Bổ túc số khái niệm toán học 1.4.1 Tập hợp 1.4.2 Quan hệ 1.4.3 Phép chứng minh 1.4.4 Đồ thị Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 1.2 Một số yêu cầu với môn học  Kiến thức nền: Toán rời rạc (tập hợp, đồ thị, cây, quan hệ, phương pháp chứng minh,…);  kiến thức tốn liên quan;  khả lập trình (C, C++, C#,…)  Hình thức đánh giá:  Tổng số tiết: 45;  Hình thức thi: vấn đáp;  Điểm đánh giá: c.cần 10%, t.xuyên 20%, thi 70%;  Đồ án mơn: Giải tập viết chương trình  Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 Bài Nhập môn TA&FL 10 1.1 Giới thiệu môn học TA&FL 1.2 Yêu cầu với môn học 1.3 Tài liệu tham khảo môn TA&FL 1.4 Bổ túc số khái niệm toán học 1.4.1 Tập hợp 1.4.2 Quan hệ 1.4.3 Phép chứng minh 1.4.4 Đồ thị Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 1.4.2 Quan hệ 22  ĐN 1.10: Bao đóng quan hệ (P-closure) quan hệ nhỏ thỏa tính chất P (tập hợp số tính chất quan hệ)  ĐN 1.11: Bao đóng bắc cầu R+: o Nếu (a,b)  R (a,b) R+ o Nếu (a,b)  R+ (b,c)  R (a,c)  R+ o Khơng cịn thêm R+  ĐN 1.12: Bao đóng phản xạ bắc cầu R*: o R* = R+  { (a, a)  a  S }  Ví dụ 1.8: R = { (1, 2), (2, 2), (2, 3) } S = {1, 2, 3} o R+ = { (1, 2), (2, 2), (2, 3), (1, 3) } o R* = { (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3) } Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 Bài Nhập môn TA&FL 23 1.1 Giới thiệu môn học TA&FL 1.2 Yêu cầu với môn học 1.3 Tài liệu tham khảo mơn TA&FL 1.4 Bổ túc số khái niệm tốn học 1.4.1 Tập hợp 1.4.2 Quan hệ 1.4.3 Phép chứng minh 1.4.4 Đồ thị Automata ngôn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 1.4.3 Phép chứng minh 24  Chứng minh trực tiếp: Áp dụng phép suy diễn lôgic (phép kéo theo) cách tuần từ theo bước: A1  A2   Ak B  Ví dụ 1.9: chứng minh với số nguyên n biểu thức: n2 - n +5 biểu diễn số lẻ Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 1.4.3 Phép chứng minh 25  Chứng minh lựa chọn: áp dụng phương pháp chứng minh trực tiếp cho tất trường hợp riêng toán: Case 1: A1  B Case 2: A2  B … Case n: An  B  Ví dụ 1.10: chứng minh với số nguyên n biểu thức: 9n2 + 3n -2 biểu diễn số chẵn Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 1.4.3 Phép chứng minh 26  Chứng minh phản chứng: trường hợp bắt đầu lập luận liệt kê trường hợp, ta áp dụng luật phủ định phủ định, có nghĩa chứng minh phủ định A sai  Ví dụ 1.11: chứng minh n số nguyên n2 chẵn n số chẵn  Ví dụ 1.12: chứng minh x số thực x2 – 4x+17 Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 1.4.3 Phép chứng minh 27  Chứng minh quy nạp: o Bước (cơ sở quy nạp): chứng minh P(0) o Bước (giả thiết quy nạp): giả sử P(n-1) o Bước (quy nạp): P(n - 1)  P(n),  n   Ví dụ 1.13: chứng minh: n (n  1)(2n  1) i  i 0 n n(n  1) i  i 0 n  n(n  1)  i      i 0 n Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 Bài Nhập môn TA&FL 28 1.1 Giới thiệu môn học TA&FL 1.2 Yêu cầu với môn học 1.3 Tài liệu tham khảo môn TA&FL 1.4 Bổ túc số khái niệm toán học 1.4.1 Tập hợp 1.4.2 Quan hệ 1.4.3 Phép chứng minh 1.4.4 Đồ thị Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 1.4.4 Đồ thị 29  Khái niệm đồ thị (graph): đồ thị đôi G = (V, E) (hoặc ký hiệu G(V, E)), đó: o V : tập đỉnh (nút); o E : tập cạnh nối nút  Nếu đỉnh có tối đa cạnh, ta gọi đồ thị đơn  Ví dụ 1.14: đồ thị G = (V, E) đơn đồ thị: Chicago San Franciso Denver Detroit New York Washington Los Angales Automata ngôn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 1.4.4 Đồ thị 30  Một cạnh (u, v) G (V, E) thường viết uv (hay vu), ta nói cạnh uv nối u với v, lúc đó, ta nói u v đỉnh kề Nếu đỉnh có nhiều cạnh ta gọi chúng cạnh bội (hoặc cạnh song song) Đồ thị G, trường hợp này, đa đồ thị  Ví dụ 1.15: đồ thị G = (V, E) đa đồ thị: Chicago San Franciso Denver Detroit New York Washington Los Angales Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 1.4.4 Đồ thị 31  Nếu cạnh nối đỉnh với (ví dụ: uu, vv, ) ta gọi cạnh khun  Ví dụ 1.16: đa đồ thị G(V, E) đưới có chứa khuyên: Detroit San Franciso New York Chicago Denver Washington Los Angales Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 1.4.4 Đồ thị 32  (Đa) đồ thị có hướng (directed graph) G = (V, E) o V : tập đỉnh (nút) o E : tập cung có hướng v  w  Ví dụ 1.17: đồ thị G = (V, E) đa đồ thị có hướng: Detroit Chicago New York San Franciso Denver Washington Los Angales Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 1.4.4 Đồ thị 33  Phân biệt dạng đồ thị: Loại Cạnh Có cạnh bội? Có khuyên? Đơn đồ thị Đa đồ thị Giả đồ thị Đồ thị có hướng Đa đồ thị có hướng Vơ hướng Vơ hướng Vơ hướng Có hướng Có hướng Khơng Có Có Khơng Có Khơng Khơng Có Có Có  Cây: đồ thị có hướng gồm o nút gốc (root) o Các nút trung gian (nút trong: có nút cha nút con) o Các nút lá: không dẫn nút Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 1.4.4 Đồ thị 34  Ví dụ 1.18: Cho sau: 10  Duyệt cây: Duyệt theo thứ tự trước: 1, 2, 5, 6, 3, 4, 7, 9, 10, Duyệt theo thứ tự giữa: 5, 2, 6, 1, 3, 9, 7, 10, 4, Duyệt theo thứ tự sau: 5, 6, 2, 3, 9, 10, 7, 8, 4, Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 1.4.4 Đồ thị 35  Ví dụ 1.19: minh họa cấu trúc cú pháp câu ‘An sinh viên giỏi’ Câu đơn Chủ ngữ Danh từ Vị ngữ Động từ Bổ ngữ Danh từ An Tính từ sinh viên giỏi Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 Tài liệu tham khảo 36  Kenneth H Rosen Toán rời rạc ứng dụng tin học.- NXBKHKT, 2000  Nguyễn Tơ Thành, Nguyễn Đức Nghĩa Tốn rời rạc.NXBGD, 2000 Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2012 ... Automata ngơn ngữ hình thức - ©copyright by PhD C.T.Ha, Le Quy Don Technical University 07/03/2 012 1. 3 Tài liệu môn học 11 Bài giảng giảng viên Nguyễn Gia Định Lý thuyết ngôn ngữ hình thức ơtơmát... sử P(n -1 ) o Bước (quy nạp): P(n - 1)  P(n),  n   Ví dụ 1. 13: chứng minh: n (n  1) (2n  1) i  i 0 n n(n  1) i  i 0 n  n(n  1)  i      i 0 n Automata ngơn ngữ hình thức - ©copyright... TA&FL 12 1. 1 Giới thiệu môn học TA&FL 1. 2 Yêu cầu với môn học 1. 3 Tài liệu tham khảo mơn TA&FL 1. 4 Bổ túc số khái niệm tốn học 1. 4 .1 Tập hợp 1. 4.2 Quan hệ 1. 4.3 Phép chứng minh 1. 4.4 Đồ thị Automata