Bài giảng lý thuyết ôtômát và ngôn ngữ hình thức: Chương 2 (Chi tiết)

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 47 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Accepter hữu hạn đơn định

(cid:132) Đị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

(cid:132) Q là một tập hữu hạn các trạng thái nội (internal states), (cid:132) Σ là một tập hữu hạn các ký hiệu được gọi là bảng chữ cái ngõ

M = (Q, Σ, δ, q0, F),

(cid:132) δ: 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 48 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

nhập (input alphabet),

Accepter hữu hạn đơn định (tt)

(cid:132) q0 ∈ Q là trạng thái khởi đầu (initial state), (cid:132) F ⊆ Q là một tập các trạng thái kết thúc (final states) (hay

(cid:132) Chú ý

(cid:132) Ôtômát hữu hạn không có bộ nhớ so với mô hình tổng quát.

Trang 49 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

còn được gọi là trạng thái chấp nhận).

Hoạt động của một dfa

(cid:132) Hoạt động của một dfa

(cid:132) 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.

(cid:132) Trong suốt mỗi lần di chuyển, cơ cấu nhập tiến về phía phải

(cid:132) Khi gặp kí hiệu kết thúc chuỗi, chuỗi là được chấp nhận

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.

Trang 50 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

(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

(cid:132) Để 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.

(cid:132) Các đỉnh biểu diễn các trạng thái. (cid:132) Các cạnh biểu diễn các chuyển trạng thái. (cid:132) Các nhãn trên các đỉnh là tên các trạng thái. (cid:132) Các nhãn trên các cạnh là giá trị hiện tại của kí hiệu nhập. (cid:132) 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

(cid:132) Các trạng thái kết thúc được vẽ bằng một vòng tròn đôi.

Trang 51 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Ví dụ

(cid:132) Cho dfa sau

M = (Q, Σ, δ, q0, F) Q = {q0, q1, q2}, Σ = {0, 1}, F = {q1}, còn δ được cho bởi

(cid:132) Đồ thị chuyển trạng thái tương ứng là

δ(q0, 0) = q0, δ(q1, 0) = q0, δ(q2, 0) = q2, δ(q0, 1) = q1, δ(q1, 1) = q2, δ(q2, 1) = q1,

0 0

1 1

q2 q1 q0

Trang 52 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

1 0

Hàm chuyển trạng thái mở rộng

(cid:132) Hàm chuyển trạng thái mở rộng δ* được định nghĩa một

cách đệ qui như sau

(cid:132) δ*(q, λ) = q, (cid:132) δ*(q, wa) = δ(δ*(q, w), a), ∀ q ∈ Q, w ∈ Σ*, a ∈ Σ.

(cid:132) Ví dụ

(cid:132) Nếu δ(q0, a) = q1, và δ(q1, b) = q2, (cid:132) Thì δ*(q0, ab) = q2

(cid:132) Chú ý

(cid:132) δ không có định nghĩa cho chuyển trạng thái rỗng, tức là không

Trang 53 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

định nghĩa cho δ(q, λ).

Ngôn ngữ và dfa

(cid:132) Định nghĩa 2.2

(cid:132) Ngôn ngữ được chấp nhận bởi dfa M = (Q, Σ, δ, q0, F) là tập tất

(cid:132) L(M) = {w ∈ Σ*: δ*(q0, w) ∈ F}.

(cid:132)

(cid:132) Nhận xét: )ML (

cả các chuỗi trên Σ được chấp nhận bởi M.

Trang 54 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

= {w ∈ Σ* : δ*(q0, w) ∉ F}.

Ví dụ

(cid:132) Ví dụ

a a, b

(cid:132) Xét dfa M sau

b a, b

(cid:132) Dfa trên chấp nhận ngôn ngữ sau

q0 q2 q1

L(M) = {anb : n ≥ 0} (cid:132) Trạng thái bẫy (trap state): là trạng thái mà sau khi ôtômát đi

(cid:132) Trạng thái bẫy có thể là trạng thái kết thúc hoặc không. (cid:132) Định nghĩa trên cũng có thể mở rộng ra cho nhóm các trạng thái

vào sẽ không bao giờ thoát ra được.

Trang 55 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

bẫy kết thúc hay không kết thúc.

Định lý, bảng truyền

(cid:132) Định lý 2.1

(cid:132) 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.

(cid:132) Bảng truyền - (transition table)

(cid:132) 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 56 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Bảng truyền (tt)

a, b a

b a, b

q0 q2 q1

(cid:132) Bảng truyền gợi ý cho chúng ta một cấu trúc dữ liệu để mô tả

a q0 q2 q2 b q1 q2 q2 q0 q1 q2

(cid:132) Đồ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”.

Trang 57 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

cho ôtômát hữu hạn.

Ví dụ

(cid:132) Tìm dfa chấp nhận ngôn ngữ

(cid:132) Tìm dfa M1 chấp nhận tập tất cả các chuỗi trên Σ = {a, b} được

(cid:132) Tìm dfa M2 chấp nhận tập tất cả các chuỗi trên Σ = {0, 1},

bắt đầu bằng chuỗi ab.

ngoại trừ những chuỗi chứa chuỗi con 001.

0, 1 a, b 1 0

0 a b 1 0 001 00 0 λ q0 q2

1 q1 a b

Trang 58 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

a, b

Bài tập dfa

(cid:132) Tìm dfa chấp nhận ngôn ngữ (cid:132) L1 = {vwvR ∈ {a, b}*: |v| = 2} (cid:132) L2 = {ababn: n ≥ 0} ∪ {aban: n ≥ 0} (cid:132) L3 = {anbm : (n+m) mod 2= 0} (cid:132) L4 = {w ∈ {a, b}*: na(w) chẵn, nb(w) lẽ} (cid:132) L5 = {w ∈ {0, 1}*: giá trị thập phân của w chia hết cho 5} (cid:132) L6 = {w ∈ {a, b}*: số kí tự a trong chuỗi là một số lẽ}

Trang 59 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Ngôn ngữ chính qui

(cid:132) Định nghĩa 2.3

(cid:132) 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

(cid:132) Ví dụ

L = L(M)

(cid:132) Chứng minh rằng ngôn ngữ L= {awa : w ∈ {a,b}*} là chính b

qui. a

a a

q2 q3

q0 b q1

Trang 60 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

a, b

Accepter hữu hạn không đơn định

(cid:132) Định nghĩa 2.4

(cid:132) 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à:

(cid:132) Nhận xét

(cid:132) Có hai khác biệt chính giữa định nghĩa này và định nghĩa của

δ : Q × (Σ ∪ { λ}) → 2Q

Trang 61 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

một dfa.

Accepter hữu hạn không đơn định (tt)

(cid:132) Nhận xét (tt)

(cid:132) Đố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.

(cid:132) 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. (cid:132) Tương tự như dfa, một nfa cũng có thể được biểu diễn bằng

Trang 62 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

một ĐTCTT.

Ví dụ

a a

q2 q1 q3 a 0, 1

q2 q1 1 0 q0 q0 a

q4 q5

λ (b)

(cid:132) 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 ∈ Σ*.

Trang 63 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

a (a) (cid:132) Hàm chuyển trạng thái mở rộng (cid:132) Định nghĩa 2.5

Hàm chuyển trạng thái mở rộng

(cid:132) Ví dụ

b, λ a

(cid:132) δ*(q1, λ) = {q1, q2, q0} (cid:132) δ*(q2, λ) = {q2, q0} (cid:132) δ*(q0, a) = {q1, q2, q0} (cid:132) δ*(q1, a) = {q1, q2, q0} (cid:132) δ*(q1, b) = {q2, q0}

Trang 64 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

q2 q0 q1

Ngôn ngữ của nfa

(cid:132) Định nghĩa 2 .6

(cid:132) 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,

(cid:132) Ví dụ

(cid:132) Ngôn ngữ được chấp nhận bởi ôtômát bên dưới là

L(M) = {w ∈ Σ*: δ*(q0, w) ∩ F ≠∅}.

L = {(10)n: n ≥ 0}

0, 1

q2 q1 1 0 q0

Trang 65 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Cách tính δ*

, aq

δ

(cid:132) Với T là một tập con của Q, ta định nghĩa ( , aT

)

(

δ

, aq

δ

λ

( , aT

)

(

)

( T

(

)

δ U Tq ∈

(cid:132)

(cid:132) 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)

Trang 66 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Ví dụ a

q3 λ q2 q1

a q4 q0, q3 λ q1 q2 a

λ a q4 q5

(cid:132) Hãy tính δ*(q0, a). (cid:132) δ*(q0, a) = λ-closure(move(λ-closure(q0), a)) (cid:132) λ-closure(q0) = {q0, q1, q2} (cid:132) move({q0, q1, q2}, a) = {q4, q0, q3} (cid:132) λ-closure({q4, q0, q3}) = {q4, q0, q3, q5, q1, q2} (cid:132) Vậy δ*(q0, a) = {q0, q1, q2, q3, q4, q5}

Trang 67 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

q0 q1 q2 q3 q4 q5

Một định nghĩa khác về dfa - dfa mở rộng

(cid:132) Một dfa là một trường hợp đặc biệt của một nfa trong đó

(cid:132) Không có chuyển trạng thái-rỗng, (cid:132) Đố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.

(cid:132) 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 68 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Ví dụ

0 0

q1 q0 q0 q1 1

1 0 1

(cid:132) Dfa trong hình (a) đơn giản hơn dfa trong hình (b) mặc dù

0, 1 (b) (a)

chúng cùng chấp nhận một ngôn ngữ như nhau.

(cid:132) 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.

Trang 69 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Bài tập nfa

(cid:132) Tìm nfa chấp nhận ngôn ngữ

(cid:132) L1 = {tập tất cả các số thực của Pascal} (cid:132) 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}.

(cid:132) L2 = {w: w không chứa “run” nào có chiều dài nhỏ hơn 3} (cid:132) L3 = {w: mỗi “run” của a có chiều dài hoặc 2 hoặc 3} (cid:132) L4 = {w ∈ {0, 1}*: mỗi chuỗi con bốn kí hiệu có tối đa hai kí

Trang 70 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

hiệu 0}.

Sự tương đương giữa nfa và dfa

(cid:132) Sư tương đương giữa hai ôtômát

(cid:132) Hai accepter được gọi là tương đương nhau nếu chúng cùng

(cid:132) Ví dụ

(cid:132) Dfa và nfa sau là tương đương nhau vì cùng chấp nhận ngôn

chấp nhận một ngôn ngữ như nhau.

ngữ {(10)n: n ≥ 0}

0,1

0, 1 1 1 0 q2 q1 q0 1 0 q1 q0 q2

Trang 71 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

λ 0

Sự tương đương giữa nfa và dfa (tt)

(cid:132) Nhận xét

(cid:132) 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ó.

(cid:132) Ví dụ

a λ

(cid:132) Hãy xây dựng dfa tương đương với nfa bên.

q0 q2 q1

λba q1 q1 q2

Trang 72 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

a q0 q0 q1 q2

Ví dụ

(cid:132) 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

λba q1 q1 q2

(cid:132) δ*(q0, λ) = {q0} (cid:132) δ*({q0}, a) = {q1, q2} (cid:132) δ*({q1, q2}, a) = {q1, q2}

q0 q0 q1 q2

δ*({q0}, b) = ∅ δ*({q1, q2}, b) = {q0}

(cid:132) Chú ý

{q1, q2} a b {q0}

(cid:132) Một trạng thái của nfa là một tập trạng thái của dfa (cid:132) Trạng thái kết thúc của nfa là

b ∅

a, b

Trang 73 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

trạng thái mà có chứa trạng thái kết thúc của dfa.

Định lý về sự tương đương

(cid:132) Định lý 2.2

(cid:132) Cho L là ngôn ngữ được chấp nhận bởi một accepter hữu hạn

(cid:132) Thủ tục: nfa_to_dfa

(cid:132) Input: nfa MN = (QN, Σ, δN, q0, FN) (cid:132) Output: ĐTCTT GD của dfa MD

Trang 74 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

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

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ỳ ∈

Trang 75 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

FN thì được coi là một đỉnh kết thúc.

Ví dụ

(cid:132) 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

λ q1

a, b

q2 q1 λ q3 q2 a a

q0 a, λ

λ q1 q0 q1, q2 q4 q4 q3 q4

Trang 76 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

b q3 q3 q0 q1 q2 q3 q4

Ví dụ (tt)

λb q1 q3 q2

a q1 q0 q1, q2 q4 q4

(cid:132) δ*(q0, λ) = {q0, q3, q4} (cid:132) δ*({q0, q3, q4}, a) = {q1, q2, q4} (cid:132) δ*({q0, q3, q4}, b) = {q1, q2, q3, q4} (cid:132) δ*({q1, q2, q4}, a) = {q0, q1, q2, q3, q4} (cid:132) δ*({q1, q2, q4}, b) = {q3, q4} (cid:132) δ*({q1, q2, q3, q4}, a) = {q0, q1, q2, q3, q4} (cid:132) δ*({q1, q2, q3, q4}, b) = {q3, q4} (cid:132) δ*({q0, q1, q2, q3, q4}, a) = {q0, q1, q2, q3, q4} (cid:132) δ*({q0, q1, q2, q3, q4}, b) = {q1, q2, q3, q4} (cid:132) δ*({q3, q4}, a) = {q4} (cid:132) δ*({q4}, a) = ∅

q3 q3 q0 q1 q2 q3 q4

Trang 77 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

δ*({q3, q4}, b) = {q3, q4} δ*({q4}, b) = {q3, q4}

Ví dụ (tt)

λb q1 q3 q2

a q1 q0 q1, q2 q4 q4

q3 q3 q0 q1 q2 q3 q4

{q1, q2, q4}

a a b

{q0, q1, q2, q3, q4} b {q0, q3, q4} {q3, q4}

a {q4} a b b b a

Trang 78 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

{q1, q2, q3, q4}

Bài tập biến đổi nfa thành dfa

(cid:132) Biến đổi những nfa sau thành dfa tương đương

Nfa M2

λ q1

a q1 q2 λb q3 q3 q2 q0 λ q1 q3 a q1 q1, q2

Nfa M3 b q2 q3 q0, q2

q4 q4 q2, q3 q0 q1 q2 q3

q0, q4 q3, q4 q0 q1 q2 q3 q4 q0 q1 q2 q3 q4 F = {q0}

Trang 79 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Nfa M1 b q3 q2, q0 q1 q3 q4 F = {q2} a q1, q3 q2 q1 q4 q4 q3 F = {q4}

Rút gọn số trạng thái của một dfa

(cid:132) Hai dfa được vẽ trong (a) và (b) là tương đương nhau

0, 1

q3 0

0, 1 1 q1 0 q0 q2 q0 q1

1 1 1 q2 q5 q4 0, 1 0

0, 1 0 0

Trang 80 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

(b) (a)

Rút gọn số trạng thái của một dfa (tt)

(cid:132) Nhận xét

(cid:132) 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.

(cid:132) Trạng thái không đạt tới được (inaccessible state)

(cid:132) Là trạng thái mà không tồn tại con đường đi từ trạng thái khởi

(cid:132) Những trạng thái không đạt tới được (TTKĐTĐ) có thể bỏ đi

đầu đến nó.

Trang 81 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

(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.

Rút gọn số trạng thái của một dfa (tt)

(cid:132) Nhận xét (tt)

(cid:132) 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.

(cid:132) Từ đây dẫn tới định nghĩa hai trạng thái giống nhau hay không

(cid:132) 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.

(cid:132) Như vậy hai trạng thái này có thể gom chung lại với nhau mà

phân biệt được.

Trang 82 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

kết quả chấp nhận chuỗi không thay đổi.

Định nghĩa hai trạng thái giống nhau

(cid:132) Định nghĩa 2.7

(cid:132) 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,

(cid:132) Nhận xét

(cid:132) Trạng thái kết thúc và không kết thúc không thể giống nhau.

Trang 83 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

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 (tt)

(cid:132) Chú ý

(cid:132) Quan hệ giống nhau là một quan hệ tương đương. (cid:132) 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 84 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Thủ tục đánh dấu - mark

(cid:132) Để 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

(cid:132) Để làm điều này người ta sử dụng thủ tục mark (đánh dấu) bên

(cid:132) Input: Các cặp trạng thái, gồm (|Q| × (|Q| -1)/2) cặp, của dfa

dưới. (cid:132) Thủ tục: mark

(cid:132) Output: Các cặp trạng thái được đánh dấu phân biệt được.

Trang 85 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

đầy đủ.

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.

Trang 86 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

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.

Thủ tục đánh dấu – mark (tt)

(cid:132) Định lý 2.3

(cid:132) 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. (cid:132) Bổ đề 1

(cid:132) 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

Trang 87 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

δ(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.

Thủ tục đánh dấu – mark (tt)

(cid:132) Bổ đề 2

(cid:132) 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.

(cid:132) Bổ đề 3

(cid:132) 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 88 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Thủ tục rút gọn - reduce

(cid:132) Thủ tục: reduce

(cid:132) Input: dfa M = (Q, Σ, δ, q0, F)

(cid:132) Output: dfa tối giản

∧∧∧ , Fq

∧ ∧ , QM =

0δΣ ,

⎛ ⎜ ⎜ ⎝

⎞ ⎟ ⎟ ⎠

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}, ...

∧ được, tạo ra một trạng thái có nhãn ij … k cho . M

Trang 89 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

B2. Đối với mỗi tập {qi, qj, … , qk} các trạng thái không phân biệt

Thủ tục rút gọn - reduce

∧ δ

∧ 0q

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

Trang 90 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

B5. 0. ∧ F 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.

Ví dụ

(cid:132) 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).

1 0,1 0 0 0

q4 q0

q2 0 1 1

Trang 91 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

q3 0 q1 q2 q1 q2 q4 1 q3 q4 q4 q4 q4 q0 q1 q2 q3 q4

Ví dụ (tt)

(cid:57)1 (cid:57)1 (cid:57)0

(cid:57)0 (cid:57)0 (cid:57)1 (cid:57)0 (q0, q1) (q0, q2) (q0, q3) (q0, q4) (q1, q2) (q1, q3) (q1, q4) (q2, q3) (q2, q4) (q3, q4)

0 q1 q2 q1 q2 q4 1 q3 q4 q4 q4 q4 q0 q1 q2 q3 q4

1,2,3

0, 1 0

Trang 92 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

0,1 1 123 0 4

Định lý

(cid:132) Định lý 2.4

(cid:132) 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 M

∧ L(M) = L( ) M 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).

Trang 93 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Ví dụ

(cid:132) 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).

q0 1 0

q2 q1

0 1

1 0,1

q4 0,1 0 q5 q3 q6

0,1 1 0

Trang 94 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

0 q1 q3 q5 q3 q5 q6 q6 q0 q1 q2 q3 q4 q5 q6 1 q2 q4 q5 q4 q5 q5 q6

Ví dụ (tt)

(q4, q5)(cid:57)0 (q4, q6)(cid:57)0 (q5, q6)

(q0, q1)(cid:57)0 (q0, q2)(cid:57)0 (q0, q3)(cid:57)0 (q0, q4)(cid:57)0 (q0, q5)(cid:57)1 (q0, q6)(cid:57)1 (q1, q2)(cid:57)0 (q1, q3) (q1, q4)(cid:57)1 (q1, q5)(cid:57)0 (q1, q6)(cid:57)0 (q2, q3)(cid:57)1 (q2, q4) (q2, q5)(cid:57)0 (q2, q6)(cid:57)0 (q3, q4)(cid:57)1 (q3, q5)(cid:57)0 (q3, q6)(cid:57)0 0 q1 q3 q5 q3 q5 q6 q6 1 q2 q4 q5 q4 q5 q5 q6 q0 q1 q2 q3 q4 q5 q6

1,3

1 0

2,4

0,1 1 5,6 2,4

5,6

Trang 95 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

1,3 0 0,1