Trang 47
Lý thuyếtÔtômát &NNHT- KhoaCông NghệThôngTin
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 functi on).
Để 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 δ.
Trang48
Lý thuyếtÔtômát&NNHT -KhoaCông NghệThôngTin
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.
Trang49
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.
Trang50
LýthuyếtÔtômát & NNHT-Khoa CôngNghệ ThôngTin
Đồ 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 51
LýthuyếtÔtômát & NNHT-Khoa CôngNghệ ThôngTin
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à
0 q0
1
0
1 0 q1 q2
1
Trang 52
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à k
hông
định nghĩa cho δ(q, λ).
Trang 53
LýthuyếtÔtômát &NNHT -Khoa CôngNghệ ThôngTin
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}.
Trang 54
Lýthuyết Ôtômát &NNHT-Khoa Công NghệThôngTin
Ví dụ
Ví dụ a a, b
Xét dfa M sau b a, b
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.
q0 q1 q2
Định nghĩa trên cũng có thể mở rộng ra cho nhóm các trạn g thái
bẫy kết thúc hay không kết thúc.
Trang 55
Lýthuyết Ôtômát &NNHT-Khoa Công NghệThôngTin
Đị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 tr ong
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ôngNghệ ThôngTin
Bảng truyền (tt)
a
a, b
a b
q0 q0 q1 q1 q2 q2 q2 q2 q2
b a, b
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”.
Trang57
Lýthuyết Ôtômát&NNHT-Khoa Công NghệThôngTin
q0 q1 q2
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.
q0 a b
q1 a
b
a, b q2
0, 1
1
0
λ 0 0 00 001 1
0 1
q3
a, b Trang 58
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ẽ}
Trang59
LýthuyếtÔtômát &NNHT -Khoa CôngNghệ ThôngTin
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. q0 b
a b
a
q2 q
3
b
q1 a,
b Trang60
LýthuyếtÔtômát &NNHT -Khoa CôngNghệ ThôngTin
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.
Trang61
Lý thuyếtÔtômát&NNHT -KhoaCông NghệThôngTin
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ó k hô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ứ h ai
của δ. Điều này có nghĩa là nfa có thể thực hiện một sự ch uyể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ằn g
một ĐTCTT.
Trang62
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ
a a
q0 a a
a
a (a)
Hà m ch uy ển trạ
ng th ái m ở rộ
n g q
0
q1 q2 q3 q4 q5
q1 q2
1
0 λ
(b)
0, 1
Đị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 ∈ Σ*.
Trang 63
LýthuyếtÔtômát& NNHT-Khoa CôngNghệ ThôngTin
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, λ
Trang 64
LýthuyếtÔtômát &NNHT -Khoa CôngNghệ ThôngTin
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}
q0 1
0 q1 0, 1 q2
λ
Trang65
Lý thuyếtÔtômát &NNHT -KhoaCông NghệThôngTin
Cách tính δ *
Với T là một tập con của Q, ta định nghĩa δ ( T , a )
=
δ ( q, a ) δ* ( T , λ
) =
q∈T
δ ( q, λ ) δ* ( T ,
a ) =
q∈T
qUδ(q, a)
Người ta thường hiện thực cách tính các hàm này δ (q,
U U ∈T
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ôngNghệ ThôngTin
Ví dụ
a λ
q0 q4 q1 q1 q0, q3 q2 q2
q3
q4 q5 q5
a
q0 λ
a a
q1 q4
λ λ
q2 q3
q5 Hãy tính δ*(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}
Trang67
Lý thuyếtÔtômát&NNHT -KhoaCông NghệThôngTin
δ*(q0, a) = λ-closure(move(λ-closure(q0), a))
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ươn g
đươ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 ệunhậ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.
Trang68
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
0
q0 q1
1
(a)
Ví dụ
0
q0 q1 0 1 1
q2 0, 1
(b)
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ạ ngthái bẫy không kết thúc.
Trang69
Lý thuyếtÔtômát&NNHT -KhoaCông NghệThôngTin
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ốn g
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 70
LýthuyếtÔtômát & NNHT-Khoa CôngNghệ ThôngTin
Sự tương đương giữa nfa và dfa
0 0
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
q0 1 q1 q2 q0 1
0 0, 1
1 q1 q2
λ
Trang 71
LýthuyếtÔtômát &NNHT -Khoa CôngNghệ ThôngTin
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ằn g
hai lớp này là tương đương nhau, tức là với một nfa thì sẽ c ó
a b λ q0 q1
q1 q1 q2 q2 q0
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.
b
a
q0 q1 q2
Trang72
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}
δ*({q1, q2}, a) = {q1, q2} δ*({q1, q2}, b) = {q0}
a Một trạng thái của nfa là
một tập t rạng thái của dfa a b λ
q0 q1
q1 q1 q2 q2 q0
Chú ý
{q0} b
b ∅
δ*({q0}, a) = {q1, q2} δ*({q0}, b) = ∅
Trạng thái kết thúc của nfa là
a
{q1, q2} trạng thái mà có chứa trạng thái
kết thúc của dfa.
a, b
Trang73
Lý thuyếtÔtômát &NNHT -KhoaCông NghệThôngTin
Đị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 c ho
L = L(MD).
Thủ tục: nfa_to_dfa
Input: nfa MN = (QN, Σ, δN, q0, FN) Output: ĐTCTT GD của dfa MD
Trang74
Lýthuyết Ôtômát& NNHT-Khoa CôngNghệ ThôngTin
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 75
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ
Hãy biến đổi nf a dưới (có bảng truy
ền tương ứng b ên
cạnh) thành df a tương đương.
a, b a
q q1
b
q3
a b λ
q0 q1 q1 q3 q1 q0 q2 q2 q1, q2
q3 q4 q3 q4 q4 q3
λ a
a, λ b
a
q2 q4
Trang76
LýthuyếtÔtômát &N NHT-Khoa CôngNghệ Thôn gTin
Ví dụ (tt)
δ*(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}
a b λ
q0 q1 q1 q3 q1 q0 q2 q2 q1, q2
q3 q4 q3 q4 q4 q3
δ*({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}
Trang77
Lýthuyết Ôtômát& NNHT-Khoa CôngNghệ ThôngTin
Ví dụ (tt)
a b λ
q0 q1 q1 q3 q1 q0 q2 q2 q1, q2
q3 q4 q3 q4 q4 q3
{q0, q3, q4}
{q1, q2, q4}
a
a
a a b b
{q1, q2, q3, q4}
b
{q0, q1, q2, q3, q4}
a
b {q3, q4} {q4} a b
Trang 78
Lýthuyết Ôtô mát& NNHT-Khoa Công
Nghệ Thông Ti n
Bài tập biến đổi nf a thành dfa
Nfa M3
a b λ
q0 q1 q2 q1 q1 q1, q2 q3 q3 q2 q0, q2
q3 q2, q3
F = {q0}
a b λ
q0 q1, q3 q3 q3 q1 q2 q2 q0 q2 q1
q3 q4 q4 q4 q4 q3
F = {q4} Nfa M1
a b λ
q0 q1 q3 q1 q1 q2 q2, q0
q2 q1
q3 q0, q4 q3 q4 q4 q3, q4 q4
F = {q2}
Trang79
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 q
0
0 1 q1 0
q2 1
Biến đổi những nfa sau thành dfa tương đương
q4 q5
q0 q1 q2
1 q3 1
0, 1 1
0 0, 1
0 0, 1 0
(a) (b)
Trang80
LýthuyếtÔtômát &NNHT -Khoa CôngNghệ ThôngTin
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 k hở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 81
Lýthuyết Ôtômát& NNHT-Khoa CôngNghệ ThôngTin
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 nh au",
đố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 k hô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 q uả 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.
Trang82
Lý thuyếtÔtômát &NNHT- KhoaCông NghệThôngTin
Đị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 b iệ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 83
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.
Trang84
LýthuyếtÔtômát &NNHT -Khoa CôngNghệ ThôngTin
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.
Trang85
Lý thuyếtÔtômát &NNHT- KhoaCông NghệThôngTin
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 h ay
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 86
LýthuyếtÔtômát& NNHT-Khoa CôngNghệ ThôngTin
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.
Trang87
Lý thuyếtÔtômát&NNHT -KhoaCông NghệThôngTin
Thủ tục đánh dấu – mark (tt)
Bổ đề 2
Khi băng qua vòng lặp trong bướclầ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.
Trang88
Lýthuyết Ôtômát& NNHT-Khoa Công NghệThôngTin
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 p hân
biệt được, gọi là {qi, qj, … , qk}, {ql, qm, … , qn}, ...
M =
Q, Σ,δ,q0, F