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

Chia sẻ: BDBC BDBC | Ngày: | Loại File: PPT | Số trang:34

Thêm vào BST

Báo xấu

100
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

Chươ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ều khiển OUTPUT BỘ NHỚ 2
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ị) 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, a Ngô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"); 7
Automata 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 q4 Nhậ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=(Q, Σ, δ, q0, F) δ : hàm chuyển ánh xạ Q x Σ → 2Q q0 Q : trạng thái bắt đầu. F Q : tập các trạng thái kết thúc. Chú ý: khái niệm δ(q, a) là tập hợp tất cả các trạng thái p sao cho có phép chuyển từ trạng thái q trên nhãn a. Hàm chuyển trạng thái mở rộng: • δ(q, ) = {q} • δ(q, wa) = { p | có một trạng thái r trong δ(q, w) mà p δ(r, a) } = δ( δ(q,w), a) • δ(P, w) = q P δ(q, w) với P Q 9
Ví dụ về NFA Ví dụ: xét chuỗi nhập w=01001 và NFA đã cho ở trên • M( {q0, q1, q2, q3, q4}, {0, 1}, δ, q0, {q2, q4} ) δ Input • δ(q0, 0) = {q0,q3} Trạng thái 0 1 • δ(q0, 01) = δ( δ(q0, 0), 1) q0 {q0,q3} {q0,q1} = δ({q0, q3},1) = δ(q0, 1) q1 Ø {q2} δ(q3, 1) = {q0, q1} q2 {q2} {q2} q3 {q4} Ø • δ(q0, 010) = {q0, q3} q4 {q4} {q4} • δ(q0, 0100) = {q0, q3, q4} • δ(q0, 01001) = {q0, q1, q4} Do q4 F nên w=01001 L(M) 10
Sự tương đương giữa DFA & NFA Định lý 1: Nếu L là tập được chấp nhận bởi một NFA thì tồn tại một DFA chấp nhận L. Giả sử NFA M={Q, Σ, δ, q0, F} chấp nhận L Ta xây dựng DFA M’={Q’, Σ, δ’, q0’, F’} chấp nhận L • Q’ = 2Q . Một phần tử trong Q’ được ký hiệu là [q0, q1, …, qi] với q0, q1, …, qi Q • q0’ = [q0] • F’ là tập hợp các trạng thái của Q’ có chứa ít nhất một trạng thái kết thúc trong tập F của M • Hàm chuyển δ’([q1, q2,..., qi], a) = [p1, p2,..., pj] nếu và chỉ nếu δ({q1, q2,..., qi }, a) = {p1, p2,..., pj} 11
Ví dụ về sự tương đương giữa DFA & NFA Ví dụ: NFA M ({q0, q1}, {0, 1}, δ, q0, {q1}) với hàm chuyển δ(q0,0) = {q0, q1}, δ(q0,1) = {q1}, δ(q1,0) = , δ(q1,1) = {q0, q1} Ta sẽ xây dựng DFA tương đương M’ (Q’, {0, 1}, δ’, [q0], F’) • Q’ = { , [q0], [q1], [q0, q1]} • F’ = {[q1], [q0, q1]} • Hàm chuyển δ’  δ’( , 0) = δ’( , 1) =  δ’([q0], 0) = [q0, q1]  δ’([q0], 1) = [q1]  δ’([q1], 0) =  δ’([q1], 1) = [q0, q1]  δ’([q0, q1], 0) = [q0, q1]  δ’([q0, q1], 1) = [q0, q1] 12
NFA với - dịch chuyển (NFA ) Ví dụ: xây dựng NFA chấp nhận chuỗi 0*1*2* 0 1 2 Start 0, 1 1, 2 q0 q1 q2 0, 1, 2 0 1 2 Start q0 q1 q2 Định nghĩa: NFA M(Q, Σ, δ, q0, F) • δ : hàm chuyển ánh xạ Q x (Σ { }) → 2Q • Khái niệm δ(q, a) là tập hợp các trạng thái p sao cho có phép chuyển nhãn a từ q tới p, với a (Σ { }) 13
Mở rộng hàm chuyển trạng thái cho NFA Định nghĩa -CLOSURE: ● -CLOSURE(q) = { p | có đường đi từ q tới p theo nhãn } ● -CLOSURE(P) = q P -CLOSURE(q) Hàm chuyển trạng thái mở rộng: mở rộng δ thành δ* • δ* : Q x Σ* → 2Q • δ*(q, w) = { p | có đường đi từ q tới p theo nhãn w, trên đường đi có thể chứa cạnh nhãn } Ta có: • δ*(q, ) = -CLOSURE(q) • δ*(q,a) = -CLOSURE(δ(δ*(q, ),a)) • δ*(q, wa) = -CLOSURE( δ( δ*(q, w), a) ) Cách khác: δ*(q, wa) = -CLOSURE(P) với P = { p | r δ*(q, w) và p δ(r, a) } • δ*(R, w) = q R δ*(q, w) 14
Mở rộng hàm chuyển trạng thái cho NFA 0 1 2 Ví dụ: Start q0 q1 q2 Xét chuỗi nhập w = 012 • δ*(q0, ) = -CLOSURE(q0) = {q0, q1, q2} • δ*(q0, 0) = -CLOSURE(δ(δ*(q0, ), 0)) = -CLOSURE(δ({q0, q1, q2}, 0)) = -CLOSURE(δ(q0, 0) δ(q1, 0) δ(q2, 0) ) = -CLOSURE( {q0} ) = -CLOSURE({q0}) = {q0, q1, q2} • δ*(q0, 01) = -CLOSURE(δ(δ*(q0, 0), 1)) = -CLOSURE(δ({q0, q1, q2}, 1)) = -CLOSURE({q1}) = {q1,q2} • δ*(q0, 012) = -CLOSURE(δ(δ*(q0, 01), 2)) 15 = -CLOSURE(δ({q1, q2}, 2)) = -CLOSURE({q 2}) = {q2}
Giải thuật hình thức cho NFA Mục đích: mô phỏng hoạt động của NFA Input: chuỗi nhập x$ Output: câu trả lời ‘YES’ (x được chấp nhận) hoặc ‘NO’ Giải thuật: q := -CLOSURE (q0) ; c := nextchar ; {c là ký hiệu nhập được đọc tiếp theo} While c $ do begin q := -CLOSURE (δ(q, c)); c := nextchar ; end If (q in F) then write("YES") else write("NO"); 16
Sự tương đương giữa NFA và NFA Định lý 2: nếu L được chấp nhận bởi một NFA có -dịch chuyển thì L cũng được chấp nhận bởi một NFA không có -dịch chuyển. Giả sử: NFA M(Q, Σ, δ, q0, F) chấp nhận L Ta xây dựng: NFA M’={Q, Σ, δ’, q0, F’} Với: • F’ = F q0 nếu -CLOSURE(q0) chứa một trạng thái thuộc F. Ngược lại, F’ = F • δ’(q, a) = δ*(q, a) 17
Sự tương đương giữa NFA và NFA 0 1 2 Start Ví dụ: q0 q1 q2 Xây dựng NFA tương đương M’={Q, Σ, δ’, q0, F’} • Q = {q0, q1, q2} • Σ = {0, 1, 2} • Trạng thái bắt đầu: q0 δ’ Inputs • F’ = {q0, q2} • Hàm chuyển δ’ Trạng 0 1 2 0 1 2 thái q {q0, q1, q2} {q1, q2} {q2} 0 Start 0, 1 1, 2 q0 q1 q2 q1 {q1, q2} {q2} q2 {q2} 0, 1, 2 18
Xây dựng DFA từ NFA( ) Ví dụ: xây dựng DFA tương đương với NFA sau: M = (Q={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, Σ={a, b}, δ, 0, F={10}) a 2 3 Start a b b 0 1 6 7 8 9 10 b 4 5 Ta xây dựng DFA M’= (Q’, Σ, δ’, q0’, F’) tương đương M • Trạng thái bắt đầu: q0’ ↔ -CLOSURE(q0) • F’ = { p | trong ký hiệu của p có chứa ít nhất một trạng thái của F } • Xây dựng hàm chuyển δ’ 19
Giải thuật xây dựng hàm chuyển δ’ Giải thuật: T := -CLOSURE (q0) ; T chưa được đánh dấu ; Thêm T vào tập các trạng thái Q’ của DFA ; While Có một trạng thái T của DFA chưa được đánh dấu do Begin Đánh dấu T; { xét trạng thái T} For Với mỗi ký hiệu nhập a do begin U:= -closure( (T, a)) If U không có trong tập trạng thái Q’ của DFA then begin Thêm U vào tập các trạng thái Q’ của DFA ; Trạng thái U chưa được đánh dấu; [T, a] := U;{ [T, a] là phần tử của bảng chuyển DFA} end; end; End; 20