Bài giảng Ngôn ngữ hình thức: Chương 1 Đại cương về ngôn ngữ và biểu diễn ngôn ngữ, cung cấp cho người học những kiến thức như: Nhắc lại một số kiến thức toán liên quan; Khái niệm chung về ngôn ngữ; Hệ viết lại và vấn đề biểu diễn ngôn ngữ; Văn phạm. Mời các bạn cùng tham khảo! | NGÔN NGỮ HÌNH THỨC GV Nguyễn Thị Hồng Email nguyenhong@ Giới thiệu môn học Số tín chỉ 3 Chuyên cần nghỉ quá 20 số buổi Cấm thi Điểm giữa kì 4 bài Kiểm tra viết Bài tập nhóm Điểm giữa kì Chương 1 ĐẠI CƯƠNG VỀ NGÔN NGỮ VÀ BIỂU DIỄN NGÔN NGỮ Nội dung I. Nhắc lại một số kiến thức toán liên quan II. Khái niệm chung về ngôn ngữ III. Hệ viết lại và vấn đề biểu diễn ngôn ngữ IV. Văn phạm I. Một số kiến thức toán liên quan Tập hợp Kí hiệu A B C Cách cho Liệt kê A 0 2 4 6 8 Chỉ ra tính chất của phần tử B x x là số chẵn Tập hợp Các phép toán trên tập hợp Hợp A B x x A hoặc x B Giao A B x x A và x B Hiệu A B x x A và x B Tích Đề các A B a b a A và b B Lũy thừa 2A hay A là tập mọi tập con của A Quan hệ Định nghĩa Cho hai tập hợp A và B. Ta gọi quan hệ hai ngôi giữa A và B là tập hợp các cặp có thứ tự a b sao cho a A và b B. R A B Kí hiệu R a b R ta viết aRb Tính chất R a a a A là quan hệ đồng nhất trên A Phản xạ nếu a A aRa Bắc cầu truyền ứng a b c A aRb và bRc kéo theo aRc Đối xứng a b A aRb kéo theo bRa. R là phản đối xứng nếu a b A aRb và bRa kéo theo a b Quan hệ Quan hệ phản xạ và truyền ứng quan hệ tiền thứ tự Quan hệ tiền thứ tự đối xứng quan hệ tương đương Quan hệ tiền thứ tự phản đối xứng quan hệ thứ tự bộ phận Quan hệ thứ tự bộ phận sao cho a b A aRb hoặc bRa quan hệ thứ tự toàn phần VD quan hệ Quan hệ Bao đóng của quan hệ Bao đóng truyền ứng phản xạ đối xứng của quan hệ R trên tập A là tập nhỏ nhất chứa quan hệ đã cho mà có tính chất truyền ứng phản xạ đối xứng Ví dụ Cho tập A x1 x2 x3 Một quan hệ trên tập A R x1 x1 x1 x2 x2 x3 Bao đóng phản xạ của R x1 x1 x1 x2 x2 x3 x2 x2 x3 x3 Đồ thị Định nghĩa Đồ thị G V E trong đó V là một tập hữu hạn các đỉnh hay nút E là tập hợp các cặp đỉnh cạnh Ví dụ G V E trong đó V 1 2 3 4 5 6 E 1 2 1 5 2 3 2 5 3 4 4 5 4 6 Đồ thị Đồ thị có hướng G V E trong đó E là cặp đỉnh có thứ tự cung Cây là đồ thị có hướng có một nút là Gốc các nút cha nút con II. Ngôn ngữ Bộ chữ Xâu Các phép toán trên xâu Ngôn ngữ Các phép toán trên ngôn .
