Tin học lý thuyết - Chương 1

Để đáp ứng nhu cầu học tập của các bạn sinh viên, nhất là sinh viên chuyên ngành tin học, Khoa Công Nghệ Thông Tin - Trường Đại Học Cần Thơ chúng tôi đã tiến hành biên soạn các giáo trình, bài giảng chính trong chương trình học. Bài giảng môn Tin học lý thuyết này được biên soạn cơ bản dựa trên quyển “Introduction to Automata Theory, Languages and Computation” của John E. Hopcroft và Jeffrey D. Ullman, xuất bản bởi Addison-Wesley vào năm 1979. ...
Nội dung trích xuất từ tài liệu:
Tin học lý thuyết - Chương 1 LỜI NÓI ĐẦUĐể đáp ứng nhu cầu học tập của các bạn sinh viên, nhất là sinh viên chuyên ngành tinhọc, Khoa Công Nghệ Thông Tin - Trường Đại Học Cần Thơ chúng tôi đã tiến hànhbiên soạn các giáo trình, bài giảng chính trong chương trình học. Bài giảng môn Tinhọc lý thuyết này được biên soạn cơ bản dựa trên quyển “Introduction to AutomataTheory, Languages and Computation” của John E. Hopcroft và Jeffrey D. Ullman,xuất bản bởi Addison-Wesley vào năm 1979. Giáo trình cũng được biên soạn dựa trênkinh nghiệm giảng dạy nhiều năm môn Lý thuyết ngôn ngữ hình thức và Ôtômát củachúng tôi.Tài liệu này được soạn theo đề cương chi tiết môn Tin học lý thuyết dành cho sinhviên chuyên ngành Tin học - Khoa Công Nghệ Thông Tin Trường Đại Học Cần Thơ.Mục tiêu của nó nhằm giúp các bạn sinh viên chuyên ngành năm thứ ba, thứ tư có mộttài liệu cô đọng dùng làm tài liệu học tập, nhưng cũng không loại trừ sự tham khảo củacác đối tượng khác.Chúng tôi đã hết sức làm đơn giản hóa trong phạm vi có thể các nội dung trong giáotrình. Dù đã rất cố gắng nhưng có lẽ giáo trình vẫn còn nhiều thiếu sót và hạn chế. Tôixin chân thành cảm ơn và rất hoan nghênh các ý kiến đóng góp của các bạn đồngnghiệp gần, xa và của các bạn sinh viên để giáo trình môn học này được hoàn chỉnhhơn theo thời gian. Đại Học Cần Thơ, tháng 12 năm 2003 MSc. VÕ HUỲNH TRÂM Email : vhtram@cit.ctu.edu.vn MỤC LỤCLỜI NÓI ĐẦUTỔNG QUANChươ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 ....................................................................................... 8Chươ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 ................................................................................... 19Chươ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.................................................................................. 48Chươ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 .................................................................................. 61Chươ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 ................................................................................... 91Chươ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 ................................................................................ 108Chươ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 .............................................................................. 132Chươ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 ................................ ...