Bài giảng Ôtômát và ngôn ngữ hình thức: Chương 3 Văn phạm chính quy và ôtômát hữu hạn cung cấp cho người học những kiến thức như: Ôtômát hữu hạn đơn định - DFA; Ôtômát hữu hạn không đơn định - NFA; Sự tương đương của NFA và DFA; Mối liên quan giữa VPCQ và OH; OHD không xuất phát lại; Các tính chất đóng của ngôn ngữ chính quy; Định lý KLEENE; Biểu thức chính quy; Thuật toán Thampson. | Nội dung Chương 3 1. Ôtômát hữu hạn đơn định - DFA. 2. Ôtômát hữu hạn không đơn định - NFA. VĂN PHẠM CHÍNH QUY 3. Sự tương đương của NFA và DFA VÀ 4. Mối liên quan giữa VPCQ và OH 5. OHD không xuất phát lại ÔTÔMÁT HỮU HẠN 6. Các tính chất đóng của ngôn ngữ chính quy. 7. Định lý KLEENE. 8. Biểu thức chính quy. 9. Thuật toán Thampson 2 Ôtômát hữu hạn đơn định DFA Deterministic Finite Automata Input w Mô tả phi hình thức 0 1 1 0 0 1 1 1 1 Ôtômát hữu hạn như một máy đoán nhận chuỗi nó Băng từ sức chứa vô hạn làm việc như sau Băng từ chia thành nhiều ô. Mỗi ô có khả năng lưu Output Yes w L q Bộ điều khiển trữ một ký hiệu của chuỗi nhập chuỗi cần được No w L đoán nhận w є . Tùy theo cấu hình hiện tại gồm trạng thái hiện thời của bộ điều khiển và ký hiệu trên ô mà đầu đọc quan sát được mà Ôtômát Có một đầu đọc ở mỗi thời điểm quan sát một ô trên chuyển sang trạng thái mới đồng thời đầu đọc dịch chuyển băng từ. sang phải một ô. Có một bộ điều khiển Q gồm tập hợp hữu hạn trạng thái ở mỗi thời điểm có một trạng thái hiện hành gọi Quy luật chuyển sang trạng thái mới được cho bởi một hàm gọi là hàm chuyển trạng thái Q x Q. là trạng thái nội. 3 4 1 Trong Q có phân biệt q0 Q gọi là trạng thái đầu và một tập hợp F chứa các trạng thái kết thúc. Định nghĩa hình thức Một ôtômát hữu hạn đơn định viết tắt là Ta nói ôtômát đoán nhận hay thừa nhận một chuỗi vào w nếu xuất phát từ q0 đầu đọc nhìn vào ký hiệu bên trái ÔHĐ là một hệ thống M Q q0 F trong đó nhất của w sau một số bước hữu hạn làm việc nó đọc xong là một bộ chữ cái hữu hạn gọi là bộ chữ vào. chuỗi w và rơi vào một trong các trạng thái kết thúc. Q là một tập hữu hạn các trạng thái Q . Tập hợp mọi chuỗi được đoán nhận bởi Ôtômát hợp thành Q x Q được gọi là hàm chuyển. ngôn ngữ được đoán nhận bởi ôtômát đó. Do Q là hữu hạn và hàm chuyển là hàm toàn phần và đơn q0 Q là trạng thái đầu. trị cho nên bước chuyển của Ôtômát được xác định một F Q là tập các trạng thái cuối. cách duy nhất. Chính vì vậy mà Ôtômát mô tả như trên được gọi
