Bài giảng Tin học lí thuyết: Chương 3 - Võ Huỳ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

67
lượt xem 2
download

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

Bài giảng "Tin học lí thuyết - 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 & 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 học lí thuyết: Chương 3 - Võ Huỳ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