Giáo trình Ôtômát và ngôn ngữ hình thức: Phần 1

Giáo trình này giới thiệu một cách hệ thống những khái niệm cơ bản và các tính chất chung của ôtômát và ngôn ngữ hình thức. Phần 1 giáo trình gồm 4 chương đầu với nội dung sau: Chương mở đầu trình bày các khái niệm cơ bản, các tính chất quan trọng của các cấu trúc đại số, logic mệnh đề, logic tân từ và các phương pháp suy luận toán học làm cơ sở cho các chương sau. Chương 2 giới thiệu về lý thuyết ôtômát, những khái niệm cơ sở và các hoạt động của ôtômát. Văn phạm và các ngôn ngữ hình thức được đề cập đến ở chương 3. Những vấn đề liên quan đến tập chính qui, ngôn ngữ chính qui và ôtômát hữu hạn được trình bày chi tiết ở chương 4.
Nội dung trích xuất từ tài liệu:
Giáo trình Ôtômát và ngôn ngữ hình thức: Phần 1 Ôtômát và ngôn ngữ hình thức MỤC LỤC LỜI NÓI ĐẦU .......................................................................................................... 5 Chƣơng I: Mở đầu ................................................................................................... 8 1.1 Tập hợp và các cấu trúc đại số......................................................................... 8 1.1.1 Tập hợp và các tập con ............................................................................. 8 1.1.2 Tập hợp và các phép toán hai ngôi .......................................................... 9 1.3 Quan hệ và quan hệ tương đương .................................................................. 12 1.4 Hàm số .......................................................................................................... 15 1.5 Logic mệnh đề và tân từ .............................................................................. 16 1.5.1 Logic mệnh đề ........................................................................................ 16 1.6.2 Công thức mệnh đề ................................................................................. 18 1.5.3 Dạng chuẩn của các công thức ............................................................... 20 1.5.4 Các qui tắc suy diễn trong tính toán mệnh đề ........................................ 23 1.6 Tân từ (vị từ) và các lượng tử ........................................................................ 25 1.7 Các phương pháp chứng minh ...................................................................... 28 Bài tập về logic và lập luận ................................................................................. 30 Chƣơng II: Lý thuyết ôtômát ............................................................................... 35 2.1 Ôtômát hữu hạn ............................................................................................. 35 2.1.1 Các tính chất của hàm chuyển trạng thái ................................................ 38 2.1.2 Các phương pháp biểu diễn ôtômát ........................................................ 39 2.1.3 Ngôn ngữ đoán nhận được của ôtômát ................................................... 40 2.2 Ôtômát hữu hạn không đơn định .................................................................. 41 2.3 Sự tương đương của ôtômát đơn định và không đơn định ........................... 43 2.4 Cực tiểu hoá ôtômát hữu hạn ........................................................................ 47 Bài tập về ôtômát hữu hạn ................................................................................... 51 Chƣơng III: Văn phạm và ngôn ngữ hình thức .................................................. 53 3.1 Bảng chữ cái và các ngôn ngữ ...................................................................... 53 3.2 Các dẫn xuất và và ngôn ngữ sinh bởi văn phạm .......................................... 55 3.3 Phân loại các ngôn ngữ của Chomsky ........................................................... 62 3.4 Tính đệ qui và các tập đệ qui ......................................................................... 70 3.5 Các phép toán trên các ngôn ngữ ................................................................... 73 3.6 Ngôn ngữ và ôtômát ...................................................................................... 76 -1- Ôtômát và ngôn ngữ hình thức Bài tập về văn phạm và các ngôn ngữ sinh ......................................................... 77 Chƣơng IV: Tập chính qui và văn phạm chính qui ........................................... 80 4.1 Các biểu thức chính qui ................................................................................. 80 4.2 Sự tương đương của các biểu thức chính qui ................................................ 82 4.3 Ôtômát hữu hạn và biểu thức chính qui......................................................... 83 4.3.1 Các hệ biến đổi và các biểu thức chính qui ............................................ 85 4.3.2 Loại bỏ các - dịch chuyển trong các hệ thống biến đổi trạng thái ...... 87 4.3.3 Chuyển các hệ chuyển trạng thái không đơn định về hệ thống đơn định ......................................................................................................................... 88 4.3.4 Phương pháp đại số ứng dụng định lý Arden ......................................... 90 4.3.5 Thiết lập ôtômát hữu hạn tương đương với biểu thức chính qui ............ 93 4.3.6 Sự tương đương của hai biểu thức chính qui ......................................... 96 4.4 Bổ đề Bơm đối với các tập chính qui ............................................................ 97 4.5 Ứng dụng của bổ đề “Bơm” (điều kiện cần của ngôn ngữ chính qui) ......... 98 4.6 Các tính chất đóng của các tập chính qui ...................................................... 99 4.7 Các tập chính qui và văn phạm chính qui .................................................... 101 4.7.1 Xây dựng văn phạm chính qui tương đương với ÔTĐĐ cho trước ........... 101 4.7.2 Xây dựng ÔTĐĐ hữu hạn tương đương với văn phạm chính qui G.......... 102 4.8 Điều kiện cần và đủ của ngôn ngữ chính qui............................................... 103 4.8.1 Quan hệ tương đương bất biến phải ..................................................... 103 4.8.2 Điều kiện cần và đủ: Định lý Myhill - Nerode .................................... 103 Bài tập về biểu thức chính qui ........................................................................... 105 Chƣơng V: Các ngôn ngữ phi ngữ cảnh ............................................................ 109 5.1 Các ngôn ngữ phi ngữ cảnh và các cây dẫn xuất ......................................... 109 5.2 Sự nhập nhằng trong văn phạm phi ngữ cảnh ............................................. 114 5.3 Giản lược các văn phạm phi ngữ cảnh ........................................................ 115 5.3.1 Lược giản các văn phạm ...