Bài giảng Lý thuyết tính toán - Bài 02. Automat hữu hạn

GV: Nguyễn Ngọc Tú [email protected] Bài 02. Automat hữu hạn (p01) LÝ THUYẾT TÍNH TOÁN INTRODUCTION TO COMPUTATION THEORY (FORMAL LANGUAGES & AUTOMATA) TIN331 Sử dụng slides của các tác giả: Hồ Văn Quân + Nick Hopper Nội dung  Accepter hữu hạn đơn định  Accepter hữu hạn không đơn định  Sự tương đương giữa Accepter hữu hạn đơn định và Accepter hữu hạn không đơn định  Rút gọn số trạng thái Accepter hữu hạn đơn định – DFA Đị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). Accepter hữu hạn đơn định – DFA  Để 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 δ.  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. Ví dụ.  có hàm chuyển của một ôtômát như sau: δ(1,a)=2, δ(2,b)=2, δ(2,c)=2 1 2 a b c Hoạt động của 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. Đồ 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:  Đỉnh biểu diễn các trạng thái.  Cạnh biểu diễn các chuyển trạng thái.  Nhãn trên các đỉnh là tên các trạng thái.  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. Ví dụ 01.  Cho dfa sau  M = (Q, Σ, δ, q0, F)  Q = {q0, q1, q2}, Σ = {0, 1}, F = {q1},  còn δ được cho bởi δ(q0, 0) = q0, δ(q1, 0) = q0, δ(q2, 0) = q2, δ(q0, 1) = q1, δ(q1, 1) = q2, δ(q2, 1) = q1, q0 0 0 1 q1 q2 1 1 0 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 δ 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, λ). 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:  L’(M)= {w ∈ Σ* : δ*(q0, w) ∉ F}. Ví dụ 02.  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, b a b q0 q1 q2 Đị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. Định lý, bảng truyền a b q0 q0 q1 q1 q2 q2 q2 q2 q2 a, b a, b b q0 q1 q2 a Ví dụ 03.  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 b q1 a q3 a, b q2 q0 1 0, 1 1 0 1 0 0 λ 0 00 001 Ex.  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ẻ} 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 a b b q2 q1 a q3 q0 b 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 định nghĩa là: δ : Q × (Σ ∪ { λ}) → 2Q Ví dụ 04. q2 q1 q3 q4 q5 a a a q0 a a a (a) 0, 1 q0 q2 1 0 q1 λ (b) 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 ∈ Σ*. Ví dụ 05.  δ*(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 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, 1 q0 q1 q2 1 0 λ 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 U δ(T,a)= ∈T qUδ(q,a) δ(q,λ) δ*(T,a)= q∈T δ(q,a) δ*(T,λ) = q∈T Ví dụ 06.  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 λ q0 q4 q1 q1 q0,q3 q2 q2 q3 q4 q5 q5 λ λ q0 q1 a a q4 q2 q3 λ q5 a 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í dụ 07. khác nhau ở một trạng thái bẫy không kết thúc. Ex.  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}. 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 0 1 1 q0 q1 q2 0, 1 q0 q1 q2 1 0 λ 0, 1 Ex.  NFA  DFA a b λ q0 q1 q1 q1 q2 q2 q0 a b λ q0 q1 q2 a Ex. ans  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}  δ*({q1, q2}, a) = {q1, q2}  δ*({q0}, b) = ∅  δ*({q1, q2}, b) = {q0} ∅ a, b a {q1, q2} a {q0} b b Đị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 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. Ex. a b λ q0 q1 q1 q3 q1 q0 q2 q2 q1,q2 q3 q4 q3 q4 q4 q3 b a λ a, q0 q1 b q3 λ a a, λ b a q2 q4 Bài tập – NFA  DFA NfaM1 a b λ q0 q1 q3 q1 q1 q2 q2,q0 q2 q1 q3 q0,q4 q3 q4 q4 q3,q4 q4 F={q2} NfaM2 a b λ q0 q1,q3 q3 q3 q1 q2 q2 q0 q2 q1 q3 q4 q4 q4 q4 q3 F={q4} NfaM3 a b λ q0 q1 q2 q1 q1 q1,q2 q3 q3 q2 q0,q2 q3 q2,q3 F={q0} Rút gọn DFA Rút gọn DFA  Hai trạng thái giống nhau  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  δ*(p, w) ∈ F, và  δ*(q, w) ∉ F  δ*(p, w) ∉ F,  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. Rút gọn DFA – Thủ tục đánh dấu  Xác định các cặp trạng thái không giống nhau  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.  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. Rút gọn DFA – Thủ tục đánh dấu  Đị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. Rút gọn DFA – Thủ tục đánh dấu  Bổ đề 2  Khi băng qua vòng lặp trong bước j 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. Ví dụ q0 q1 q2 q3 q4 0 1 1 0 1 1 0 0 0,1 mark: (q0, q1) 1 (q0, q3) 1 (q1, q2) (q1, q4) 0 (q2, q4) 0 (q0, q2) 1 (q0, q4) 0 (q1, q3) (q2, q3) (q3, q4) 0 Ví dụ  Dùng thủ tục reduce dẫn đến ba tập trạng thái không phân biệt được là {q0}, {q1, q2, q3} và {q4} từ đó ba trạng thái của là 0, 123 và 4. 0 123 4 1 0,1 0 0,1  Input DFA M = (Q, , , q0, F), output DFA tối giản  Dùng thủ tục mark để tìm mọi cặp trạng thái phân biệt được. Từ đây tìm được các tập của tất cả các trạng thái không phân biệt được là {qi, qj, ..., qk}, {ql, qm, ..., qn},...  Đối với mỗi tập {qi, qj, ..., qk} các trạng thái không phân biệt như vậy, tạo một trạng thái được gắn nhãn ij...k cho  Đối với mỗi qui 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 qui tắc (ij...k, a) = lm...n.  Trạng thái khởi đầu là trạng thái của mà nhãn của nó có chứa 0.  là tập các trạng thái kết thúc của mà nhãn chứa i sao cho qi  F.