ĐAI H C VINHỌ
KHOA CNTT
Biên so n: ạHOÀNG DANH LONG
K50-CNTT
Chương II
ÔTÔMÁT HỮU HẠN VÀ BIỂU
THỨC CHÍNH QUY
I. ÔTÔMÁT HỮU HẠN (FA : Finite Automata)
T i m i th i đi m, h th ng có th đ c xác đ nh ạ ỗ ờ ể ệ ố ể ượ ị ở
m t trong s ộ ố h u h n ữ ạ tr ng tháiạ (states).
M i tr ng thái c a h th ng t i m i th i đi m s thay ỗ ạ ủ ệ ố ạ ỗ ờ ể ẽ
đ i tùy thu c vào ổ ộ INPUT
Ôtômát h u h n (FA) đ c chia thành 2 lo i: ữ ạ ượ ạ đ n ơ
đ nhị (DFA) và không đ n đ nhơ ị (NFA).
DFA có kh năng nh n d ng ngôn ng d dàng h n ả ậ ạ ữ ễ ơ
NFA, nh ng thay vào đó thông th ng kích th c ư ườ ướ
c a nó l i l n h n so v i ôtômát h u h n không đ n ủ ạ ớ ơ ớ ữ ạ ơ
đ nh t ng đ ng.ị ươ ươ
Ôtômát h u h n đ n đ nh - DFA ữ ạ ơ ị
(Deterministic Finite Automata)
M t cách hình th c ta đ nh nghĩa ôtômát h u h n ộ ứ ị ữ ạ
đ n đ nh là b g m năm thành ph n ơ ị ộ ồ ầ (Q, Σ, δ, q0, F),
trong đó :
•Q là t p h p h u h n các tr ng thái.ậ ợ ữ ạ ạ
∀Σ là b ch cái h u h n.ộ ữ ữ ạ
∀δ là hàm chuy n ánh x t ể ạ ừ Q × Σ → Q, t c là ứδ(q,
a) là m t tr ng thái đ c cho b i phép chuy n t ộ ạ ượ ở ể ừ
tr ng thái ạq trên ký hi u nh p ệ ậ a.
•q0 ∈ Q là tr ng thái b t đ uạ ắ ầ
•F ⊆ Q là t p các tr ng thái k t thúcậ ạ ế
S đ chuy nơ ồ ể
M t đ th có h ng, g i là ộ ồ ị ướ ọ
s đ chuy n ơ ồ ể (transition
diagram) t ng ng v i ươ ứ ớ
m t DFA nh sau: ộ ư
Các đ nh c a đ thỉ ủ ồ ị là các
tr ng tháiạ c a DFA; ủ
N u có m t đ ng chuy n ế ộ ườ ể
t tr ng thái ừ ạ q đ n tr ng ế ạ
thái p trên input a thì có
m t cung nhãn ộa t đ nh ừ ỉ q
đ n đ nh ế ỉ p trong s đ ơ ồ
chuy n. ể
Tr ng thái kh i đ u qạ ở ầ 0
nhãn "Start".Các tr ng thái ạ
k t thúc trong F đ c ch ế ượ ỉ
ra b ng ằhai vòng tròn.
Minh họa
DFA đang tr ng thái ở ạ q đ c ký hi u nh p ọ ệ ậ a trên băng, chuy n sang ể
tr ng thái đ c xác đ nh b i hàm chuy n ạ ượ ị ở ể δ(q, a), r i d ch đ u đ c ồ ị ầ ọ
sang ph i m t ký t . ả ộ ự
N u ếδ(q, a) chuy n đ n m t trong nh ng tr ng thái k t thúc thì DFA ể ế ộ ữ ạ ế
ch p nh n chu i đ c vi t trên băng input phía tr c đ u đ c, ấ ậ ỗ ượ ế ướ ầ ọ
nh ng không bao g m ký t t i v trí đ u đ c v a d ch chuy n đ n.ư ồ ự ạ ị ầ ọ ừ ị ể ế
Trong tr ng h p đ u đ c đã d ch đ n cu i chu i trên băng và DFA ườ ợ ầ ọ ị ế ố ỗ
chuy n đ n tr ng thái k t thúc, thì DFA m i ch p nh n toàn b ể ế ạ ế ớ ấ ậ ộ
chu i trên băng.ỗ