Để đá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. . | 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 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. Giáo trình cũng được biên soạn dựa trên kinh 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ủa chú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 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ơ. 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ột tà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ủa cá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áo trì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ôi xin 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 đồng nghiệ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ỉnh hơ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@ MỤC LỤC LỜI NÓI ĐẦU TỔNG QUAN Chương I BỔ TÚC TOÁN . Tập . Quan . Phép chứng minh quy . Đồ thị và Bài tập Chương Chương II NGÔN NGỮ VÀ BIỂU DIỄN NGÔN NGỮ . Tổng quan về ngôn . Vấn đề biểu diễn ngôn ngữ. 13 . Văn phạm và các lớp văn . Cơ chế Bài tập Chương Chương III ÔTÔMÁT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY . Ôtômát hữu . Biểu thức chính . Sự tương đương giữa ôtômát hữu hạn và biểu thức chính . Một vài ứng dụng của ôtômát hữu 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 . Văn phạm chính .
