Tin học lý thuyết - Chương 3: Automata hữu hạn & Biểu thức chính quy

Chia sẻ: Nguyễn NHi | Ngày: | Loại File: PDF | Số trang:31

Thêm vào BST

Báo xấu

109
lượt xem 12
download

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

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ủ đề:

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

Lưu

Nội dung Text: Tin học lý thuyết - Chương 3: Automata hữu hạn & Biểu thức chính quy

Automata hữu hạn & Chương 3: 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
Phân loại FA DFA Deterministic Finite Automata FA (Finite Automata) NFA Nondeterministic Finite Automata Biểu thức chính quy 2
Automata hữu hạn đơn định (DFA) Ví dụ: c 01100101 Input 1 Start q1 q0 1 0 0 Bộ điều khiển a b Trạng thái bắt đầu 0 0 1 Trạng thái kết thúc q2 q3 1 x d 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ái kết thúc. 3
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 • 4
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"); 5
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 0 1 0 0 1 q1 q0 q0 q0 q0 q0 q0 1 0 1 0 0 1 q3 q1 q3 q3 q1 q2 0 0 1 q4 q4 1 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. 6 • 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 7
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} ) • • δ(q0, 0) = {q0,q3} δ Input • δ(q0, 01) = δ( δ(q0, 0), 1) Trạng thái 0 1 = δ({q0, q3},1) = δ(q0, 1) q0 {q0,q3} {q0,q1}  δ(q3, 1) = {q0, q1} q1 Ø {q2} q2 {q2} {q2} • δ(q0, 010) = {q0, q3} q3 {q4} Ø • δ(q0, 0100) = {q0, q3, q4} q4 {q4} {q4} • δ(q0, 01001) = {q0, q1, q4} Do q4  F nên w=01001  L(M) 8
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 Q’ = 2 . 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} 9
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] 10
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 q1 q0 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  (Σ  {}) 11
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 δ* : Q x Σ* → 2 • δ*(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) • 12
Mở rộng hàm chuyển trạng thái cho NFA 0 1 2 Start Ví dụ:   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)) = -CLOSURE(δ({q1, q2}, 2)) = -CLOSURE({q2}) = {q2} • Do q2  F nên w  L(M) 13
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"); 14
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  q nếu -CLOSURE(q0) chứa một trạng thái thuộc F. • Ngược lại,0F’ = F δ’(q, a) = δ*(q, a) • 15
Sự tương đương giữa NFA và NFA 0 1 2 Ví dụ: Start   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 • • F’ = {q0, q2} Hàm chuyển δ’ • δ’ Inputs Trạng thái 0 1 2 0 1 2 q0 {q0, q1, q2} {q1, q2} {q2} Start 0, 1 1, 2 q1 {q1, q2} {q2}  q1 q0 q2 q2 {q2}   0, 1, 2 16
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     a b b Start 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 δ’ • 17
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; 18
Xây dựng DFA từ NFA() -CLOSURE(q0) = {0, 1, 2, 4, 7} → q0’ = [0, 1, 2, 4, 7] = A ● -CLOSURE(δ(A, a)) = -CLOSURE({3, 8}) = {1, 2, 3, 4, 6, ● 7, 8} → B -CLOSURE(δ(A, b)) = -CLOSURE({5}) = {1, 2, 4, 5, 6, 7} ● →C -CLOSURE(δ(B, a)) = -CLOSURE({3, 8}) → B ● -CLOSURE(δ(B, b)) = -CLOSURE({5, 9}) = {1, 2, 4, 5, 6, ● 7, 9} → D -CLOSURE(δ(C, a)) = -CLOSURE({3, 8}) → B ● -CLOSURE(δ(C, b)) = -CLOSURE({5}) = → C ● -CLOSURE(δ(D, a)) = -CLOSURE({3, 8}) → B ● -CLOSURE(δ(D, b)) = -CLOSURE({5,10}) = {1, 2, 4, 5, ● 6, 7, 10} → E -CLOSURE(δ(E, a)) = -CLOSURE({3, 8}) → B ● 19 -CLOSURE(δ(E, b)) = -CLOSURE({5}) = → C ●
Xây dựng DFA từ NFA() • Bảng hàm chuyển Ký hiệu nhập b Trạng thái a b C A B C a b b B B D Start a b A B D E C B C b a a D B E a E B C • Ký hiệu bắt đầu: q0’ = A (↔ -CLOSURE(q0) ) • Tập trạng thái kết thúc: F’ = {E} (vì trong E có chứa trạng thái 10  F) 20