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.
Nội dung trích xuất từ tài liệu:
Bài giảng Ngôn ngữ hình thức - ĐH Lâm Nghiệp ThS. ĐẶNG THỊ KIM ANHNG¤N NG÷ H×NH THøC TRƯỜNG ĐẠI HỌC LÂM NGHIỆP - 2019 ThS. ĐẶNG THỊ KIM ANH BÀI GIẢNGNGÔN NGỮ HÌNH THỨC TRƢỜNG ĐẠI HỌC LÂM NGHIỆP - 2019 MỤC LỤCDANH MỤC CÁC HÌNH, SƠ ĐỒ ............................................................................... iiiLỜI NÓI ĐẦU .................................................................................................................1Chương 1. VĂN PHẠM VÀ NGÔN NGỮ HÌNH THỨC ..........................................3 1.1. Các khái niệm cơ bản về ngôn ngữ hình thức ......................................................3 1.1.1. Bảng chữ cái .................................................................................................3 1.1.2. Từ ..................................................................................................................3 1.1.3. Ngôn ngữ.......................................................................................................4 1.2. Các phép toán trên các từ .....................................................................................4 1.2.1. Phép nhân ghép ............................................................................................4 1.2.2. Phép lấy từ ngược .........................................................................................5 1.2.3. Phép chia từ ..................................................................................................6 1.3. Các phép toán trên ngôn ngữ ...............................................................................6 1.3.1. Phép hợp .......................................................................................................6 1.3.2. Phép giao ......................................................................................................7 1.3.3. Phép lấy phần bù ..........................................................................................7 1.3.4. Phép nhân ghép ............................................................................................8 1.3.5. Phép lặp ........................................................................................................9 1.3.6. Phép lấy ngôn ngữ ngược ...........................................................................10 1.3.7. Phép chia ngôn ngữ ....................................................................................10 1.4. Văn phạm và ngôn ngữ sinh bởi văn phạm........................................................10 1.4.1. Định nghĩa văn phạm..................................................................................11 1.4.2. Ngôn ngữ sinh bởi văn phạm ......................................................................12 1.4.3. Phân loại văn phạm theo Chomsky ............................................................14 1.5. Các tính chất của văn phạm và ngôn ngữ sinh bởi văn phạm ............................17 1.5.1. Một số tính chất của văn phạm và dẫn xuất ...............................................17 1.5.2. Tính đóng của lớp ngôn ngữ sinh bởi văn phạm ........................................19Chương 2. OTOMAT HỮU HẠN VÀ NGÔN NGỮ CHÍNH QUY .......................24 2.1. Otomat hữu hạn đơn định...................................................................................24 2.1.1. Otomat hữu hạn đơn định ...........................................................................24 2.1.2. Biểu diễn otomat hữu hạn đơn định............................................................25 2.1.3. Ngôn ngữ được đoán nhận bởi otomat đơn định ........................................28 2.2. Otomat hữu hạn không đơn định........................................................................30 2.2.1. Định nghĩa Otomat hữu hạn không đơn định .............................................30 2.2.2. Ngôn ngữ được đoán nhận bởi otomat hữu hạn không đơn định ...............31 i 2.2.3. Đơn định hóa các otomat ........................................................................... 32 2.2.4. Sự tương đương giữa otomat đơn định và otomat không đơn định ........... 35 2.3. Ngôn ngữ chính quy và biểu thức chính quy ..................................................... 36 2.3.1. Ngôn ngữ chính quy và biểu thức chính quy .............................................. 36 2.3.2. Sự liên hệ giữa otomat hữu hạn và ngôn ngữ chính quy ............................ 38 2.4. Điều kiện cần của ngôn ngữ chính quy.............................................................. 40 2.4.1. Otomat tối tiểu .................................................................................. ...