mucluc
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (156.56 KB, 2 trang )
MỤC LỤC
LỜI NÓI ĐẦU
TỔNG QUAN
Chương I
BỔ TÚC TOÁN
1.1. Tập hợp............................................................................................... 1
1.2. Quan hệ............................................................................................... 3
1.3. Phép chứng minh quy nạp .................................................................. 4
1.4. Đồ thị và cây....................................................................................... 5
Bài tập Chương I....................................................................................... 8
Chương II
NGÔN NGỮ VÀ BIỂU DIỄN NGÔN NGỮ
2.1. Tổng quan về ngôn ngữ...................................................................... 9
2.2. Vấn đề biểu diễn ngôn ngữ............................................................... 13
2.3. Văn phạm và các lớp văn phạm ....................................................... 14
2.4. Cơ chế Ôtômát.................................................................................. 17
Bài tập Chương II ................................................................................... 19
Chương III
ÔTÔMÁT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY
3.1. Ôtômát hữu hạn ................................................................................ 20
3.2. Biểu thức chính quy ......................................................................... 37
3.3. Sự tương đương giữa ôtômát hữu hạn và
biểu thức chính quy .......................................................................... 39
3.4. Một vài ứng dụng của ôtômát hữu hạn............................................. 45
Bài tập Chương III.................................................................................. 48
Chương IV
VĂN PHẠM CHÍNH QUY VÀ CÁC TÍNH CHẤT
4.1. Văn phạm chính quy......................................................................... 51
4.2. Một số tính chất của tập hợp chính quy ........................................... 56
4.3. Các giải thuật xác định tập hợp chính quy ....................................... 59
Bài tập Chương IV.................................................................................. 61
Chương V
VĂN PHẠM PHI NGỮ CẢNH
5.1. Định nghĩa văn phạm phi ngữ cảnh.................................................. 63
5.2. Giản lược văn phạm phi ngữ cảnh ................................................... 70
5.3. Chuẩn hóa văn phạm phi ngữ cảnh .................................................. 76
5.4. Tính chất của ngôn ngữ phi ngữ cảnh .............................................. 81
5.5. Các giải thuật quyết định CFL ......................................................... 85
Bài tập Chương V ................................................................................... 91
Chương VI
ÔTÔMÁT ĐẨY XUỐNG
6.1. Định nghĩa Ôtômát đẩy xuống ......................................................... 95
6.2. Ôtômát đẩy xuống và ngôn ngữ phi ngữ cảnh ............................... 102
Bài tập Chương VI................................................................................ 108
Chương VII
MÁY TURING
7.1. Định nghĩa TM ............................................................................... 110
7.2. Ngôn ngữ và “hàm tính được” ....................................................... 113
7.3. Các kỹ thuật xây dựng TM............................................................. 115
7.4. Các biến dạng của TM.................................................................... 121
7.5. Giả thuyết Church .......................................................................... 125
7.6. Máy Turing như là một bộ liệt kê................................................... 126
7.7. Sự tương đương giữa văn phạm kiểu 0 và máy Turing.................. 129
Bài tập Chương VII .............................................................................. 132
Chương VIII
ÔTÔMÁT TUYẾN TÍNH GIỚI NỘI VÀ VĂN PHẠM CẢM NGỮ
CẢNH
8.1. Ôtômát tuyến tính giới nội ............................................................. 133
8.2. Văn phạm cảm ngữ cảnh ................................................................ 134
8.3. Sự tương đương giữa LBA và CSG ............................................... 136
8.4. Tương quan giữa các lớp ngôn ngữ ............................................... 138
Bài tập Chương VIII............................................................................. 140
TÀI LIỆU THAM KHẢO
