tailieunhanh - Bài giảng Ngôn ngữ hình thức - ĐH Lâm Nghiệp

Sau khi học xong môn học này sinh viên có thể hiểu sâu hơn cấu trúc của các ngôn ngữ lập trình, các chương trình dịch cũng như bản chất của thuật toán và độ phức tạp tính toán của chúng. Nội dung chính của các chương như sau: Văn phạm và ngôn ngữ phi hình thức; Otomat hữu hạn và ngôn ngữ chính quy; Otomat đẩy xuống và ngôn ngữ phi ngữ cảnh; Máy Turing. | ThS. ĐẶNG THỊ KIM ANH NG N NG H NH THøC TRƯỜNG ĐẠI HỌC LÂM NGHIỆP - 2019 ThS. ĐẶNG THỊ KIM ANH BÀI GIẢNG NGÔN NGỮ HÌNH THỨC TRƢỜNG ĐẠI HỌC LÂM NGHIỆP - 2019 MỤC LỤC DANH MỤC CÁC HÌNH SƠ ĐỒ . iii LỜI NÓI ĐẦU .1 Chƣơng 1. VĂN PHẠM VÀ NGÔN NGỮ HÌNH THỨC .3 . Các khái niệm cơ bản về ngôn ngữ hình thức .3 . Bảng chữ cái .3 . Từ .3 . Ngôn . Các phép toán trên các từ .4 . Phép nhân ghép .4 . Phép lấy từ ngược .5 . Phép chia từ .6 . Các phép toán trên ngôn ngữ .6 . Phép hợp .6 . Phép giao .7 . Phép lấy phần bù .7 . Phép nhân ghép .8 . Phép lặp .9 . Phép lấy ngôn ngữ ngược .10 . Phép chia ngôn ngữ .10 . Văn phạm và ngôn ngữ sinh bởi văn . Định nghĩa văn . Ngôn ngữ sinh bởi văn phạm .12 . Phân loại văn phạm theo Chomsky .14 . Các tính chất của văn phạm và ngôn ngữ sinh bởi văn phạm .17 . Một số tính chất của văn phạm và dẫn xuất .17 . Tính đóng của lớp ngôn ngữ sinh bởi văn phạm .19 Chƣơng 2. OTOMAT HỮU HẠN VÀ NGÔN NGỮ CHÍNH QUY .24 . Otomat hữu hạn đơn . Otomat hữu hạn đơn định .24 . Biểu diễn otomat hữu hạn đơn . Ngôn ngữ được đoán nhận bởi otomat đơn định .28 . Otomat hữu hạn không đơn . Định nghĩa Otomat hữu hạn không đơn định .30 . Ngôn ngữ được đoán nhận bởi otomat hữu hạn không đơn định .31 i . Đơn định hóa các otomat . 32 . Sự tương đương giữa otomat đơn định và otomat không đơn định . 35 . Ngôn ngữ chính quy và biểu thức chính quy . 36 . Ngôn ngữ chính quy và biểu thức chính quy . 36 . Sự liên hệ giữa otomat hữu hạn và ngôn ngữ chính quy . 38 . Điều kiện cần của ngôn ngữ chính quy. 40 . Otomat tối tiểu . 41 . Điều kiện cần của ngôn ngữ chính quy . 41 Chƣơng 3. OTOMAT ĐẨY XUỐNG VÀ NGÔN NGỮ PHI NGỮ CẢNH . 45 . Văn phạm phi ngữ cảnh và cây suy dẫn của nó . 45 . Cây suy dẫn đầy đủ trong văn phạm phi ngữ cảnh . 45 . Rút gọn các văn phạm phi .