ÔTÔMÁT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY Nội dung chính: Trong chương này, ta sẽ nghiên cứu một loại "máy trừu tượng" gọi là ôtômát hữu hạn. Chúng là công cụ dùng đoán nhận một lớp ngôn ngữ khá đơn giản gọi là lớp ngôn ngữ chính quy. Trước hết, hai dạng của ôtômát hữu hạn sẽ lần lượt được trình bày và có sự chứng minh rằng chúng tương đương nhau về khả năng đoán nhận ngôn ngữ. Tiếp đó, ta sẽ đề cập đến biểu thức chính quy - một phương tiện khác để xác định. | Chương III ồtômát hữu hạn và biểu thức chính quy CHƯƠNG III ÔTÔMÁT HỮU HẠN VÀ BIÊU THỨC CHÍNH QUY Nội dung chính Trong chương này ta sẽ nghiên cứu một loại máy trừu tượng gọi là ôtômát hữu hạn. Chúng là công cụ dùng đoán nhận một lớp ngôn ngữ khá đơn giản gọi là lớp ngôn ngữ chính quy. Trước hết hai dạng của ôtômát hữu hạn sẽ lần lượt được trình bày và có sự chứng minh rằng chúng tương đương nhau về khả năng đoán nhận ngôn ngữ. Tiếp đó ta sẽ đề cập đến biểu thức chính quy - một phương tiện khác để xác định ngôn ngữ và ta lại thấy rằng lớp ngôn ngữ do các ôtômát hữu hạn chấp nhận chính là lớp ngôn ngữ chính quy. Phần tiếp theo của chương sẽ đề cập đến mối quan hệ giữa cơ chế ôtômát và các biểu thức chính quy dùng ký hiệu cho ngôn ngữ. Cuối chương này một vài ứng dụng cụ thể của ôtômát hữu hạn sẽ được trình bày. Mục tiêu cần đạt Kết thúc chương này sinh viên cần nắm vững Khái niệm ôtômát hữu hạn các thành phần các dạng và sự khác biệt cơ bản giữa hai dạng. Cách thức chuyển đổi tương đương từ dạng đơn định sang không đơn định và ngược lại. Viết biểu thức chính quy ký hiệu cho tập ngôn ngữ chính quy. Mối liên quan giữa ôtômát hữu hạn và biểu thức chính quy. Vẽ sơ đồ chuyển trạng thái đơn định hoặc không đơn định từ một biểu thức chính quy. Tìm các ứng dụng thực tế khác từ mô hình ôtômát hữu hạn. Kiến thức cơ bản Để tiếp thu tốt nội dung của chương này sinh viên cần có một số các kiến thức liên quan về lý thuyết đồ thị lý thuyết mạch hiểu các khái niệm cơ bản về kiến trúc máy tính có sử dụng qua một số trình soạn thảo văn bản thông thường . Tài liệu tham khảo 1 John E. Hopcroft Jeffrey - Introduction to Automata Theory Languages and Computation - Addison - Wesley Publishing Company Inc -1979 Chapter 2 Finite Automata and Regular Expressions . 2 Phan Thị Tươi - Trình biên dịch - Nhà xuất bản Giáo dục - 1986 Chương 3 Bộ phân tích từ vựng . 20 Chương III ồtômát hữu hạn và biểu thức chính quy 3 and Theory of Finite Automata http .
