- BÀI 3: ÔTÔMAT HỮU HẠN KHÔNG ĐƠN ĐỊNH. - Toán tử chính quy với NFA. - 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. - 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. - Ôtômat hữu hạn đơn định. - Ôtômat hữu hạn không đơn định. - Cạnh epsilon: Có thể đi đến trạng thái sau mà không cần phải đọc thông tin gì cả. - Ví dụ. - Cho NFA đoán nhận tất cả các chuỗi mà chứa chuỗi con 011110 sau:. - Đoán nhận chuỗi Chấp thuận/Bác bỏ?. - 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. - Hãy đoán nhận chuỗi: 010110. - 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. - 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. - Ôtômat hữu hạn không đơn định ≡ bộ 5 (hay 5 chiều) M = (Q, Σ ε , δ, q 0 , F). - Q: Tập trạng thái (hữu hạn. - q 0 : Trạng thái bắt đầu (q 0 ∈ Q). - F: Là tập các trạng thái kết thúc (F ⊆ Q). - Hai máy là tương đương nếu chúng đoán nhận cùng 1 ngôn ngữ Chứng minh (Bằng việc xây dựng). - (Q’,Σ’,δ’,q ’ 0 ,F’) để đoán nhận cùng ngôn ngữ với NFA trên. - R chứa tất cả các trạng thái chấp thuận } Q = {A,B,C. - Ví dụ:. - Chỉnh sửa lại trạng thái bắt đầu của DFA q ’ 0 = E({q 0. - Toán tử chính quy (Nhắc lại). - Giả sử A, B là các ngôn ngữ. - Ta có các toán tử chính quy sau:. - Lớp các ngôn ngữ chính quy là đóng đối với toán tử hợp. - Nếu A 1 và A 2 là ngôn ngữ chính quy thì A 1 ∪ A 2 cũng là ngôn ngữ chính quy. - Chứng minh ĐL 1 (chi tiết). - NFA N 1 = (Q 1 ,Σ,δ 1 ,q 1 ,F 1 ) đoán nhận A 1. - NFA N 2 = (Q 2 ,Σ,δ 2 ,q 2 ,F 2 ) đoán nhận A 2. - Xây dựng NFA N = (Q,Σ,δ,q 0 ,F) đoán nhận A 1 ∪ A 2. - q 0 = Một trạng thái mới. - {q 1 , q 2 } nếu q = q 0 và a = ε. - nếu q = q 0 và a 6= ε. - Lớp các ngôn ngữ chính quy là đóng đối với toán tử ghép tiếp. - Nếu A 1 và A 2 là ngôn ngữ chính quy thì A 1 ◦ A 2 cũng là ngôn ngữ chính quy. - {q 2 } nếu q = F 1 và a = ε δ 1 (q, a) nếu q = q 0 và a 6= ε. - Lớp các ngôn ngữ chính quy là đóng đối với toán tử sao. - Nếu A 1 là ngôn ngữ chính quy thì A 1 * cũng là ngôn ngữ chính quy. - q 0 = Một trạng thái mới - F = {q 0. - δ 1 (q, a) nếu q ∈ Q 1 và q 6∈ F 1. - δ 1 (q, a) nếu q ∈ F 1 và a 6= ε δ 1 (q, a. - {q 1 } nếu q ∈ F 1 và a = ε {q 1 } nếu q = q 0 và a = ε
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt