›
›

Bài giảng Automata hữu hạn và Biểu thức chính quy

pdf 34 trang huongle 8700
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Automata hữu hạn và Biểu thức chính quy", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_automata_huu_han_va_bieu_thuc_chinh_quy.pdf

Nội dung text: Bài giảng Automata hữu hạn và Biểu thức chính quy

  1. 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
  2. Đị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
  3. 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
  4. Phân loại FA DFA Deterministic Finite Automata FA (Finite Automata) NFA Nondeterministic Finite Automata Biểu thức chính quy 4
  5. Automata hữu hạn đơn định (DFA) Ví dụ: c Input 1 0 1 1 0 0 1 0 1 Start q0 1 q1 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. 5
  6. 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
  7. 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
  8. 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 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. • DFA là một trường hợp đặc biệt của NFA 8
  9. Định nghĩa NFA Q : tập hữu hạn các trạng thái. Σ : bộ chữ cái nhập. Q M=(Q, Σ, δ, q0, F) δ : hàm chuyển ánh xạ Q x Σ → 2 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
  10. 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} q {q } {q } 2 2 2 • δ(q0, 010) = {q0, q3} q {q } Ø 3 4 • δ(q0, 0100) = {q0, q3, q4} q4 {q4} {q4} • δ(q0, 01001) = {q0, q1, q4} Do q4 F nên w=01001 L(M) 10
  11. 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} 11
  12. 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
  13. 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
  14. 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
  15. 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)) = -CLOSURE(δ({q1, q2}, 2)) = -CLOSURE({q2}) = {q2} • Do q2 F nên w L(M) 15
  16. 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
  17. 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
  18. 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} δ’ Inputs • Hàm chuyển δ’ Trạng thái 0 1 2 0 1 2 q0 {q0, q1, q2} {q1, q2} {q2} Start 0, 1 1, 2 q0 q1 q2 q1  {q1, q2} {q2} q   {q } 0, 1, 2 2 2 18
  19. 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
  20. 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
  21. 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 21 ● -CLOSURE(δ(E, b)) = -CLOSURE({5}) = → C
  22. Xây dựng DFA từ NFA() • Bảng hàm chuyển Ký hiệu nhập Trạng thái b a b C A B C b a b B B D Start a b A B D E C B C b a D B E a 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) 22
  23. Biểu thức chính quy (RE) Vài ví dụ: • 00 : là biểu thức chính quy biểu diễn tập {00} • (0+1)* : tập hợp tất cả các chuỗi số 0 và số 1, kể cả chuỗi rỗng = {, 0, 1, 00, 01, 10, 11, 010, 011, 0010 } • (0+1)*011 : ký hiệu cho tất cả các chuỗi 0, 1 tận cùng bởi 011 = {011, 0011, 1011, 00011, 11011, } 23
  24. Biểu thức chính quy (RE) • (0+1)*00(0+1)* : tập hợp tất cả các chuỗi 0,1 có ít nhất hai số 0 liên tiếp = {00, 000, 100, 0000, 0001, 1000, 1001, 011001, } • (0+ )(1+10)* : tất cả các chuỗi không có hai số 0 liên tiếp = {, 0, 01, 010, 1, 10, 01010, 0111, } • 0*1*2* : {, 0, 1, 2, 01, 02, 12, 012, 0012, 0112, } • 00*11*22* : tất cả các chuỗi trong tập 0*1*2* với ít nhất một ký hiệu 0, 1 và 2 ↔ viết gọn thành 0+1+2+ 24
  25. Biểu thức chính quy (RE) Định nghĩa: cho Σ là một bộ chữ cái. BTCQ trên Σ là các tập hợp mà chúng mô tả được định nghĩa đệ quy như sau: ●  là BTCQ ký hiệu cho tập rỗng ●  là BTCQ ký hiệu cho tập {} ● a Σ, a là BTCQ ký hiệu cho tập {a} ● Nếu r và s là các BTCQ ký hiệu cho các tập hợp R và S thì (r + s), (rs) và ( r*) là các BTCQ ký hiệu cho các tập hợp R  S, RS và R* tương ứng Thứ tự ưu tiên: Phép bao đóng > Phép nối kết > Phép hợp Ví dụ: • Biểu thức ((0(1*)) + 1) có thể viết là 01*+1 25
  26. Tính chất đại số của BTCQ Phép hợp: Phép nối kết: • r +  =  + r = r • r = r = r • r + r = r • r = r =  • r + s = s + r • (r + s) t = rt + st • (r + s) + t = r + (s + t) = r + s + t • r (s + t) = rs + rt Phép bao đóng: Tổng hợp: • * =  • (r* + s*)* = (r*s*)* = (r + s)* • * =  • (rs)*r = r(sr)* • r*r* = r* • (r*s)* r* = (r + s)* • (r*)* = r* • r* =  + r + r2 + + rk + • r* =  + r+ • ( + r)+ = ( + r)* = r* • r*r = r r* = r+ 26
  27. Sự tương đương giữa NFA và BTCQ Định lý 3: nếu r là BTCQ thì tồn tại một NFA với -dịch chuyển chấp nhận L(r) Chứng minh: quy nạp theo số phép toán • Xét r không có phép toán nào Start Start Start a q0 q0 qf q0 qf r =  r =  r = a Các NFA cho các kết hợp đơn • Xét r có i phép toán: r = r1 + r2, r = r1r2 hoặc r = r1*  Xây dựng NFA M1 = (Q1, Σ1, δ1, q1, {f1}) và M2 = (Q2, Σ2, δ2, q2, {f2}) sao cho L(M1) = L(r1) và L(M2) = L(r2)  Xây dựng NFA M như sau: 27
  28. Sự tương đương giữa NFA và BTCQ M  q1 1 f1  Start • r = r1 + r2 q0 f0  M  q2 2 f2 Start  q M1 f q M2 f • r = r1r2 1 1 2 2  Start  M  • r = r1* q0 q1 1 f1 f0  28
  29. Sự tương đương giữa NFA và BTCQ Ví dụ: xây dựng NFA chấp nhận BTCQ r = 01* + 1 • r có dạng: r = r1 + r2 với r1 = 01* và r2 = 1 • r1 có dạng r1 = r3r4 với r3 = 0 và r4 = 1* • r4 có dạng r4 = r5* với r5 = 1   1  Start 1 Start q q q q q1 q2 7 5 6 8 r2 r4 = r5* = 1*   Start 0 q3 q4 r 0   1  3 Start q3 q4 q7 q5 q6 q8 Start 1  q5 q6 r1 = r3r4 = 01* r5 q 1 q 1 2   r = r1 + r2 = 01* + 1  Start q q9  10 0   1   q3 q4 q7 q5 q6 q8 29 
  30. Sự tương đương giữa DFA và BTCQ Định lý 4: Nếu L được chấp nhận bởi một DFA, thì L được ký hiệu bởi một BTCQ Chứng minh: • L được chấp nhận bởi DFA M({q , q , , q }, Σ, δ, q , F) • Đặt Rk = {x | δ(q , x) = q và nếu 1δ(q2, y) = nq (y  x) 1thì l ≤ k} (hay Rkij là tập hợpi tất cảj các chuỗi làmi chol automata đi từ trạng tháiij i đến trạng thái j mà không đi ngang qua trạng thái nào lớn hơn k) k • Định nghĩa đệ quy của R ij : k k-1 k-1 k-1 k-1 R ij = R ik(R kk)*R kj  R ij {a | δ(q , a) = q }, nếu i ≠ j 0 i j R ij = {a | δ(qi, a) = qj}  {}, nếu i = j 30
  31. Sự tương đương giữa DFA và BTCQ k • Ta sẽ chứng minh (quy nạp theo k) bổ đề sau: với mọi R ij đều tồn tại một k biểu thức chính quy ký hiệu cho R ij . 0  k = 0: R ij là tập hữu hạn các chuỗi 1 ký hiệu hoặc  k-1  Giả sử ta có bổ đề trên đúng với k-1, tức là tồn tại BTCQ r lm sao k-1 k-1 cho L(r lm) = R lm k  Vậy đối với R ij ta có thể chọn BTCQ k k-1 k-1 k-1 k-1 r ij = (r ik)(r kk)*(r kj) + r ij → bổ đề đã được chứng minh ● Ta có nhận xét: n L(M) = qj F R 1j ● Vậy L có thể được ký hiệu bằng BTCQ n n n r = r 1j1 + r 1j2 + + r 1jp với F = {qj1, qj2, , qjp} 31
  32. Sự tương đương giữa DFA và BTCQ Ví dụ: viết BTCQ cho DFA 1 Start 0 1 q1 q2 q3 0 0, 1 Ta cần viết biểu thức: 3 3 r = r 12 + r 13 Ta có: 3 2 2 2 2 • r 12 = r 13(r 33)*r 32 + r 12 3 2 2 2 2 • r 13 = r 13(r 33)*r 33 + r 13 32
  33. Sự tương đương giữa DFA và BTCQ k = 0 k = 1 k = 2 k r 11   (00)* k r 12 0 0 0(00)* k r 13 1 1 0*1 k r 21 0 0 0(00)* k r 22   + 00 (00)* k r 23 1 1 + 01 0*1 k r 31   (0 + 1)(00)*0 k r 32 0 + 1 0 + 1 (0 + 1)(00)* k r 33    + (0 + 1)0*1 Thay vào và rút gọn, ta có: r = 0*1((0 + 1)0*1)* ( + (0 + 1)(00)*) + 0(00)* 33
  34. Mối liên hệ giữa FA và BTCQ Sơ đồ liên hệ: Định lý 1 DFA NFA Định lý 4 Định lý 2 RE NFA Định lý 3 34