Bài giảng Tin học lý thuyết - Chương 3: Automata hữu hạn và biểu thức chính quy

Bài giảng chương 3 trình bày về automata hữu hạn và biểu thức chính quy. Chương này gồm có những nội dung chính sau: Khái niệm DFA & NFA, sự tương đương giữa DFA & NFA, biểu thức chính quy, các tính chất của tập chính quy. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Tin học lý thuyết - Chương 3: Automata hữu hạn và biểu thức chính quyChương 3: Automata hữu hạn & Biểu thức chính quy Nội dung: • Khái niệm DFA & NFA • Sự tương đương giữa DFA & NFA • Biểu thức chính quy • Các tính chất của tập chính quy 1 Định nghĩa ôtômát (automata)Định nghĩa: là máy trừu tượng có cơ cấu và hoạt động đơn giản nhưng có khả năng đoán nhận ngôn ngữ • Con người phải lập trình sẵn cho máy một ‘lộ trình’ để thực hiện INPUT Bộđiềukhiển OUTPUT BỘ NHỚ 2 Phân loại automataAutomata đơn định (Deterministic Automata): • Mỗi bước di chuyển chỉ được xác định duy nhất bởi cấu hình hiện tại (hàm chuyển của automata là đơn trị)Automata không đơn định (Non-deterministic Automata): • Tại mỗi bước di chuyển, nó có vài khả năng để lựa chọn (hàm chuyển của automata là đa trị) 3 Phân loại FA DFA Deterministic Finite Automata FA(Finite Automata) NFA Nondeterministic Finite Automata Biểu thức chính quy 4 Automata hữu hạn đơn định (DFA) Ví dụ: 0 1 1 0 0 1 0 1 c Input 1 Start q0 1 q1 0 0 Bộ điều khiển a b Trạng thái bắt đầu 0 0 1 q2 q3 Trạng thái kết thúc 1 d x Phép chuyển trên nhãn x Q : tập hữu hạn các trạng thái (p, q…) Σ : bộ chữ cái nhập (a, b … ; w, x, y …)M=(Q, Σ, δ, q0, F) δ : hàm chuyển, ánh xạ: Q x Σ → Q q0 Q : trạng thái bắt đầu. F Q : tập các trạng thái5 kết thúc. Mở rộng hàm chuyển trạng thái 1. δ(q, ) = q 2. δ(q, wa) = δ( δ(q,w), a) với w, aNgôn ngữ được chấp nhận: L(M) = { x | δ( q0, x ) F} Ngôn ngữVí dụ: chuỗi nhập w=110101 chính quy • δ(q0, 1) = q1 • δ(q0, 11) = δ(q1, 1) = q0 • δ(q0, 110) = δ(q1, 10) = δ(q0, 0) = q2 • δ(q0, 1101) = δ(q1, 101) = δ(q0, 01) = δ(q2, 1) = q3 • δ(q0, 11010) = … = δ(q3, 0) = q1 • δ(q0, 110101) = … = δ(q1, 1) = q0 F 6 Giải thuật hình thức• Mục đích: kiểm tra một chuỗi nhập x có thuộc ngôn ngữ L(M) được chấp nhận bởi automata M.• Input: chuỗi nhập x$• Output: câu trả lời ‘YES’ hoặc ‘NO’• Giải thuật: q := q0 ; c := nextchar ; {c là ký hiệu nhập được đọc tiếp theo} While c $ do begin q := δ(q, c); c := nextchar ; end If (q in F) then write(YES) else write(NO); 7Automata hữu hạn không đơn định (NFA)• Ví dụ: cho automata M (hình vẽ) và xét chuỗi nhập 01001 1 1 0 0 Start 0 0 q0 q3 q4 1 q1 q0 0 q0 1 q0 0 q0 0 q0 1 q0 1 0 1 0 0 1 q3 q1 q3 q3 q1 q2 0 0 1 1 q4 q4Nhận xét:• Ứng với một trạng thái và một ký tự nhập, có thể có không, một hoặc nhiều phép chuyển trạng thái. 8• DFA là một trường hợp đặc biệt của NFA Định nghĩa NFA Q : tập hữu hạn các trạng thái. Σ : bộ chữ cái nhập.M ...