Đang chuẩn bị liên kết để tải về 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 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. . | 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 Chương 3: Đị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 Bộ điều khiển INPUT OUTPUT BỘ NHỚ Phân loại automata Automata đơ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ị) Phân loại FA FA (Finite Automata) DFA Deterministic Finite Automata NFA Nondeterministic Finite Automata Biểu thức chính quy Start 1 1 0 0 0 0 1 1 a b c d q1 q0 q3 q2 Ví dụ: Input Bộ điều khiển 1 0 1 0 0 1 1 0 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 ) δ : 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ái kết thúc. M=(Q, Σ, δ, q0, F) Trạng thái bắt đầu Trạng thái kết thúc x Phép chuyển trên nhãn x Automata hữu hạn đơn định (DFA) Mở rộng hàm chuyển trạng thái δ(q, ) = q δ(q, wa) = δ( δ(q,w), a) với w, a Ngôn ngữ được chấp nhận: L(M) = { x | δ( q0, x ) F } Ngôn ngữ chính quy Ví dụ: chuỗi nhập w=110101 δ(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 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"); Automata hữu hạn không đơn định (NFA) Nhận xét: Ứng với một | 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 Chương 3: Đị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 Bộ điều khiển INPUT OUTPUT BỘ NHỚ Phân loại automata Automata đơ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ị) Phân loại FA FA (Finite Automata) DFA Deterministic Finite Automata NFA Nondeterministic Finite Automata Biểu thức chính quy Start 1 1 0 0 0 0 1 1 a b c d q1 q0 q3 q2 Ví dụ: Input Bộ điều khiển 1 0 1 0 0 1 1 0 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 ) δ : hàm