Ôtômát hữu hạn

Trang 47 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Chương 2 Ôtômát hữu hạn 2.1 Accepter hữu hạn đơn định 2.2 Accepter hữu hạn không đơn định 2.3 Sự tương đương giữa accepter hữu hạn đơn định và accepter hữu hạn không đơn định 2.4 Rút gọn số trạng thái của một ôtômát hữu hạn Trang 48 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Accepter hữu hạn đơn định „ Định nghĩa 2.1 Một accepter hữu hạn đơn định (deterministic finite state accepter) hay dfa được định nghĩa bởi bộ năm M = (Q, Σ, δ, q0, F), „ Q là một tập hữu hạn các trạng thái nội (internal states), „ Σ là một tập hữu hạn các ký hiệu được gọi là bảng chữ cái ngõ nhập (input alphabet), „ δ: Q × Σ → Q là hàm chuyển trạng thái (transition function). Để chuyển trạng thái ôtômát dựa vào trạng thái hiện hành q ∈ Q nó đang ở vào và kí hiệu nhập a ∈ Σ nó đang đọc được, nó sẽ chuyển sang trạng thái kế được định nghĩa sẵn trong δ. Trang 49 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Accepter hữu hạn đơn định (tt) „ q0 ∈ Q là trạng thái khởi đầu (initial state), „ F ⊆ Q là một tập các trạng thái kết thúc (final states) (hay còn được gọi là trạng thái chấp nhận). „ Chú ý „ Ôtômát hữu hạn không có bộ nhớ so với mô hình tổng quát. Trang 50 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Hoạt động của một dfa „ Hoạt động của một dfa „ Tại thời điểm khởi đầu, nó được giả thiết ở trong trạng thái khởi đầu q0, với cơ cấu nhập (đầu đọc) của nó đang ở trên kí hiệu đầu tiên bên trái của chuỗi nhập. „ Trong suốt mỗi lần di chuyển, cơ cấu nhập tiến về phía phải một kí hiệu, như vậy mỗi lần di chuyển sẽ lấy một kí hiệu ngõ nhập. „ Khi gặp kí hiệu kết thúc chuỗi, chuỗi là được chấp nhận (accept) nếu ôtômát đang ở vào một trong các trạng thái kết thúc của nó. Ngược lại thì có nghĩa là chuỗi bị từ chối. Trang 51 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Đồ thị chuyển trạng thái „ Để biểu diễn một cách trực quan cho dfa người ta sử dụng đồ thị chuyển trạng thái. Cách biểu diễn như sau. „ Các đỉnh biểu diễn các trạng thái. „ Các cạnh biểu diễn các chuyển trạng thái. „ Các nhãn trên các đỉnh là tên các trạng thái. „ Các nhãn trên các cạnh là giá trị hiện tại của kí hiệu nhập. „ Trạng thái khởi đầu sẽ được nhận biết bằng một mũi tên đi vào không mang nhãn mà không xuất phát từ bất kỳ đỉnh nào „ Các trạng thái kết thúc được vẽ bằng một vòng tròn đôi. Trang 52 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ „ Cho dfa sau M = (Q, Σ, δ, q0, F) Q = {q0, q1, q2}, Σ = {0, 1}, F = {q1}, còn δ được cho bởi δ(q0, 0) = q0, δ(q0, 1) = q1, δ(q1, 0) = q0, δ(q1, 1) = q2, δ(q2, 0) = q2, δ(q2, 1) = q1, „ Đồ thị chuyển trạng thái tương ứng là q0 0 0 1 q1 q2 1 1 0 Trang 53 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Hàm chuyển trạng thái mở rộng „ Hàm chuyển trạng thái mở rộng δ* được định nghĩa một cách đệ qui như sau „ δ*(q, λ) = q, „ δ*(q, wa) = δ(δ*(q, w), a), ∀ q ∈ Q, w ∈ Σ*, a ∈ Σ. „ Ví dụ „ Nếu δ(q0, a) = q1, và δ(q1, b) = q2, „ Thì δ*(q0, ab) = q2 „ Chú ý „ δ không có định nghĩa cho chuyển trạng thái rỗng, tức là không định nghĩa cho δ(q, λ). Trang 54 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ngôn ngữ và dfa „ Định nghĩa 2.2 „ Ngôn ngữ được chấp nhận bởi dfa M = (Q, Σ, δ, q0, F) là tập tất cả các chuỗi trên Σ được chấp nhận bởi M. „ L(M) = {w ∈ Σ*: δ*(q0, w) ∈ F}. „ Nhận xét: „ = {w ∈ Σ* : δ*(q0, w) ∉ F}.( )ML Trang 55 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ „ Ví dụ „ Xét dfa M sau „ Dfa trên chấp nhận ngôn ngữ sau L(M) = {anb : n ≥ 0} „ Trạng thái bẫy (trap state): là trạng thái mà sau khi ôtômát đi vào sẽ không bao giờ thoát ra được. „ Trạng thái bẫy có thể là trạng thái kết thúc hoặc không. „ Định nghĩa trên cũng có thể mở rộng ra cho nhóm các trạng thái bẫy kết thúc hay không kết thúc. a, b a, ba bq0 q1 q2 Trang 56 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Định lý, bảng truyền „ Định lý 2.1 „ Cho M = (Q, Σ, δ, q0, F) là một accepter hữu hạn đơn định, và GM là đồ thị chuyển trạng thái tương ứng của nó. Thì ∀ qi, qj ∈ Q, và w ∈ Σ+, δ*(qi, w) = qj nếu và chỉ nếu có trong GM một con đường mang nhãn là w đi từ qi đến qj. „ Bảng truyền - (transition table) „ Là bảng trong đó các nhãn của hàng (ô tô đậm trên hàng trong hình bên) biểu diễn cho trạng thái hiện tại, còn nhãn của cột (ô tô đậm trên cột trong hình bên) biểu diễn cho ký hiệu nhập hiện tại. Các điểm nhập (entry) trong bảng định nghĩa cho trạng thái kế tiếp. Trang 57 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Bảng truyền (tt) „ Bảng truyền gợi ý cho chúng ta một cấu trúc dữ liệu để mô tả cho ôtômát hữu hạn. „ Đồng thời cũng gợi ý cho chúng ta rằng một dfa có thể dễ dàng được hiện thực thành một chương trình máy tính; chẳng hạn bằng một dãy các phát biểu “if”. q2q2q2 q2q2q1 q1q0q0 ba a, b a, ba bq0 q1 q2 Trang 58 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ „ Tìm dfa chấp nhận ngôn ngữ „ Tìm dfa M1 chấp nhận tập tất cả các chuỗi trên Σ = {a, b} được bắt đầu bằng chuỗi ab. „ Tìm dfa M2 chấp nhận tập tất cả các chuỗi trên Σ = {0, 1}, ngoại trừ những chuỗi chứa chuỗi con 001. a b a, b a, b a bq1 q3 q2q0 1 0, 1 10 1 0 0 λ 0 00 001 Trang 59 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Bài tập dfa „ Tìm dfa chấp nhận ngôn ngữ „ L1 = {vwvR ∈ {a, b}*: |v| = 2} „ L2 = {ababn: n ≥ 0} ∪ {aban: n ≥ 0} „ L3 = {anbm : (n+m) mod 2= 0} „ L4 = {w ∈ {a, b}*: na(w) chẵn, nb(w) lẽ} „ L5 = {w ∈ {0, 1}*: giá trị thập phân của w chia hết cho 5} „ L6 = {w ∈ {a, b}*: số kí tự a trong chuỗi là một số lẽ} Trang 60 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ngôn ngữ chính qui „ Định nghĩa 2.3 „ Một ngôn ngữ L được gọi là chính qui nếu và chỉ nếu tồn tại một accepter hữu hạn đơn định M nào đó sao cho L = L(M) „ Ví dụ „ Chứng minh rằng ngôn ngữ L= {awa : w ∈ {a,b}*} là chính qui. a a, b b b a a b q2 q1 q3q0 Trang 61 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Accepter hữu hạn không đơn định „ Định nghĩa 2.4 „ Một accepter hữu hạn không đơn định (nondeterministic finite state accepter) hay nfa được định nghĩa bằng bộ năm: M = (Q , Σ, δ, q0, F ) trong đó Q, Σ, q0, F được định nghĩa như đối với accepter hữu hạn đơn định còn δ được định nghĩa là: δ : Q × (Σ ∪ { λ}) → 2Q „ Nhận xét „ Có hai khác biệt chính giữa định nghĩa này và định nghĩa của một dfa. Trang 62 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Accepter hữu hạn không đơn định (tt) „ Nhận xét (tt) „ Đối với nfa miền trị của δ là tập 2Q, vì vậy giá trị của nó không còn là một phần tử đơn của Q, mà là một tập con của nó và đặc biệt có thể là ∅, tức là có thể không có định nghĩa cho một δ(q, a) nào đó. Người ta gọi trường hợp này là một cấu hình chết (dead configuration), và có thể hình dung trong trường hợp này ôtômát dừng lại, không hoạt động nữa. „ Thứ hai định nghĩa này cho phép λ như là một đối số thứ hai của δ. Điều này có nghĩa là nfa có thể thực hiện một sự chuyển trạng thái mà không cần phải lấy vào một kí hiệu nhập nào. „ Tương tự như dfa, một nfa cũng có thể được biểu diễn bằng một ĐTCTT. Trang 63 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ „ Hàm chuyển trạng thái mở rộng „ Định nghĩa 2.5 „ Cho một nfa, hàm chuyển trạng thái mở rộng được định nghĩa sao cho δ*(qi, w) chứa qj nếu và chỉ nếu có một con đường trong ĐTCTT đi từ qi đến qj mang nhãn w. Điều này đúng với mọi qi, qj ∈ Q và w ∈ Σ*. a q0 q1 q2 q4 q5 q3 a (a) a a a a 0, 11q0 q1 q20 λ (b) Trang 64 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Hàm chuyển trạng thái mở rộng „ Ví dụ „ δ*(q1, λ) = {q1, q2, q0} „ δ*(q2, λ) = {q2, q0} „ δ*(q0, a) = {q1, q2, q0} „ δ*(q1, a) = {q1, q2, q0} „ δ*(q1, b) = {q2, q0} a b, λ λ q0 q1 q2 Trang 65 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ngôn ngữ của nfa „ Định nghĩa 2 .6 „ Ngôn ngữ được chấp nhận bởi nfa M = (Q, Σ, δ, q0, F), được định nghĩa như là một tập tất cả các chuỗi được chấp nhận bởi nfa trên. Một cách hình thức, L(M) = {w ∈ Σ*: δ*(q0, w) ∩ F ≠ ∅}. „ Ví dụ „ Ngôn ngữ được chấp nhận bởi ôtômát bên dưới là L = {(10)n: n ≥ 0} 0, 11q0 q1 q20 λ Trang 66 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Cách tính δ* „ Với T là một tập con của Q, ta định nghĩa „ Người ta thường hiện thực cách tính các hàm này δ(q, a), δ(T, a), δ*(q, λ), δ*(T, λ) lần lượt bằng các hàm move(q, a), move(T, a), λ-closure(q), λ-closure(T) (λ- closure đọc là bao đóng-λ) „ δ*(q, a) = λ-closure(move(λ-closure(q), a)) „ δ*(T, a) = λ-closure(move(λ-closure(T) ( ) ( )U Tq aqaT ∈ = ,, δδ ( ) ( )U Tq aqaT ∈ = ,,* δδ( ) ( )U Tq qT ∈ = λδλδ ,,* Trang 67 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ „ Hãy tính δ*(q0, a). „ δ*(q0, a) = λ-closure(move(λ-closure(q0), a)) „ λ-closure(q0) = {q0, q1, q2} „ move({q0, q1, q2}, a) = {q4, q0, q3} „ λ-closure({q4, q0, q3}) = {q4, q0, q3, q5, q1, q2} „ Vậy δ*(q0, a) = {q0, q1, q2, q3, q4, q5} a a λλ q0 q1 a q4 q2 q3 λ q5 q5 q5q4 q3 q2 q2q0, q3q1 q1q4q0 λa Trang 68 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Một định nghĩa khác về dfa - dfa mở rộng „ Một dfa là một trường hợp đặc biệt của một nfa trong đó „ Không có chuyển trạng thái-rỗng, „ Đối với mỗi trạng thái q và một kí hiệu nhập a, có tối đa một cạnh chuyển trạng thái đi ra khỏi q và có nhãn là a. „ Về bản chất định nghĩa này và định nghĩa trước đây là tương đương nhau (cùng định nghĩa tính đơn định của dfa). Nó chỉ khác định nghĩa thứ nhất ở chỗ cho phép khả năng không có một sự chuyển trạng thái đối với một cặp trạng thái và kí hiệu nhập. Trong trường hợp này thì ta xem như nó rơi vào một trạng thái bẫy không kết thúc mà trạng thái này không được vẽ ra. Trang 69 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ „ Dfa trong hình (a) đơn giản hơn dfa trong hình (b) mặc dù chúng cùng chấp nhận một ngôn ngữ như nhau. „ Vậy dfa mở rộng và dfa dfa đầy đủ theo định nghĩa ban đầu thật sự là tương đương nhau và chúng chỉ khác nhau ở một trạng thái bẫy không kết thúc. 0 1 q0 q1 (a) 0 1 q0 q1 q2 0, 1 10 (b) Trang 70 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Bài tập nfa „ Tìm nfa chấp nhận ngôn ngữ „ L1 = {tập tất cả các số thực của Pascal} „ Một “run” trong một chuỗi là một chuỗi con có chiều dài tối thiểu 2 kí tự, dài nhất có thể và bao gồm toàn các kí tự giống nhau. Chẳng hạn, chuỗi abbbaabba chứa một “run” của b có chiều dài 3, một “run” của a có chiều dài 2 và một “run” của b có chiều dài 2. Tìm các nfa và dfa cho mỗi ngôn ngữ sau trên {a, b}. „ L2 = {w: w không chứa “run” nào có chiều dài nhỏ hơn 3} „ L3 = {w: mỗi “run” của a có chiều dài hoặc 2 hoặc 3} „ L4 = {w ∈ {0, 1}*: mỗi chuỗi con bốn kí hiệu có tối đa hai kí hiệu 0}. Trang 71 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Sự tương đương giữa nfa và dfa „ Sư tương đương giữa hai ôtômát „ Hai accepter được gọi là tương đương nhau nếu chúng cùng chấp nhận một ngôn ngữ như nhau. „ Ví dụ „ Dfa và nfa sau là tương đương nhau vì cùng chấp nhận ngôn ngữ {(10)n: n ≥ 0} 0,1 1 10 0 q0 q1 q2 0, 11q0 q1 q20 λ Trang 72 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Sự tương đương giữa nfa và dfa (tt) „ Nhận xét „ Dfa về bản chất là một loại giới hạn của nfa, nên lớp các dfa là một lớp con của lớp nfa. Nhưng nó có phải là một lớp con thực sự hay không? Rất hay là người ta đã chứng minh được rằng hai lớp này là tương đương nhau, tức là với một nfa thì sẽ có một dfa tương đương với nó. „ Ví dụ „ Hãy xây dựng dfa tương đương với nfa bên. a a b λq0 q1 q2 q0q2 q2q1q1 q1q0 λba Trang 73 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ „ Xây dựng dfa bằng cách mô phỏng lại quá trình chấp nhận một chuỗi bất kỳ của nfa „ δ*(q0, λ) = {q0} „ δ*({q0}, a) = {q1, q2} δ*({q0}, b) = ∅ „ δ*({q1, q2}, a) = {q1, q2} δ*({q1, q2}, b) = {q0} „ Chú ý „ Một trạng thái của nfa là một tập trạng thái của dfa „ Trạng thái kết thúc của nfa là trạng thái mà có chứa trạng thái kết thúc của dfa. q0q2 q2q1q1 q1q0 λba b a a b a, b {q0} ∅ {q1, q2} Trang 74 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Định lý về sự tương đương „ Định lý 2.2 „ Cho L là ngôn ngữ được chấp nhận bởi một accepter hữu hạn không đơn định MN = (QN, Σ, δN, q0, FN), thì tồn tại một accepter hữu hạn đơn định MD = (QD, Σ, δD, {q0}, FD) sao cho L = L(MD). „ Thủ tục: nfa_to_dfa „ Input: nfa MN = (QN, Σ, δN, q0, FN) „ Output: ĐTCTT GD của dfa MD Trang 75 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Thủ tục: nfa_to_dfa B1. Tạo một đồ thị GD với đỉnh khởi đầu là tập δN*(q0, λ). B2. Lặp lại các bước B3 đến B6 cho đến khi không còn cạnh nào thiếu. B3. Lấy một đỉnh bất kỳ {qi, qj, … , qk} của GD mà có một cạnh còn chưa được định nghĩa đối với một a nào đó ∈ Σ. B4. Tính δN*({qi, qj, … , qk}, a) = {ql, qm, … , qn}. B5. Tạo một đỉnh cho GD có nhãn {ql, qm, … , qn} nếu nó chưa tồn tại. B6. Thêm vào GD một cạnh từ {qi, qj, … , qk} đến {ql, qm, … , qn} và gán nhãn cho nó bằng a. B7. Mỗi trạng thái của GD mà nhãn của nó chứa một qf bất kỳ ∈ FN thì được coi là một đỉnh kết thúc. Trang 76 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ „ Hãy biến đổi nfa dưới (có bảng truyền tương ứng bên cạnh) thành dfa tương đương. a , b a a λ b λ q0 q1 q3 q2 q4 b a, λ a q3q4 q4q3q4q3 q1, q2q2 q2q0q1 q3q1q1q0 λba Trang 77 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ (tt) q3q4 q4q3q4q3 q1, q2q2 q2q0q1 q3q1q1q0 λba „ δ*(q0, λ) = {q0, q3, q4} „ δ*({q0, q3, q4}, a) = {q1, q2, q4} „ δ*({q0, q3, q4}, b) = {q1, q2, q3, q4} „ δ*({q1, q2, q4}, a) = {q0, q1, q2, q3, q4} „ δ*({q1, q2, q4}, b) = {q3, q4} „ δ*({q1, q2, q3, q4}, a) = {q0, q1, q2, q3, q4} „ δ*({q1, q2, q3, q4}, b) = {q3, q4} „ δ*({q0, q1, q2, q3, q4}, a) = {q0, q1, q2, q3, q4} „ δ*({q0, q1, q2, q3, q4}, b) = {q1, q2, q3, q4} „ δ*({q3, q4}, a) = {q4} δ*({q3, q4}, b) = {q3, q4} „ δ*({q4}, a) = ∅ δ*({q4}, b) = {q3, q4} Trang 78 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ (tt) q3q4 q4q3q4q3 q1, q2q2 q2q0q1 q3q1q1q0 λba b a ab ab b a b a a {q0, q3, q4} {q1, q2, q4} {q1, q2, q3, q4} {q0, q1, q2, q3, q4}{q3, q4} {q4} Trang 79 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Bài tập biến đổi nfa thành dfa „ Biến đổi những nfa sau thành dfa tương đương F = {q4}F = {q2} F = {q0}q3q4q4q4q3, q4q4 q2, q3q3q4q4q3q4q3q0, q4q3 q0, q2q2q1q2q1q2 q3q3q1, q2q1q0q2q2q1q2, q0q2q1 q1q2q1q0q3q3q1, q3q0q1q3q1q0 λbaλbaλba Nfa M3Nfa M2Nfa M1 Trang 80 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Rút gọn số trạng thái của một dfa „ Hai dfa được vẽ trong (a) và (b) là tương đương nhau 0, 1 1 0 0, 1q0 q1 q2 (b) 0 0 1 0, 1 1 0 0, 1 1 1 0 q0 q1 q2 q3 q4 q5 (a) Trang 81 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Rút gọn số trạng thái của một dfa (tt) „ Nhận xét „ Trong hình (a) có một trạng thái đặc biệt, trạng thái q5, nó là trạng thái không đạt tới được từ trạng thái khởi đầu, người ta gọi nó là trạng thái không đạt tới được. „ Trạng thái không đạt tới được (inaccessible state) „ Là trạng thái mà không tồn tại con đường đi từ trạng thái khởi đầu đến nó. „ Những trạng thái không đạt tới được (TTKĐTĐ) có thể bỏ đi (kèm với các cạnh chuyển trạng thái liên quan tới nó) mà không làm ảnh hưởng tới ngôn ngữ được chấp nhận bởi ôtômát. Trang 82 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Rút gọn số trạng thái của một dfa (tt) „ Nhận xét (tt) „ Các chuyển trạng thái từ sau đỉnh q1 và q2 "có vẻ giống nhau", đối xứng nhau và ôtômát thứ hai "có vẻ như" kết hợp hai phần này. „ Từ đây dẫn tới định nghĩa hai trạng thái giống nhau hay không phân biệt được. „ Khái niệm giống nhau được định nghĩa tổng quát dựa trên việc: với mọi chuỗi nếu xuất phát từ hai trạng thái này thì kết quả về mặt chấp nhận chuỗi là giống nhau tức là hoặc cùng rơi vào trạng thái kết thúc, hoặc không cùng rơi vào trạng thái kết thúc. „ Như vậy hai trạng thái này có thể gom chung lại với nhau mà kết quả chấp nhận chuỗi không thay đổi. Trang 83 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Định nghĩa hai trạng thái giống nhau „ Định nghĩa 2.7 „ Hai trạng thái p và q của một dfa được gọi là không phân biệt được (indistinguishable) hay giống nhau nếu với mọi w ∈ ∑* δ*(q, w) ∈ F suy ra δ*(p, w) ∈ F, và δ*(q, w) ∉ F suy ra δ*(p, w) ∉ F, Còn nếu tồn tại một chuỗi w nào đó ∈ ∑* sao cho δ*(q, w) ∈ F còn δ*(p, w) ∉ F, hay ngược lại thì p và q được gọi là phân biệt được (distinguishable) hay khác nhau bởi chuỗi w. „ Nhận xét „ Trạng thái kết thúc và không kết thúc không thể giống nhau. Trang 84 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Nhận xét (tt) „ Chú ý „ Quan hệ giống nhau là một quan hệ tương đương. „ Vì vậy quan hệ này sẽ phân hoạch tập trạng thái Q thành các tập con rời nhau, mỗi tập con bao gồm các trạng thái giống nhau. Trang 85 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Thủ tục đánh dấu - mark „ Để xác định các cặp trạng thái không phân biệt được, người ta thực hiện công việc ngược lại là xác định các cặp trạng thái không giống nhau „ Để làm điều này người ta sử dụng thủ tục mark (đánh dấu) bên dưới. „ Thủ tục: mark „ Input: Các cặp trạng thái, gồm (|Q| × (|Q| -1)/2) cặp, của dfa đầy đủ. „ Output: Các cặp trạng thái được đánh dấu phân biệt được. Trang 86 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Thủ tục đánh dấu - mark B1. Loại bỏ tất cả các TTKĐTĐ. B2. Xét tất cả các cặp trạng thái (p, q). Nếu p ∈ F và q ∉ F hay ngược lại, đánh dấu cặp (p, q) là phân biệt được. Các cặp trạng thái được đánh dấu ở bước này sẽ được ghi là đánh dấu ở bước số 0 (gọi là bước cơ bản). Lặp lại bước B3 cho đến khi không còn cặp nào không được đánh dấu trước đó được đánh dấu ở bước này. B3. Đối với mọi cặp (p, q) chưa được đánh dấu và mọi a ∈ ∑, tính δ(p, a) = pa và δ(q, a) = qa. Nếu cặp (pa, qa) đã được đánh dấu là phân biệt được ở lần lặp trước đó, thì đánh dấu (p, q) là phân biệt được. Các cặp được đánh dấu ở bước này sẽ được ghi là được đánh dấu ở bước thứ i nếu đây là lần thứ i băng qua vòng lặp. Trang 87 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Thủ tục đánh dấu – mark (tt) „ Định lý 2.3 „ Thủ tục mark, áp dụng cho một dfa đầy đủ bất kỳ M = (Q, ∑, δ, q0, F), kết thúc và xác định tất cả các trạng thái phân biệt được. „ Bổ đề 1 „ Cặp trạng thái qi và qj là phân biệt được bằng chuỗi có độ dài n, nếu và chỉ nếu có các chuyển trạng thái δ(qi, a) = qk và δ(qj, a) = ql với một a nào đó ∈ ∑, và qk và ql là cặp trạng thái phân biệt được bằng chuỗi có độ dài n-1. Trang 88 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Thủ tục đánh dấu – mark (tt) „ Bổ đề 2 „ Khi băng qua vòng lặp trong bước⎫lần thứ n, thủ tục sẽ đánh dấu được thêm tất cả các cặp trạng thái phân biệt được bằng chuỗi có độ dài n mà chưa được đánh dấu. „ Bổ đề 3 „ Nếu thủ tục dừng lại sau n lần băng qua vòng lặp trong bước 3, thì không có cặp trạng thái nào của dfa mà phân biệt được bằng chuỗi có chiều dài lớn hơn n. Trang 89 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Thủ tục rút gọn - reduce „ Thủ tục: reduce „ Input: dfa M = (Q, Σ, δ, q0, F) „ Output: dfa tối giản B1. Sử dụng thủ tục mark để tìm tất cả các cặp trạng thái phân biệt được. Từ đây tìm ra các tập của tất cả các trạng thái không phân biệt được, gọi là {qi, qj, … , qk}, {ql, qm, … , qn}, ... B2. Đối với mỗi tập {qi, qj, … , qk} các trạng thái không phân biệt được, tạo ra một trạng thái có nhãn ij… k cho . ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛= ∧∧∧∧∧ FqQM ,,,, 0δΣ ∧ M Trang 90 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Thủ tục rút gọn - reduce B3. Đối với mỗi quy tắc chuyển trạng thái của M có dạng δ(qr, a) = qp, tìm các tập mà qr và qp thuộc về. Nếu qr ∈ {qi, qj, … , qk} và qp ∈ {ql, qm, … , qn}, thì thêm vào quy tắc ( ij… k, a) = lm… n. B4. Trạng thái khởi đầu là trạng thái của mà nhãn của nó có chứa 0. B5. là tập tất cả các trạng thái mà nhãn của nó chứa i sao cho qi∈ F. ∧ δ ∧ δ ∧ F ∧ 0q Trang 91 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ „ Hãy rút gọn trạng thái của dfa sau (cho kèm bảng truyền tương ứng bên cạnh). q4q4q4 q4q2q3 q4q1q2 q4q2q1 q3q1q0 10 0 0 0 01 1 1 1 0,1 q0 q3 q2 q1 q4 Trang 92 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ (tt) q4q4q4 q4q2q3 q4q1q2 q4q2q1 q3q1q0 10 (q3, q4)(q2, q3)(q1, q3)(q0, q4)(q0, q2) (q2, q4)(q1, q4)(q1, q2)(q0, q3)(q0, q1) 0,1 0 1 0, 1 0 123 4 0 1,2,3 4 90 90 90 90 9191 91 Trang 93 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Định lý „ Định lý 2.4 „ Cho một dfa M bất kỳ, áp dụng thủ tục reduce tạo ra một dfa khác sao cho L(M) = L( ) Hơn nữa là tối giản theo nghĩa không có một dfa nào khác có số trạng thái nhỏ hơn mà cũng chấp nhận L(M). ∧ M ∧ M Trang 94 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ „ Hãy rút gọn trạng thái của dfa sau (cho kèm bảng truyền tương ứng bên cạnh). 0 0 01 1 1 1 0,1 0,1 0,1 0 q0 q1 q2 q3 q4 q5 q6 q6q6q6 q5q6q5 q5q5q4 q4q3q3 q5q5q2 q4q3q1 q2q1q0 10 Trang 95 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ (tt) q6q6q6 q5q6q5 q5q5q4 q4q3q3 q5q5q2 q4q3q1 q2q1q0 10 (q3, q6)90(q2, q3)91(q0, q6)91 (q3, q5)90(q1, q6)90(q0, q5)91 (q3, q4)91(q1, q5)90(q0, q4)90 (q5, q6)(q2, q6)90(q1, q4)91(q0, q3)90 (q4, q6)90(q2, q5)90(q1, q3)(q0, q2)90 (q4, q5)90(q2, q4)(q1, q2)90(q0, q1)90 1,3 2,4 5,6 0 0,1 0 1 1 0,1 0 1,3 2,4 5,6 Trang 96 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Bài tập rút gọn dfa „ Rút gọn những dfa sau thành dfa tối giản q4q6q7q7q7 q7q1q6q6q7q6 q5q5q5q6q4q5 q3q2q4q0q3q4q3q5q4q5q4q4 q4q1q3q0q4q3q4q5q3q3q3 q3q0q2q4q1q2q3q2q2q3q4q2 q4q2q1q3q2q1q3q2q1q2q4q1 q3q1q0q2q1q0q2q1q0q4q1q0 babababa Dfa M4Dfa M3Dfa M2Dfa M1