Bài giảng Lý thuyết tính toán: Bài 3 - 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 không đơn định; khái niệm; sự tương đương giữa NFA và DFA; định nghĩa hình thức; toán tử chính quy với NFA; . 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 3 ÔTÔMAT HỮU HẠN KHÔNG ĐƠN ĐỊNH Phạm Xuân Cường Khoa Công nghệ thông tin cuongpx@ Nội dung bài giảng 1. Khái niệm 2. Sự tương đương giữa NFA và DFA 3. Định nghĩa hình thức 4. Toán tử chính quy với NFA 1 Khái niệm Không đơn định Không đơn định Ở mỗi thời điểm có thể tồn tại vài lựa chọn cho trạng thái tiếp theo 0 1 0 1 1 0 ε 1 start q1 q2 q3 q4 Không đơn định là sự tổng quát hóa của đơn định Mọi Ôtômat hữu hạn đơn định đều là Ôtômat hữu hạn không đơn định Thuật ngữ FSM Finite State Machine DFA Deterministic Finite State Automaton Ôtômat hữu hạn đơn định NFA Nondeterministic Finite State Automaton Ôtômat hữu hạn không đơn định 2 NFA hoạt động như thế nào 3 a 5 a b 2 8 b ε b 4 6 ε a 9 4 7 Cạnh epsilon Có thể đi đến Chọn đường đi như thế nào trạng thái sau mà không cần phải đọc thông tin gì cả 3 Ví dụ Cho NFA đoán nhận tất cả các chuỗi mà chứa chuỗi con 011110 sau 0 1 0 1 0 1 1 1 1 0 start a b c d e f g Đoán nhận chuỗi 0100011110101 Chấp thuận Bác bỏ 4 NFA hoạt động như thế nào NFA chấp nhận 1 xâu khi tồn tại một đường đi nào đó đạt được trạng thái chấp thuận . Chấp thuận Chấp thuận DFA NFA 5 Ví dụ NFA Cho NFA sau 0 1 0 1 1 0 ε 1 start a b c d Hãy đoán nhận chuỗi 010110 6 Sự tương đương giữa NFA và DFA Sự tương đương giữa NFA và DFA Định lý 1 Mọi NFA đều có thể biến đổi thành DFA tương đương Ví dụ Đoán nhận tất cả các chuỗi trên bộ 0 1 mà có chữ số 0 ở vị trí thứ 2 tính từ cuối lên 1 1 0 1 0 0 start a b c 1 0 0 1 start a b c 0 1 0 c NFA DFA 7 Ví dụ Thiết kế NFA đoán nhận tất cả các chuỗi mà nó chứa các chuỗi con 0100 hoặc 0111 0 1 0 1 0 0 0 1 ε start 0 1 ε 0 1 1 1 8 Định nghĩa hình thức Định nghĩa hình thức Ôtômat hữu hạn không đơn định 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 9 Ví dụ NFA 1 start a b 0 1 0 0 0 0 1 1 c d 1 ε δ Q a b c d Σε Σε 0 1 ε 0 1 ε Trạng thái q0 a a c b Ø b
