BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PH ÒNG ISO 9001:2008 ĐỀ CƯƠNG CHI TIẾT MÔN HỌC OTOMAT VÀ NGÔN NG Ữ HÌNH THỨC Mã môn: FLO32021 Dùng cho các ngành CÔNG NGHỆ THÔNG TIN Bộ môn phụ trách MẠNG VÀ HỆ THỐNG THÔNG TIN THÔNG TIN VỀ CÁC GIẢNG VIÊN CÓ THỂ THAM GIA GIẢNG DẠY MÔN HỌC 1. Ths. Đỗ Xuân Toàn – Giảng viên cơ hữu - Chức danh, học hàm, học vị: Thạc sỹ - Thuộc bộ môn: Mạng và hệ thống thông tin - Địa chỉ liên hệ: Bộ môn Mạng và hệ thống thông tin - Điện thoại: 031.3739878. Email: [email protected] - Các hướng nghiên cứu chính: Mạng máy tính, Quản trị mạng, bảo mật mạng, Lập trình C++, Lập trình hướng đối tượng. 2. Ths. Đỗ Văn Chiểu – Giảng viên cơ hữu - Chức danh, học hàm, học vị: Thạc sỹ - Thuộc bộ môn: Mạng và Hệ thống Thông tin - Địa chỉ liên hệ: Mạng và Hệ thống Thông tin - Điện thoại: 3739878 Email: [email protected] - Các hướng nghiên cứu chính: Trí tuệ nhân tạo, Công nghệ phần mềm. 3. Thông tin về trợ giảng (nếu có): - Họ và tên: - Chức danh, học hàm, học vị: - Thuộc bộ môn/lớp: - Địa chỉ liên hệ: - Điện thoại: Email: - Các hướng nghiên cứu chính: THÔNG TIN VỀ MÔN HỌC 1. Thông tin chung: - Số đơn vị học trình/ tín chỉ: 3/2 - Các môn học tiên quyết: Logic Toán, Lý thuyết đồ thị - Các môn học kế tiếp: Chương trình dịch - Các yêu cầu đối với môn học (nếu có): - Thời gian phân bổ đối với các hoạt động: + Nghe giảng lý thuyết: 22 tiết + Làm bài tập trên lớp: 20 tiết + Thảo luận: + Thực hành, thực tập (ở PTN, nhà máy, điền dó,...): 0 tiết + Hoạt động theo nhóm: + Tự học: 90 tiết + Kiểm tra: 3 tiết 2. Mục tiêu của môn học: - Kiến thức: Cung cấp cho sinh viên các khái ni ệm về ngôn ngữ, văn phạm, ôtômát hữ hạn, ôtômát đẩy xuống, biểu thức chính quy, … làm cơ s ở cho nghiên cứu tin học về mặt lý thuyết và cũng làm cơ sở để học tiếp môn Chương trình dịch - Kỹ năng: Giải các bài toán về văn phạm chính quy và otomat hữu hạn, phương pháp giải các bài toán lien quan tới văn phạm phi ngữ cảnh và otomat đẩy xuống. - Thái độ: Yêu thích môn học ,thấy được vai trò của môn học trong các ứng dụng thực tiễn và là nền tảng cho sự phát triển thêm của các môn học tiếp theo 3. Tóm tắt nội dung môn học: - Bài giảng giới thiệu bốn chương:Chương mở đầu trình bày các khái niệm cơ bản về ngôn ngữ và cách xác định ngôn ngữ. Chương 2 giới thiệu về ôtômát hữu hạn và biểu thức chính qui. Văn phạm phi ngữ cảnh và văn phạm chính qui thì được đề cập đến trong chương 3. Chương 4 tr ình bày ôtômát đẩy xuống. 4. Học liệu: Học liệu bắt buộc: [1].Đỗ Đức Giáo, Toán Rời rạc, Nhà xuất bản Giáo dục, 2005. Học liệu tham khảo [2].Nguyễn Văn Ba, Ngôn ngữ hình thức, NXB KHKT 2002 [3].Đoàn Văn Ban, Giáo trình Ôtômát và Ngôn ngữ hình thức, ĐHQG HN 2003 [4].Đặng Huy Ruận, Lý thuyết Ngôn ngữ h ình thức và Ôtômát, NXB ĐHQG HN 2002 5. Nội dung và hình thức dạy – học: Hình thức dạy – học Nội dung TH, Tổng Lý Bài Thảo Tự học, Kiểm (Ghi cụ thể theo từng chương, mục, tiểu mục) TN, (tiết) thuyết tập luận tự NC tra điền dã Chương 1: Đại cương về ngôn ngữ hình 6 4 24 1 35 thức và cách xác định ngôn ngữ 1.1. Khái niệm chung về ngôn ngữ 1.2. Văn phạm và ngôn ngữ sinh bởi văn phạm. 1.3. Phân loại văn phạm của Chomsky. 1.4. Một số thí dụ về văn phạm. 1.5. Một số tính chất của văn phạm 1.6. Hai bài toán điển hình Bài tập cuối chương Chương2:Ôtomathữu hạn và biểu thức 6 4 24 1 35 chính quy. 2.1. Ôtômat hữu hạn 2.2. Ngôn ngữ chính quy và biểu thức chính quy 2.3. Các tính chất đóng của lớp các ngôn ngữ chính quy 2.4. Bài tập cuối chương Kiểm tra Chương3:Văn phạm phi ngữ cảnh 6 5 24 35 3.1. Xuất xứ và định nghĩa văn phạm phi ngữ cảnh (VPPNC). 3.2. Cây suy dẫn và sự nhập nhằng trong VPPNC 3.3. Giản lược các VPPNC 3.4. Bài tập cuối chương Hình thức dạy – học Nội dung TH, Tổng Lý Bài Thảo Tự học, Kiểm (Ghi cụ thể theo từng chương, mục, tiểu mục) TN, (tiết) thuyết tập luận tự NC tra điền dã Chương4:Ôtoomat đẩy xuống 4.1. Mô tả phi hình thức. 4.2. Định nghĩa Ôtômat đẩy xuống. 5 3 18 1 27 4.3. Mối liên quan giữa các dạng khác nhau của Ôtômat đẩy xuống 4.4. Sự tương đương giữa Ôtômat đẩy xuống và VPPNC 4.5. Bài tập cuối chương Ôn tập cuối kỳ 3 3 Tổng (tiết) 22 20 0 90 3 135 6. Lịch trình tổ chức dạy – học cụ thể: Chi tiết về hình thức Nội dung yêu cầu sv Ghi Tuần Nội dung tổ chức dạy – học phải chuẩn bị trước chú Chương 1: Đại cương về ngôn ngữ hình thức và cách xác định ngôn ngữ 1.1. Khái niệm chung về ngôn ngữ Ôn các kiến thức về 1 Giảng bài trên lớp. 3 tiết 1.2. Văn phạm và ngôn ngữ sinh tập hợp bởi văn phạm. 1.3. Phân loại văn phạm của Chomsky. 1.4. Một số thí dụ về văn phạm. Giảng bài trên lớp, Nắm vững các kiến 2 1.5. Một số tính chất của văn phạm Sinh viên làm bài 4 tiết thức của baig trước. 1.6. Hai bài toán điển hình trên lớp Nắm vững cách vận Sinh viên làm bài dụng các kiến thức tập trên lớp bài trước để thực 3 Bài tập cuối chương 3 tiết Chữa bài tâp trên hiện bài tập. Sinh lớp viên cần thực hiện bài tập đã cho. Kiểm tra lần 1 1tiết Chương 2: Ôtomat hưỡu hạn và 4 Giảng bài trên lớp biểu thức chính quy 2 tiết 2.1. Ôtômat hữu hạn 2.2. Ngôn ngữ chính quy và biểu thức chính quy 5 Giảng bài trên lớp 3 tiết 2.3. Các tính chất đóng của lớp các ngôn ngữ chính quy Hướng dẫn làm bài 6 2.4. Bài tập cuối chương 2 tiết tập trên lớp 2.4. Bài tập cuối chương Chữa bài tập trên 2t 7 Làm trước bài tập Kiểm tra lần 2 lớp 1t Chương 3: Văn phạm phi ngữ cảnh 3.1. Xuất xứ và định nghĩa văn 8 phạm phi ngữ cảnh (VPPNC). Giảng bài trên lớp 3.2. Cây suy dẫn và sự nhập nhằng 3 tiết trong VPPNC 9 3.3. Giản lược các VPPNC Giảng bài trên lớp 3t Hướng dẫn làm bài 10 3.4. Bài tập cuối chương 3 tiết tập trên lớp 3.4. Bài tập cuối chương Chữa bài tập trên 2 tiết 11 Chương 4: Ôtomat đẩy xuống lớp Làm trước bài tập 1 tiết 4.1. Mô tả phi hình thức Giảng bài trên lớp 4.2. Định nghĩa Ôtômat đẩy xuống. 12 4.3. Mối liên quan giữa các dạng Giảng bài trên lớp 3 tiết khác nhau của Ôtômat đẩy xuống 4.4. Sự tương đương giữa Ôtômat Giảng bài trên lớp 1 tiết 13 đẩy xuống và VPPNC Hướng dẫn làm bài 2 tiết 4.5. Bài tập cuối chương tập trên lớp 4.5. Bài tập cuối chương Chữa bài tập trên 2t 14 Làm trước bài tập Kiểm tra lần 3 lớp 1t Ôn lại các kiến thức 15 Ôn tập cuối kỳ Giải đáp trên lớp 3 tiết đã học