Bài giảng Lý thuyết tính toán: Bài 2 - Phạm Xuân Cường cung cấp cho học viên các kiến thức về ôtômat hữu hạn, biểu diễn hình học của Ôtômat hữu hạn; định nghĩa hình thức; thiết kế ôtômat hữu hạn; ngôn ngữ chính quy; toán tử chính quy; tính đóng của toán tử; . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | LÝ THUYẾT TÍNH TOÁN BÀI 2 ÔTÔMAT HỮU HẠN Phạm Xuân Cường Khoa Công nghệ thông tin cuongpx@ Nội dung bài giảng 1. Ôtômat hữu hạn 2. Định nghĩa hình thức 3. Thiết kế Ôtômat hữu hạn 4. Ngôn ngữ chính quy 5. Toán tử chính quy 1 Ôtômat hữu hạn Ôtômat hữu hạn Ôtômat hữu hạn Finite State Machine - FSM hay Finite Automation Là mô hình tính toán đơn giản nhất Phù hợp với - Các máy tính hoặc bộ điều khiển nhỏ - Có số trạng thái hữu hạn và khá nhỏ Ví dụ Bộ điều khiển cửa trượt tự động Không Trước Sau Cả hai Trước Sau Đóng Mở Không 2 Biểu diễn hình học của Ôtômat hữu hạn 0 1 1 0 start q1 q2 q3 0 1 Trạng thái bắt đầu Biểu thị bởi mũi tên chỉ vào nó Trạng thái kết thúc Biểu thị bởi vòng tròn kép Mũi tên từ trạng thái này sang trạng thái khác được gọi là chuyển dịch Thông tin đầu ra hoặc là chấp thuận hoặc là bác bỏ 3 Ứng dụng của FSM Tạo ra các chuỗi tương ứng với mô hình của FSM Nhận diện các chuỗi có thỏa mãn mô hình FSM hay không Ví dụ nhận diện các chuỗi sau - 11010101 Chấp thuận bác bỏ - 100 Chấp thuận bác bỏ - 110000 Chấp thuận bác bỏ - 0100 Chấp thuận bác bỏ - 101000 Chấp thuận bác bỏ Làm thế nào để biểu diễn các chuỗi chấp thuận bằng 1 ngôn ngữ 4 Định nghĩa hình thức Định nghĩa hình thức Ôtômat hữu hạn bộ 5 hay 5 chiều M Q Σ δ q0 F Trong đó - Q Tập trạng thái hữu hạn - Σ Bộ chữ tập hữu hạn các ký tự - δ Hàm dịch chuyển δ Q x Σ Q - q0 Trạng thái bắt đầu q0 Q - F Là tập các trạng thái kết thúc F Q 5 Ví dụ Ôtômat hữu hạn 1 start a b 1 0 0 0 0 1 c d 1 δ Q a b c d Σ Σ 0 1 0 1 Trạng thái q0 a a c b b d a F d c a d d b c 6 Ngôn ngữ của máy M Nếu A là tập tất cả các xâu mà máy M chấp nhận A là ngôn ngữ của máy M L M A Máy M đoán nhận recognizes A Máy M chấp thuận accepts A Do một máy có thể chấp thuận vài xâu nhưng nó luôn đoán nhận chỉ một ngôn ngữ Nếu máy không chấp thuận một xâu nào thì nó vẫn đoán nhận một ngôn ngữ Ngôn ngữ rỗng - Ø 7 Thiết kế Ôtômat hữu hạn Thiết kế Ôtômat hữu hạn Cho bộ chữ Σ 0 1 . Làm thế nào để đoán nhận tất cả các chuỗi không chứa chuỗi 0011
