tailieunhanh - Lý thuyết Ngôn ngữ hình thức và Automata

Vào những năm 1930, Alain Turing đã nghiên cứu trừu tượng có khả năng thực hiện các tính toán như máy tính hàng ngày. Các máy trừu tượng này được gọi là máy Twing. Vào những năm 1940 và 1950 các máy trừu tượng đơn giản hơn, mà chúng ta gọi là Ôtômat hữu hạn. | Khoa Công nghệ Thông tin Trường Đại học Bách khoa Đại học Đà Nắng GIÁO TRÌNH LÝ THUYẾT NGÔN NGỮ HÌNH THỨC VÀ ÔTÔMÁT Nguyễn Thanh Bình Đà Nắng 2007 Mục lục Chương 1. Mở đầu. 6 Giới Khái niệm về ngôn Bảng chữ alphabet .6 Xâu String .7 Các phép toán trên Ngôn Các phép toán trên ngôn Khái niệm về văn Khái niệm về Chương 2. Ôtômát hữu hạn__12 Ôtômát hữu hạn đơn định deterministic finite automata - DFA .12 Mô tả không hình Mô tả hình DFA xử lí xâu như thế Các cách biểu diễn đơn giản hơn của Hàm dịch chuyển mở Ngôn ngữ được thừa nhận bởi Bài tập. 17 Ôtômát hữu hạn không đơn định non deterministic finite automata - NFA 17 Định nghĩa hình thức Hàm dịch chuyển mở rộng . 18 Ngôn ngữ được thừa nhận bởi Sự tương đương giữa DFA và Xây dựng DfA từ Sự tương đương giữa NFA và Bài ứng NFA cho tìm kiếm từ DFA cho tìm kiếm từ Bài Chương 3. Biểu thức chỉnh quy và văn phạm chỉnh quy. 27 2 Biểu thức chính quy regular expresssion .27 Định nghĩa hình thức của biểu thức chính Độ uu tiên các phép toán trên biểu thức chính Các tính chất đại số của biểu thức chính Bài Biểu thức chính quy và ngôn ngữ chính Bài ứng dụng của biểu thức chính Phân tích từ vựng lexical analysis .33 Văn phạm chính Văn phạm tuyến tính phải và văn phạm tuyến tính Ngôn ngữ chính quy và văn phạm chính Bài Các tính chất đóng của ngôn ngữ chính Tính đóng của ngôn ngữ chính quy duới các phép toán tập Tính đóng duới các phép toán Các thuật