Bài giảng Tin học: Chương 3 - Võ Huỳnh Trâm

Chia sẻ: Thanh Hoa | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

76
lượt xem 2
download

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

Bài giảng "Tin học - Chương 3: Automata hữu hạn và Biểu thức chính quy" cung cấp cho người học các kiến thức: Khái niệm DFA và NFA, sự tương đương giữa DFA và 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 nội dung chi tiết.

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: Chương 3 - Võ Huỳnh Trâm

c 0 1 1 0 0 1 0 1 I t n p u 1 Start q q 1 1 0 0 B i k h i 0 ñ u n a b • Khái niệm DFA & NFA 0 Trạng thái bắt ñầu 0 1 Trạng thái kết thúc • Sự tương ñương giữa DFA & NFA q q 2 3 1 d x Phép chuyển trên nhãn x • Biểu thức chính quy : tập hữu hạn các trạng thái (p, q…) • Các tính chất của tập chính quy : bộ chữ cái nhập (a, b … ; w, x, y …) M=(Q, Σ, δ, q0, F) : hàm chuyển, ánh xạ: Q x Σ → Q ∈ Q : trạng thái bắt ñầu. 0 1 F ⊆ Q : tập các trạng thái kết thúc. 3 ε ∀ eterministic D inite utomata F A ∈ 0 ( inite utomata) F A Ngôn ngữ chuỗi nhập w=110101 chính quy ondeterministic • δ(q0, 1) = q1 N inite utomata • δ(q0, 11) = δ(q1, 1) = q0 F A • δ(q0, 110) = δ(q1, 10) = δ(q0, 0) = q2 • δ(q0, 1101) = δ(q1, 101) = δ(q0, 01) = δ(q2, 1) = q3 • δ(q0, 11010) = … = δ(q3, 0) = q1 2 • δ(q0, 110101) = … = δ(q1, 1) = q0 ∈ F 4 Printed with FinePrint - purchase at www.fineprint.com
• kiểm tra một chuỗi nhập có thuộc ngôn ngữ : tập hữu hạn các trạng thái. ñược chấp nhận bởi automata . : bộ chữ cái nhập. M=(Q, Σ, δ, q0, F) : hàm chuyển ánh xạ Q x Σ → Q • chuỗi nhập • câu trả lời ‘ ’ hoặc ‘ ’ ∈ Q : trạng thái bắt ñầu. 0 • F ⊆ Q : tập các trạng thái kết thúc. : khái niệm là tập hợp tất cả các trạng thái p q := q0 ; sao cho có phép chuyển từ trạng thái q trên nhãn a. c := nextchar ; à ý i i { l k h h ñ ñ t t h } c u n p ư c c p e o While c $ do begin q := δ(q, c); • ε c := nextchar ; • có một trạng thái r trong mà p∈ end If (q in F) then write("YES") else write("NO"); • ∪ ∈P với ∀ ⊆ q 5 7 • cho automata M (hình vẽ) và xét chuỗi nhập 1 1 0 0 • 0 1 2 3 4 0 2 4 Start 0 0 q q q 0 3 4 Input • δ(q0, 0) = {q0,q3} δ 1 Trạng thái 0 1 • δ(q0, 01) = δ( δ(q0, 0), 1) 0 1 0 0 1 q0 q0 q0 q0 q0 q0 q q0 {q0,q3} {q0,q1} 1 1 = δ({q0, q3},1) = δ(q0, 1) q1 Ø {q2} 0 1 0 0 1 q3 q1 q3 q3 q1 ∪ δ(q3, 1) = {q0, q1} q2 {q2} {q2} • δ(q0, 010) = {q0, q3} q 0 2 0 q3 {q4} Ø 1 q4 q4 1 q4 {q4} {q4} • δ(q0, 0100) = {q0, q3, q4} • δ(q0, 01001) = {q0, q1, q4} • Ứng với một trạng thái và một ký tự nhập, có thể có Do ∈ nên ∈ 4 không, một hoặc nhiều phép chuyển trạng thái. 6 8 • DFA là một trường hợp ñặc biệt của NFA Printed with FinePrint - purchase at www.fineprint.com
ε ε Nếu là tập ñược chấp nhận bởi một thì tồn NFA chấp nhận chuỗi 0+1+2+ tại một chấp nhận . 0 1 2 Start 0 1 2 q q q q Giả sử chấp nhận L 2 0 1 3 0 Ta xây dựng chấp nhận L xây dựng NFA chấp nhận chuỗi 0*1*2* 0 Một phần tử trong ñược ký hiệu là [q0, q1, Q • 0 1 2 …, qi] với q0, q1, …, qi ∈ Start ε ε • q q q 0 1 2 0 0 • là tập hợp các trạng thái của có chứa ít nhất một trạng thái kết thúc trong tập F của M : ε 0 • Hàm chuyển nếu và • δ : hàm chuyển ánh xạ Q x ( ∪ ε ) → 2Q 1 2 i 1 2 j chỉ nếu • Khái niệm là tập hợp các trạng thái p sao cho 1 2 i 1 2 j 9 có phép chuyển nhãn từ q tới p, với a ∈ (Σ ∪ {ε}) 11 ε NFA với hàm chuyển 0 1 0 1 (q0,0) = {q0, q1}, (q0,1) = {q1}, (q1,0) = ∅, (q1,1) = {q0, q1} ε ● ε (q) = { p | có ñường ñi từ q tới p theo nhãn ε } ● ε (P) = ∪ ∈ ε (q) P Ta sẽ xây dựng DFA tương ñương q 0 • = {∅∅ [q0], [q1], [q0, q1]} mở rộng thành • = {[q1], [q0, q1]} • Qx →2 Q • Hàm chuyển • (q, w) = { p | có ñường ñi từ q tới p theo nhãn , trên ∅ ∅ ∅ ñường ñi có thể chứa cạnh nhãn ε } ([q0], 0) = [q0, q1] • δ*(q, ε) = ε-CLOSURE(q) ([q0], 1) = [q1] • δ*(q,a) = ε-CLOSURE(δ(δ*(q, ε),a)) ([q1], 0) = ∅ • δ*(q, wa) = ε-CLOSURE( δ( δ*(q, w), a) ) ([q1], 1) = [q0, q1] Cách khác: δ*(q, wa) = ε-CLOSURE(P) ([q0, q1], 0) = [q0, q1] với P = { p | r ∈ δ*(q, w) và p ∈ δ(r, a) } 10 12 ([q0, q1], 1) = [q0, q1] • δ*(R, w) = ∪ ∈ δ*(q, w) R q Printed with FinePrint - purchase at www.fineprint.com
ε ε 0 1 2 Start ε ε nếu L ñược chấp nhận bởi một NFA có ε-dịch q q q 0 1 2 Xét chuỗi nhập chuyển thì L cũng ñược chấp nhận bởi một NFA không có • δ*(q0, ε) = ε-CLOSURE(q0) = {q0, q1, q2} ε-dịch chuyển. • δ*(q0, ) = ε-CLOSURE(δ(δ*(q0, ε), 0)) ε M(Q, Σ, δ, q0, F) chấp nhận L = ε-CLOSURE(δ({q0, q1, q2}, 0)) = ε-CLOSURE(δ(q0, 0) ∪ Ta xây dựng: M’={Q, Σ, , q0, } δ(q1, 0) ∪ δ(q2, 0) ) = ε-CLOSURE( {q0} ∪ ∅ ∪ ∅ ) Với: = ε-CLOSURE({q0}) = {q0, q1, q2} • ∪ nếu ε-CLOSURE(q0) chứa một trạng thái thuộc F. 0 • δ*(q0, ) = ε-CLOSURE(δ(δ*(q0, 0), 1)) Ngược lại, = ε-CLOSURE(δ({q0, q1, q2}, 1)) = ε-CLOSURE({q1}) • (q, a) = (q, a) = {q1,q2} • δ*(q0, ) = ε-CLOSURE(δ(δ*(q0, 01), 2)) = ε-CLOSURE(δ({q1, q2}, 2)) = ε-CLOSURE({q2}) = {q2} 13 15 • Do q2 ∈ F nên w ∈ L(M) ε ε 0 1 2 mô phỏng hoạt ñộng của NFAε Start ε ε q q q 0 1 2 chuỗi nhập câu trả lời ‘YES’ (x ñược chấp nhận) hoặc ‘NO’ Xây dựng NFA tương ñương M’={Q, Σ, , q0, } • Q = {q0, q1, q2} q := ε (q0) ; • Σ = {0, 1, 2} C L O S U R E • Trạng thái bắt ñầu: q0 c := nextchar ; à ý i i { l k h h ñ ñ t t h } c u n p ư c c p e o While c $ do • = {q0, q2} δ’ Inputs begin • Hàm chuyển Trạng thái 0 1 2 q := ε (δ(q, c)); C L O S U R E 0 1 2 q0 {q0, q1, q2} {q1, q2} {q2} c := nextchar ; Start 0, 1 1, 2 q1 ∅ {q1, q2} {q2} end q q q 0 1 2 If (q in F) then write("YES") else write("NO"); q2 ∅ ∅ {q2} 0, 1, 2 14 16 Printed with FinePrint - purchase at www.fineprint.com
ε ε ● ε-CLOSURE(q0) = {0, 1, 2, 4, 7} → q0’ = [0, 1, 2, 4, 7] = xây dựng DFA tương ñương với NFAεε sau: = (Q={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, Σ={a, b}, δ, 0, F={10}) ● ε-CLOSURE(δ(A, a)) = ε-CLOSURE({3, 8}) = {1, 2, 3, 4, 6, 7, 8} → ε a ● ε-CLOSURE(δ(A, b)) = ε-CLOSURE({5}) = {1, 2, 4, 5, 6, 7} → 2 3 ε ε ε ε Start a b b ● ε-CLOSURE(δ(B, a)) = ε-CLOSURE({3, 8}) → B 0 1 6 7 8 9 1 0 ε 4 b ε ● ε-CLOSURE(δ(B, b)) = ε-CLOSURE({5, 9}) = {1, 2, 4, 5, 6, 5 7, 9} → ε ● ε-CLOSURE(δ(C, a)) = ε-CLOSURE({3, 8}) → B Ta xây dựng = (Q’, Σ, δ’, q0’, F’) tương ñương ● ε-CLOSURE(δ(C, b)) = ε-CLOSURE({5}) = → C • Trạng thái bắt ñầu: q0’ ↔ ε-CLOSURE(q0) ● ε-CLOSURE(δ(D, a)) = ε-CLOSURE({3, 8}) → B • F’ = { | trong ký hiệu của có chứa ít nhất một trạng ● ε-CLOSURE(δ(D, b)) = ε-CLOSURE({5,10}) = {1, 2, 4, 5, thái của F } 6, 7, } → • Xây dựng hàm chuyển δ’ 17 ● ε-CLOSURE(δ(E, a)) = ε-CLOSURE({3, 8}) → B 19 ● ε-CLOSURE(δ(E, b)) = ε-CLOSURE({5}) = → C ε • Bảng hàm chuyển T := ε (q0) ; ; C O S h ñ ñ á h d L U R E T c ư a ư c n u K ý h i N h Q u n p h ê à $ á h á i Q ’ , T T t t t D F A b m v o p c c r n ' g c a ; T t h á i r U n g a b C While do C ó 2 h á i , h ñ ñ á h d t t t T D F A m r n ' g c a c ư a ư c n u Begin A B C b a b B B D á h d { xét trạng thái T} ð T Start n u ; a b 6 A B D E For 5 i i k ý h i 9 h $ do V m u n p a C B C b begin a ε δ D B E a l ( ( ) ) U T : = c o s u r e a a , If then k h ô ó $ h á i Q ’ , E B C U t t t t D F A n g c r o n g p r n ' g c a begin h ê à $ á h á i Q ’ , T U t t t D F A m v o p c c r n ' g c a ; • Ký hiệu bắt ñầu: q0’ = A (↔ ε-CLOSURE(q0) ) h á i h ñ ñ á h d T t U r n ' g c ư a ư c n u ; δ {δ[T, a] là phần tử của bảng chuyển DFA} [ ] • Tập trạng thái kết thúc: F’ = {E} (vì trong E có chứa trạng T U a : = ; , end; end; thái 10 ∈ ) End; 18 20 Printed with FinePrint - purchase at www.fineprint.com
• : là biểu thức chính quy biểu diễn tập {00} • r+∅=∅+r=r • rε = εr = r • : tập hợp tất cả các chuỗi số 0 và số 1, kể cả • r+r=r • r∅ = ∅r = ∅ chuỗi rỗng = {ε, 0, 1, 00, 01, 10, 11, 010, 011, 0010 • r+s=s+r • (r + s) t = rt + st ... } • (r + s) + t = r + (s + t) = r + s + t • r (s + t) = rs + rt • * : 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, ... } • : tập hợp tất cả các chuỗi 0,1 có ít nhất • ε* = ε • (r* + s*)* = (r*s*)* = (r + s)* • ∅* = ∅ • (rs)*r = r(sr)* hai số 0 liên tiếp = {00, 000, 100, 0000, 0001, 1000, • r*r* = r* • (r*s)* r* = (r + s)* 1001, 011001, ... } • (r*)* = r* • ε : tất cả các chuỗi không có hai số 0 liên • r* = ε + r + r2 + … + rk + … tiếp = {ε, 0, 01, 010, 1, 10, 01010, 0111, ... } • r* = ε + r+ • (ε + )+ = (ε + )* = r* r r • * * * : {ε, 0, 1, 2, 01, 02, 12, 012, 0012, 0112, ... } • r*r = r r* = r+ • : tất cả các chuỗi trong tập 0*1*2* với ít nhất 21 23 một ký hiệu 0, 1 và 2 ↔ viết gọn thành + + + ε cho Σ là một bộ chữ cái. BTCQ trên Σ là các tập nếu r là BTCQ thì tồn tại một NFA với ε-dịch hợp mà chúng mô tả ñược ñịnh nghĩa ñệ quy như sau: chuyển chấp nhận L(r) ● ∅ là BTCQ ký hiệu cho tập rỗng quy nạp theo ● ε là BTCQ ký hiệu cho tập {ε} • Xét không có phép toán nào ● ∀a ∈ Σ, là BTCQ ký hiệu cho tập {a} ● Nếu và là các BTCQ ký hiệu cho các tập hợp R và Start q0 Start q0 qf Start q0 a qf S thì , và là các BTCQ ký hiệu cho các r= ε r=∅ r=a tập hợp R ∪ S, RS và R* tương ứng Các NFAε cho các kết hợp ñơn • Xét có i phép toán: , hoặc 1 1 2 1 2 Xây dựng NFAεε = (Q1, Σ1, δ1, q1, {f1}) và = (Q2, 1 2 Σ2, δ2, q2, {f2}) sao cho L(M1) = L(r1) và L(M2) = L(r2) • Biểu thức có thể viết là Xây dựng NFAεε như sau: 22 24 Printed with FinePrint - purchase at www.fineprint.com
ε ε q1 M1 f1 ε Nếu L ñược chấp nhận bởi một DFA, thì L ñược Start • + ký hiệu bởi một BTCQ r = r r q0 f0 1 2 ε M2 ε q2 f2 L M • ñược chấp nhận bởi DFA ({q1, q2,..., qn}, Σ, δ, q1, F) R • ðặt = {x | δ(qi, x) = qj và nếu δ(qi, y) = ql (y ⊂ x) thì l ≤ k} k i j R (hay là tập hợp tất cả các chuỗi làm cho automata ñi từ k i j Start ε • q1 M1 f1 q2 M2 f2 trạng thái i ñến trạng thái j mà không ñi ngang qua trạng r = r r 1 2 thái nào lớn hơn k) • ðịnh nghĩa ñệ quy của Rkij : = Rk-1ik(Rk-1kk)*Rk-1kj ∪ Rk-1ij k ε i j Start ε ε {a | δ(qi, a) = qj}, nếu i ≠ j * • M1 r = r q0 q1 f1 f0 1 0 i j ε {a | δ(qi, a) = qj} ∪ {ε}, nếu i = j 25 27 ε xây dựng NFAε chấp nhận BTCQ • r có dạng: r = r1 + r2 với r1 = 01* và r2 = 1 • Quy nạp theo k : • r1 có dạng r1 = r3r4 với r3 = 0 và r4 = 1* k = 0: R0ij là tập hữu hạn các chuỗi 1 ký hiệu hoặc ε • r4 có dạng r4 = r5* với r5 = 1 ε Giả sử ta có ñịnh lý ñúng với k-1, tức là tồn tại ε 1 ε Start q1 1 q2 Start q7 q5 q6 q8 BTCQ rk-1lm sao cho L(rk-1lm) = Rk-1lm Vậy ñối với rkij ta có thể chọn BTCQ r 2 * 1 * r = r = ε 4 ε 5 Start q3 0 q4 (rk-1ik)(rk-1kk)*(rk-1kj) + rk-1ij 0 ε ε 1 ε Ta có nhận xét: r Start q3 q4 q7 q5 q6 q8 3 Start 1 ε L(M) = ∪qj ∈F Rn1j 0 1 * q5 q6 r = r r = 1 3 4 Vậy L có thể ñược ký hiệu bằng BTCQ r 1 5 q1 q2 ε ε r = rn1j1 + rn1j2 + … + rn1jp 0 1 * 1 + + r = r r = 1 2 Start q9 ε q10 với F = {qj1, qj2, …, qjp} ε ε q3 0 q ε q7 ε q5 1 q ε q8 4 6 26 28 ε Printed with FinePrint - purchase at www.fineprint.com
viết BTCQ cho DFA 1 ð h l ý 1 n DFA NFA Start 0 1 q1 q2 q3 0 0, 1 ð h l ý ð h l ý 4 2 n n Ta cần viết biểu thức: RE NFAε 3 3 ð h l ý 3 1 2 1 3 n Ta có: • r312 = r213(r233)*r232 + r212 • r313 = r213(r233)*r233 + r213 29 31 k 0 k 1 k 2 = = = k ε ε (00)* r 1 1 k 0 0 0(00)* r 1 2 k 1 1 0*1 r 1 3 k 0 0 0(00)* r 2 1 k ε ε + 00 (00)* r 2 2 k 1 1 + 01 0*1 r 2 3 k ∅ ∅ (0 + 1)(00)*0 r 3 1 k 0+1 0+1 (0 + 1)(00)* r 3 2 k ε ε ε + (0 + 1)0*1 r 3 3 Thay vào và rút gọn, ta có: r= ε 30 Printed with FinePrint - purchase at www.fineprint.com