›
›

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

ppt 34 trang ngocly 2770
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Tin học lý thuyết - Chương 3: Automata hữu hạn & 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:

  • pptbai_giang_toan_giai_tich_chuong_3_automata_huu_han_bieu_thuc.ppt

Nội dung text: Bài giảng Tin học lý thuyết - Chương 3: Automata hữu hạn & 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 Nondeterministi c 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  r = r + r Start • 1 2 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({q1, q2, , qn}, Σ, δ, q1, F) k • Đặt R ij = {x | δ(qi, x) = qj và nếu δ(qi, y) = ql (y  x) thì l ≤ k} k (hay R ij là tập hợp tất cả các chuỗi làm cho automata đi từ trạng thái 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