Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 12 Nguyễn Đức Thuần

Ch-ơng II

ôtômat hữu hạn
đoán nhận Ngôn ngữ chính quy

1.ôtômat hữu hạn
(Finite automata - Fa)

Ôtômát hữu hạn có thể xem nh- "máy trừu t-ợng". Chúng là một công cụ đoán
nhận một lớp các ngôn ngữ đơn giản gọi là chính qui.

2.1 ôtômát hữu hạn

2.1 Định nghĩa:

Ôtômát hữu hạn là bộ M = <ồ,Q,d, q
0
,F>, trong đó:
ồ : là tập hữu hạn khác rỗng các ký hiệu vào.
Q : là tập hữu hạn khác rỗng các trạng thái.
q
0
: là trạng thái đầu (q
0
ẻ Q)
F : là tập các trạng thái kết thúc (FQ)
d : đ-ợc gọi là hàm chuyển có dạng :

x
n-2

x
n-1

x
n
Bộ điều khiển Hình 2.1 Các bộ phận của ôtômat hữu hạn

Khi bắt đầu làm việc máy ở trạng thái đầu q
0
và đầu đọc đang nhìn vào ô có ký
hiệu x
1
. Tiếp theo, máy chuyển từ trạng thái q
0
d-ới tác động của ký hiệu vào x
1
về trạng
q
Ng Duc Thuan

với trạng thái của
máy là q
n-1
= d(q
0
, x
1
x
2
x
n-1
).

Hàm chuyển lại đ-a máy từ trạng thái q
n-1
d-ới tác động của x
n
về trạng thái q
n
=
d(q
n-1
, x
n
) = d(q
0
, x
1
x
2

2
x
n

q
1

q
2
q
3
q
k

d(q
1
, x
1
)
d(q
2
, x
1
)
d(q
3
, x

)
d(q
1
, x
n
)
d(q
2
, x
n
)
d(q
3
, x
n
) d(q
k
, x
n
)



q
3

q
0
q
3
q
2
q
0

q
3
q
3

Ví dụ 2 : Giả sử xét các xâu w
1
= 10110, w
2
= 10011. Hỏi rằng ôtômat M có đoán
nhận các xâu đó hay không?

Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 14 Nguyễn Đức Thuần

a. Dãy trạng thái của ôtômat M khi cho w
1

w
1
= 1 0 0 1 1 q
0
đ q
2
đ q
0
đ q
1
đ q
0
đ q
2
ẽ F Do đó, ôtômat M không đoán nhận xâu w
2
= 10011.

Từ các ví dụ trên ta thấy quá trình đoán nhận một xâu nào đó đối với ôtômat M
đơn định là quá trình biến đổi trạng thái cuối cùng của ôtômat có phải là trạng thái kết
thúc hay không.

Thuật toán mô phỏng ôtômat hữu hạn đoán nhận xâu vào của ôtômat đơn định nh-
sau:

, q
1
, q
2
, q
3
}, q
0
là trạng thái đầu, F = {q
2
, q
4
} là tập các
trạng thái kết thúc.

Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 15 Nguyễn Đức Thuần

Hàm chuyển d : Qxồ đ 2
Q
đ-ợc cho ở bảng sau:

Trạng thái

Ký hiệu vào
0 1
q
0
{q
0,

4
q
3

Khi cho xâu vào là w = 01001 thì đối với máy M ta có cây đoán nhận xâu nh- sau:

Trong cây trên có một đ-ờng đi từ q
0
đến q
4
ẻ F nên xâu w
1
= 01001 là xâu đoán
nhận đ-ợc bởi máy M.


q
1
q
2
q
3

q
2

q
3

q
0
q
1
q
1
q
0

q
3
q
2 q
0


q
4

q
4

ặ

ặ

ặ

Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 16 Nguyễn Đức Thuần

Lúc này, đồ thị chuyển sẽ có dạng nh- sau:
Chú ý : Định nghĩa ôtômat hữu hạn đơn định & không đơn định bằng hệ viết lại:

L = {w ẵ w ẻồ* và q
0
w

p với p ẻ F}.

2.3 sự t>ơng đ>ơng giữa Ôtômat hữu hạn đơn định và Ôtômat
hữu hạn không đơn định:

Theo định nghĩa của Ôtômat đơn định M và không đơn định N , nếu ký hiệu các
lớp ngôn ngữ đ-ợc đoán nhận bởi M và N t-ơng ứng là L(M) và L(N). Ta có định lý sau:

2.3.1 Định lý :
Lớp ngôn ngữ đoán nhận bởi ôtômát đơn định trùng với lớp ngôn ngữ đoán nhận
đ-ợc bởi ôtômat không đơn định.

Chứng minh:
Theo định nghĩa của ôtômat đơn định & ôtômát không đơn định, dễ dàng nhận
thấy: lớp ngôn ngữ đoán nhận đ-ợc bởi ôtômat đơn định là lớp con của lớp ngôn ngữ đoán
nhận đ-ợc ôtômát không đơn định. ( L(M) L(N) ).

Ta chứng minh L(N) L(M). Thật vậy, giả sử p ẻồ
*
đoán nhận đ-ợc bởi ôtômát
không đơn định N = <ồ,Q,d,s
0
,F> hay p ẻ L(N).

Ta xây dựng ôtômát đơn định M = <ồ',Q',d',q
0


0

1

1

Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 17 Nguyễn Đức Thuần

"UẻQ, "xẻồ thì d'(U,x) =
qUẻ
U
d(q,x).
Với M định nghĩa nh- trên, thì ta có p ẻL(M) hay L(N) L(M). (đ.p.c.m)
Ví dụ 5: Cho Ôtômat không đơn định N = <ồ,Q,d, s
0
,F>, với ồ = {a,b}, Q ={s
0,
s
1
}, F = {s
1
}, hàm chuyển đ-ợc xác định : d: Qxồ đ 2
Q
đ-ợc cho bởi bảng chuyển sau:

Trạng thái Ký hiệu vào
a b
s

4
} ở đây q
1
=ặ, q
2
= {s
0
},
q
3
= {s
1
}, q
4
= {s
0
, s
1
} còn F' = {q
3
, q
4
}.
Hàm chuyển d' cho d-ới bảng sau:

Trạng thái Ký hiệu vào
a b
q
1
- Đồ thị chuyển của Ôtômát đơn định M t-ơng ứng là:

q
1

q
0

0,1

1

0

1

{q

2. Ôtômat hữu hạn và văn phạm chính qui:

2.4.1 Định lý : Nếu L là ngôn ngữ chính qui thì tồn tại một ôtômat hữu hạn không
đơn định chấp nhận L.

Chứng minh :
Giả sử L đ-ợc sinh ra bởi văn phạm chính qui G = <ồ, D,S,P>. Ta xây dựng
ôtômat hữu hạn không đơn định N = < ồ' ,Q, d, q
0
, F>, trong đó:

- ồ' = ồ, Q= D ẩ {E}, E ẽ ồẩD;
- q
0
= S
- d(E, a) = ặ, "a ẻồ
- d(B,a) chứa tất cả các trạng thái D sao cho B đaDẻP, thêm vào :
d(B,a) chứa E nếu Bđa ẻP.
-Nếu có S đe : d(B,a)={S}
F
E
ES
=
ỡ
ớ
ợ
{},
{,},

Ta chứng minh L(N) = L(G)=L.

1
a
2
a
k
.

ở đây A
1
, A
2
, , A
k-1
ẻD và do đó tồn tại một dãy qui tắc của p:
S đ a
1
A
1
; A
1
đ a
2
A
2
; ; A
k-1
đ a
k
.


d(S,e) ={S} nên e ẻ L(N).

* L(N)

L(G)

Ng-ợc lại, Lấy w = a
1
a
2
a
k
ẻ L(N) và giả sử eạw, lúc đó tồn tại một dãy trạng
thái S, A
1
,

A
2
, ,A
k
, E sao cho:

A
1
ẻd(S,a
1
); A
2
ẻd(A

.
Và do đó có dãy suy dẫn:
nếu P không chứa S đe
ng-ợc lại
Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 19 Nguyễn Đức Thuần

S a
1
A
1
a
1
a
2
A
2
a
1
a
2
a
k-1
A
k-1
a
1
a
2
a

i
, b
j
, i,j 0 }

2.4.2 Định lý : Nếu ngôn ngữ L đ-ợc đoán nhận bởi 1 ôtômát hữu hạn đơn định
thì L là 1 ngôn ngữ chính qui.

Chứng minh :
Cho M = < ồ,Q, d, q
0
, F> là ôtômát hữu hạn đơn định chấp nhận L. Ta xây
dựng văn phạm chính qui sau :
G = <ồ, D,S,P>. ở đây:
S = q
0
;
D = Q;
P đ-ợc xác định nh- sau:
- Nếu có d(q, a) = p thì P chứa q đ ap
- Nếu có d(q, a) = p ẻF thì P chứa q đ a.

Ta sẽ chứng minh : L(G) = L - {e}

* Ta chứng minh L - {
e
}

L(G):
S

1

d(p
1
, a
1
) = p
2

. . . . . . . . . .
d(p
k-1
, a
k
) = p
k
ẻ F, và do đó trong P có các qui tắc:
q
0
đ a
1
p
1
, p
1
đ a
2
p
2
, , p


* Ta chứng minh L(G)

L - {
e
}:
Ng-ợc lại lấy w = a
1
a
2
a
k
ẻ L(G), lúc đó tồn tại dãy suy dẫn:
q
0
a
1
p
1
a
1
a
2
p
2
a
1
a
2
a

1
, a
2
)
. . . . . . . . . .
p
k
=d(p
k-1
, a
k
)
và p
k
ẻ F, do đó w ẻ L(M)= L

Trong tr-ờng hợp eẻL, theo ch-ơng 1, ta có thể xây dựng đ-ợc G' sao cho:
L(G') = L(G) ẩ {e} = L .(đ.p.c.m)

Chú ý : L ngôn ngữ chính qui ị Ôtômát hữu hạn không đơn định

í ò

Ôtômát hữu hạn đơn định

2.4.3 Định lý : ( Định lý Pumping cho ngôn ngữ chính qui) Giả sử L là 1 ngôn ngữ
vô hạn đ-ợc đoán nhận bởi 1 ôtômat hữ- hạn đơn định thì tồn tại 1 số tự nhiên m sao cho
"w ẻL có ẵwẵm có thể phân tích d-ới dạng w=xyz, ở đây ẵxyẵÊ m, ẵyẵ 1 và "i0,
xy
i

(vì số trạng thái tham gia đoán nhận lớn hơn số trạng thái có đ-ợc của ôtômat nên có ít
nhất 1 trạng thái lặp)
Gọi x, y, z lần l-ợt là các xâu con của w mà:
d*(q
0
, x) = q
r

d*(q
r
, y) = q
r
{y là xâu con bé nhất của w thoả d*(q
r
, y) = q
r
}
d*(q
r
, z) = q
f

Ta có thể nhận thấy
Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 21 Nguyễn Đức Thuần

ẵxyẵÊ m=n+1, ẵyẵ 1
Từ đó suy ra:
d*(q
0

b
n
, n > 0}, G = <{a,b}, {S}, {Sđ aSbẵab}>
L = L(G)
Nếu L là đ-ợc đoán nhận bởi 1 ôtômat hữu hạn đơn định ịL là ngôn ngữ chính quiịL
thoả định lý pumping:

w
i
= a
n
b
n
= xy
i
z , ẵxyẵÊ m, ẵyẵ=k 1

Chọn n > m ị y chỉ chứa toàn bộ ký tự a. Khia i=0, w
i
= a
n-k
b
n
ẽL ( mâu thuẩn).
Vì vậy L không là ngôn ngữ chính qui.

Chú ý : Lớp ngôn ngữ chính qui và lớp nn PNC là phân biệt.

2.4.5 Một vài ví dụ minh hoạ:


m
a
m
ẽ L (mâu thuẩn).
ị Vậy L không là ngôn ngữ chính qui.

b. Cho ồ = {a, b}. Chứng minh rằng
L = { w ẻồ * : n
a
(w) < n
b
(w)} không là ngôn ngữ chính qui.
Giả sử L là 1 ngôn ngữ chính qui ị thoả định lý pumping ị $m, ẵwẵ m ị
w = xy
i
z, ẵxyẵÊ m, ẵyẵ 1. Chọn n = m, và m đủ lớn
w = a a b b ị w
i
= xy
i
z ẻ L

x y z
Chọn i 2 ị xy
i
z ẻ L ị n
a
(w
i
) > n


2.5.2 Định lý : Với w ẻồ*, thì {w} là NNCQ.
Chứng minh : Nếu w = e thì mệnh đề đã đ-ợc chứng minh.
- Nếu không w = a
0
a
1
a
n
trong đó a
0
, a
1
, , a
n
ẻồ, n 0
Xét Ôtômát không đơn định M = < ồ, {q
0
, q
1
, , q
n+1
}, d, q
0
, {q
n+1
}>, trong đó:
d(q
i
, a

, F}
Để phân tích các bộ phận hợp thành L(M) ta đ-a ra định nghĩa sau:
Gọi R
ij
k
là tập mọi xâu dẫn trong M từ trạng thái q
i
đến trạng thái q
j
mà
không đi qua một trạng thái q
l
nào đó, với l > k ( l-u ý là i,j có thể > k).
Nói cách khác là :

R
ij
k
= { w ẵ q
i
w

q
j
và với mọi tiền tố v của w, v ạw, vạe thì q
i
v

q
l

ij
k
thì trong suy dẫn
q
i
w q
j
:
(1) hoặc là trong M suy dẫn trên không đi qua trạng thái q
k
, tức là w ẻ
1-k
ij
R .
(2) hoặc là M có (một số lần) đi qua q
k
. Nh- vậy w bị chia cắt thành nhiều đoạn:
Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 23 Nguyễn Đức Thuần

- một tiền tố thuộc
1-k
ik
R đ-a M từ q
i
đến q
k
lần đầu tiên.
- tiếp đến một số (có thể là không) các xâu con thuộc R
kk

( R
kk
k -1
)* R
kj
k -1 R
i j
0
=
ù
ợ
ù
ớ
ỡ
ẩ=
=
}{}),(/{
}),(/{
ed
d
ji
ji
qaqa
qaqa

Ta thấy R
i j

nếu không thể có nhầm lẫn xảy ra, thì ta dùng r vừa để chỉ biểu thức chính qui, vừa để chỉ
tập hợp do nó chỉ định.

Ví dụ 8: - 00 là một biểu thức chính qui, chỉ định tập {00}
- Biểu thức (0+1)* chỉ định tập mọi xâu 0 và 1. ({0,1}*)
- Từ đó biểu thức (0+1)* 00(0+1)* chỉ định tập mọi xâu 0 và 1 có chứa ít
nhất một cặp 0 liền nhau.
- Biểu thức chính qui (1+10)* chỉ định tập mọi xâu 0 và 1, có ký tự 1 ở đầu
và không có 2 ký tự 0 liên tiếp. Để chứng minh điều đó, đầu tiên có thể qui nạp theo i
rằng (1+10)
i
không chứa 2 ký tự 0 liên tiếp. Sau đó chứng minh ng-ợc lại rằng cho 1 xâu
có ký tự 1 ở đầu, và không chứa 2 ký tự 0 liên tiếp, ta luôn có thể cắt xâu đó thành các xâu
nếu iạj
nếu i=j
Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 24 Nguyễn Đức Thuần

con 0 hay 10. Chẳng hạn, 1101011 đ-ợc cắt thành 1-10-10-1-1. Điều đó, chứng tỏ xâu
trên thuộc (1+10)
i
, trong đó i là số các ký tự 1.
- Biểu thức chính qui (0+e) (1+10)* chỉ định tập mọi xâu 0 và 1 không
chứa hai ký tự 0 liên tiếp.
- Biểu thức (0+1)*011 chỉ định tập mọi xâu 0,1 kết thúc bởi 011.
- Còn 0*1*2* chỉ định tập mọi xâu gồm một số ký tự 0, tiếp đến một số ký
tự 1, rồi đến một số ký tự 2.
- Biểu thức 00*11*22* chỉ định tập các xâu trong 0*1*2* trong đó 0,1,2
đều có mặt. Biểu thức đó th-ờng đ-ợc viết tắt là 0
+


Ôtômát này chấp nhận ngôn ngữ đ-ợc ký hiệu bởi 0+1
d.
Ôtômát này chấp nhận ngôn ngữ đ-ợc ký hiệu bởi biểu thức 220*1

1

s
0

s
1

0

s
2

s
1


s
2

Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 25 Nguyễn Đức Thuần

e. Ôtômát này chấp nhận ngôn ngữ đ-ợc ký hiệu bởi (220*1)*

f.
Ôtômat này chấp nhận ngôn ngữ đ-ợc ký hiệu 01*+02
3

S
0

S
1

0

0

S
2

S
1

S
0

2

2

1

0

S

0

S
3

S
2

0

1

2

1

2

0

Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 26 Nguyễn Đức Thuần

q
1
q
0

q
1
b. Ôtômat đoán nhận e
hoặc
c. Ôtômat đoán nhận {a}

d. Ôtômat đoán nhận r
1
+r
2 e. Ôtômat đoán nhận r
1
*

f. Ôtômat đoán nhận (a+b)*
hoặc

2

0

0

0

1

2

1

2

0

1

q
1
q
0

a
q
0
q
1

b(a+bb)*

Xét (a+bb)* :
Thay bb bởi

Vậy b(a+bb)* là :
2. Tìm Ôtômat đoán nhận L
1
= {awa : wẻ{a,b}*}
2.6.3 Các tính chất đại số của biểu thức chính qui:

Ta có thể chứng minh đ-ợc rằng : Cho r,s,t là các biểu thức chính qui, thì ta có các

1

q
2
b
1

q
1
q
2
Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 28 Nguyễn Đức Thuần 2.6.3 Bổ đề : Với mọi tập hữu hạn L ồ*, đều tồn tại một BTCQ mà tập nó chỉ
định là L.

2.6.4 Định lý : Một ngôn ngữ L đ-ợc chỉ định bởi một BTCQ khi và chỉ khi nó
đ-ợc đoán nhận bởi một Ôtômát hữu hạn.

Nói tóm lại : Các ngôn ngữ do BTCQ chỉ định và lớp các ngôn ngữ do Ôtômát h-u
hạn đoán nhận là một. Đó là lớp các NNCQ. 5. Cực tiểu hóa các Ôtômat hữu hạn

2.7.1 Định nghĩa : Cho M = < ồ,Q, d, q
0
, F> là Ôtômát hữu hạn đơn định, và q

1

k
q
2
, nếu không tồn tại xâu u, với
ẵuẵÊ k, sao cho q
1
và q
2
phân biệt.

- Các trạng thái q
1
và q
2
là không phân biệt, ta viết q
1
q
2
, nếu chúng là k-không
phân biệt, "k0 .
- Ôtômát M đ-ợc gọi làcực tiểu nếu trong Q không tồn tại các trạng thái không
đạt tới đ-ợc và không tồn tại bất cứ 2 trạng thái không phân biệt nhau.

Ví dụ 11: Xét Ôtômát đ-ọc biểu diễn bằng đồ thị chuyển sau:


2
là không phân biệt khi và chỉ khi chúng là (n-2)-không phân
biệt.
Chứng minh : Điều kiện cần là tầm th-ờng. Điều kiện đủ là tầm th-ờng khi F có
0 hoặc n trạng thái.
q
3

q
1

q
0

q
2

q
4

q
5

Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 29 Nguyễn Đức Thuần Ta nhận thấy rằng, với các trạng thái bất kỳ q
1
và q

0
chia Q thành 2 lớp F và Q-F.
Nếu
k+1
ạ
k
thì
k+1
là mịn hơn, bởi vì nó chứa nhiều hơn ít nhất một lớp
t-ơng đ-ơng. Vì thế không có tập nào từ các tập F, Q-F chứa nhiều hơn n-1 trạng thái,
không thể tạo nên nhiều hơn lần l-ợt n-2 quan hệ mịn hơn
0
.
Nếu
k+1
=
k
với một k nào đó thì
k
=
k+1
=
k+2
=
k+3
=
Vì thế là quan hệ đầu tiên
k
sao cho
k

=

k+1
, Gọi

=

k 3. Tạo Ôtômát hữu hạn đơn định M' = <
ồ
,Q',
d
', q
0
', F'> :

a. Q' là tập các lớp t-ơng đ-ơng của quan hệ

.
b. Ký hiệu [q] là lớp t-ơng đ-ơng chứa trạng thái q. Sau đó thiết lập: d
'([q], a) = [p], nếu
d
'(q,a) = p;
c. q
0

4

q
0

q
6

q
1

q
3

q
5

q
7

0

0

1

1

1


1
: {q
0
, q
4
},{q
2
, q
7
},{q
3
, q
5
}

2
: {q
0
, q
4
},{q
2
, q
7
},{q
3
, q
5
}


]
[q
3
] [q
3
] [q
2
] q
0
' = [q
0
]
F = {[q
0
]}.

2.7.4 Định lý : Ôtômát M' đ-ợc tạo ra trên cơ sở thuật toán 2.7.3 có số trạng thái ít
nhát trong tất cả các Ôtômát đặc tả ngôn ngữ L(M).

Chứng minh : Ta giả sử là khẳng định trên không đúng, nghĩa là tồn tại một
Ôtômát M'' có số trạng thái ít hơn của M', nh-ng L(M'') = L(M').
Theo b-ớc 1 của thuật toán 2.7.3 tất cả trạng thái của M' là đạt tới đ-ợc. Vì M'' có
ít trạng thái hơn M' nên tồn tại các xâu u,v từ trạng thái q
0
' dẫn đến 2 trạng thái khác nhau,
nh-ng lại dẫn q
0

(q
2
'', e).

Bởi vì các xâu u,v suy dẫn trong M đến các trạng thái khác nhau ta ký hiệu là p,r.
Nghĩa là tồn tại xâu z, sao cho chỉ một trong các xâu uz hoặc vz thuộc L(M). Nh-ng các
xâu uz và vz lại phải dẫn trong Ôtômát M'' đến cùng một trạng thái ký hiệu là s, phải thỏa
mãn (q
2
'',z) (s,e). Nh-ng điều đó có nghĩa là, một trong các xâu uz, vz không thể thuộc
L(M'') mâu thuẩn với giả thiết L(M') =L(M''). (đ.p.c.m)