Chương 2:
ÔTÔMÁT HỮU HẠN VÀ BIỂU
THỨC CHÍNH QUY
Nội dung
I. Biểu thức chính quy
II. Ôtômat hữu hạn

Ôtômat hữu hạn tiền định

Ôtômat hữu hạn không tiền định

Sự tương đương giữa ô tô mát hữu hạn tiền định và
không tiền định
I. Sự tương đương giữa ô tô mát và biểu thức chính quy
II. Văn phạm chính quy
III. Các ngôn ngữ chính quy

Các tính chất đóng của các ngôn ngữ chính quy

Định lý “đùn”
I. Biểu thức chính quy (BTCQ)

Định nghĩa: Cho bộ chữ ∑

φ là một BTCQ

ε là một BTCQ

∀a∈∑ thì a là một BTCQ

α,β là các BTCQ(α+β), (α.β), (α*) là các BTCQ

có hai
con 0 liên tiếp}
Tính chất của BTCQ

Cho r, s, t là các BTCQ:
(1) r+s=s+r
(2) r+(s+t)=(r+s)+t
(3) r(s+t)=rs+rt
(4) rε= εr=r
(5) r+φ=r
(6) (ε+r)*=r*
(7) (r*)*=r*
(8) r+r=r
(9) r(st)=(rs)t
(10) (r+s)t=rt+st
(11) φr=rφ= φ
(12) φ*= ε
(13) r+r*=r*
(14) (r*s*)*=(r+s)*
Ví dụ

Hãy mô tả bằng lời các tập hợp chỉ định bởi các biểu
thức chính quy sau:

(11+0)*(00+1)*

(1+01+001)*(ε+0+00)*

[00+11+(01+10)(00+11)*(01+10)]*
Cấu tạo của OHT

Cái điều khiển
Đầu đọc
Hình. Ôtômát hữu hạn tiền định
Băng vào
Nguyên lý hoạt động

Ban đầu: OHT ở trạng thái đầu, đầu đọc trỏ vào kí hiệu đầu tiên
của xâu vào

Lặp:

ÔHT đọc kí hiệu trên băng, xác định trạng thái tiếp theo dựa
vào hàm dịch chuyển, đẩy đầu đọc sang phải một ô

OHT dừng khi đọc hết xâu vào, nếu trạng thái cuối là trạng
thái thừa nhận thì xâu và được thừa nhận (thuộc ngôn ngữ
mà ôtômát mô tả)
Ôtômát hữu hạn tiền định

Ví dụ: Cho ôtômát tiền
định M, trong đó:

Bộ chữ vào ∑={0,1}

Q={q
0
, q
1
, q
2

0
q
3
q
3
q
1
q
2
Định nghĩa OHT

Định nghĩa: OHT là một bộ năm M=(∑,Q,δ,q
0
,F)
trong đó:

∑ - tập hữu hạn các kí hiệu (bộ chữ vào)

Q – tập hữu hạn các trạng thái, ∑∩Q=φ

δ:Q× ∑Q là hàm dịch chuyển

q
0
∈Q là trạng thái đầu

F⊆Q là các trạng thái thừa nhận (trạng thái cuối)
Ôtômát tiền định

Hệ viết lại ngầm định của ôtômát M là W=(V,P), trong

Ví dụ: M=(∑,Q,δ,q
0
,F)

∑={0,1}; Q={q
0
, q
1
, q
2
}; F={q
1
}

δ được cho bởi:
δ(q
0
, 0)=q
0
, δ(q
0
, 1)=q
1

δ(q
1
, 0)=q
0
, δ(q
1


F⊆Q là các trạng thái thừa (trạng thái cuối)
Ôtômát hữu hạn không tiền định

Ví dụ: Sơ đồ chuyển trạng thái của một OHK
Ôtômát hữu hạn không tiền định

OHK khác OHT:

Từ một trạng thái gặp một kí hiệu được đọc vào có
thể chuyển sang một số trạng thái tiếp theo (hàm
chuyển là hàm đa trị)

Từ một trạng thái có thể không cần kí hiệu vào OHK
cũng chuyển trạng thái (dịch chuyển ε)
Sự tương đương giữa OHT và OHK

Ta gọi:

L(OHT) là lớp các ngôn ngữ được đoán nhận bởi
OHT

L(OHK) là lớp các ngôn ngữ được đoán nhận bởi
OHK

Ta chứng minh: L(OHT)=L(OHK) (tức là ngôn ngữ L
được đoán nhận bởi OHT  L cũng được đoán nhận
bởi một OHK)
Sự tương đương giữa OHT và OHK



Cho OHK M= (∑, Q, δ,

q
0
, F), dựng OH
M’=(∑’, Q’, δ’,

q
0
’, F’) không còn dc-ε

E(s)={q∈Q|s=>*q nhờ toàn dc - ε } (∀s∈Q, s∈E(s))

∑’= ∑; Q’=Q; q
0
’= q
0

δ’: p∈δ’(q,a)∃r∈E(q) sao cho p∈δ(r,a)

F’=F∪{s ∈Q|E(s)∩F≠φ}
Loại bỏ dịch chuyển ε

Ví dụ: cho OHK có sơ đồ dịch chuyển sau:

Tìm OH tương đương với OHK đã cho
Ví dụ

Loại bỏ dịch chuyển-ε: