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