Chương

6

ÔTÔMAT HỮU HẠN ĐOÁN NHẬN BIỂU THỨC CHỈNH QUY
|1. ÔTÔMAT HỮU HẠN (FINITE AUTOMATA - FA)
Ô t ô m a t hữu h ạ n có t h ể xem n h ư " m á y t r ừ u tượng" để
đ o á n n h ậ n ngôn ngữ. C h ú n g ta sẽ t h ấ y r ằ n g láp n g ô n ngữ điíỢc
đ o á n n h ậ n bởi ô t ô m a t h ữ u h ạ n là k h á đơn g i ộ n . đó c h í n h là lốp
n g ô n ngữ c h í n h quỵ do các v ă n p h ạ m c h í n h quy sinh ra.
1.1. D i n h n g h ĩ a ô t ô m a t h ữ u h ạ n
Đinh

nghĩa

ĩ:

Ô t ô m a t hữu h ạ n là bộ M = < I . Q. 5. q„. F>.
trong dó:
ì - là t ậ p hợp hữu h ạ n k h á c rỗng các ký h i ệ u v à o .
Q- là t ậ p hợp hữu h ạ n k h á c rỗng các t r ạ n g t h á i .
q,j e Q được gọi là t r ạ n g t h á i ban đ ầ u .
F c Q được gọi là t ậ p các t r ạ n g t h á i két t h ú c .
5- được gọi là h à m chuyên có dạng;
1.

N ê n h à m chuyển là á n h xạ 5 : Q X ì —> Q. k h i đó M được
gọi

là


sau:

Xâu vào 0)

X,

x

...

2

x _!

x

n

3

n

n

t
Qo->

Khi bắt đầu làm việc máy ở trạng thái đầu q và đầu đọc
0


0

2

ôtômat dừng l ạ i . Nếu q„ 6 F thì ta nói rằng ôtômat đã đoán
nhận xâu co. Trong trường hợp ngược lại thì nói rằng ôtômat
không đoản nhận xâu co.
Tập L(M) ={co/ co e ì* mà 5(q , co) e F} được gọi là ngôn ngữ
0

được đoán nhận bởi ôtômat M. Tập trạng thái Q trong quá
trình tính toán được coi như là bộ nhớ của một ôtômat. Vì Q là
hữu hạn nên M được gọi là ôtômat hữu hạn.
241


1.2. Phương pháp biêu d i ê n ô t ô m a t hữu hạn
Cho ôtômat thực chất là cho hàm chuyển của nó. Hàm
chuyển có thể cho đuối dạng bảng chuyển, hoặc cho đuối dạng
đồ thị.
a) Phương pháp
Trạng
thái

cho bảng

chuyên:

Ký hiệu vào



3

S(q . X,)

S(q , x

Qk

5(q , X,)

ỗ(q . x )

-ỉ

2

Xi)

2

3

3

k

k

... S(q,, x„)

Ký hiệu vào

Trạng
thái

0

1

q.j

Q2

Qi

Qo

q.ì

q.

242

q

2

q

3

Ì

q - » q, -> q,, ->
0

q-2

Ì

-> q -> q. ->
3

q,.i

Hay quá trình trên tường đương với diễn đạt sau:
S(q , 110101)

= Ỗ(ô(q ,. 1), 10101) = S(q„ 10101) =

0

L

5(5(q,. 1). 0101) = 5(q„. 0101) = 5(5(q„. 0).101) = 5(q. .101)
= 5(ỗ(q . 1). OI) = ô(q . OI) = S(ô(q . 0). 1)
= 5(q,. 1) = q„ £ F.
2

2


q-2

qo

q.3

q

q

q;i

3

3

3

243


Giả sử xét các xâu co, = 10110. co = no, C0 = 10011. Hỏi
2

3

rằng ôtômat M có đoán nhận các xâu đó hav không ?
a. Dãy trạng thái của ôtômat M khi cho CO] vào là:

0


0

t

t

t

q , -» q -> q -> q e F
:

2

3

và ôtômat cĩing đoán nhận xâu C 0

3

2

=

no.

c. Vối xâu vào Cù 3 = 10011. Ta lập dãy trạng thái của
ôtômat M đối vói co như sau:
3


- Một xâu co. kết thúc b
i ký hiệu hết File là eof.
244


- M ộ t ô t ô m a t h ữ u h ạ n M với t r ạ n g t h á i ban đ ầ u q,i và t ậ p
t r ạ n g t h á i k é t t h ú c là F.
" Đ ú n g " n ế u M đ o á n n h ậ n x â u co.

Đ ầ u ra:

"Sai" n ế u M k h ô n g đ o á n n h ậ n x â u co.
Thuật toán:
Begin
S:= q ;
0

C:=ký hiệu tiếp theo ;
While c eof do
begin
S:= 5(S. C);
C:= ký hiệu tiếp theo;
end;
if s in F return (True)
else return (False);
End.

Ví dụ 3: Cho ô t ô m a t k h ô n g đơn định M = < I . Q. 5. q„. F>
v ố i ì ={0.1 J. Q-{q,,. q,. q . q.í). q.-i là t r ạ n g t h á i ban đ ầ u ,
F - ÍQ2- q-)} là t ậ p hợp t r ạ n g t h á i k é t t h ú c .


q
0

Q4

q.3

íq... Q1 ỉ
2

2

245


Sau đ â y là q u á t r ì n h đ o á n n h ậ n một x â u v à o của m á y M .
Vì đ ố i với ô t ô m a t k h ô n g đơn định t h ì h à m chuyển 5 k h i
m á y ở t r ạ n g t h á i q và t í n h i ệ u a là ô(q,a) c Q n ê n sẽ x u ấ t h i ệ n
t ì n h t r ạ n g rẽ n h á n h . Đ ể cho t i ệ n ta có t h ể l ậ p d ã y t r ạ n g t h á i
của m á y ứng v ố i x â u v à o d ư ớ i d ạ n g cây m à gốc của nó là t r ạ n g
t h á i ban đ ầ u q„. Trong c â y n à y n ế u có m ộ t đường đi t ừ gốc q
đ ế n m ộ t lá chứa t r ạ n g t h á i k ế t t h ú c t h ì ta nói r ữ n g m á y M đoán
n h ậ n x â u vào đ a n g xét. Ngược l ạ i , n ê u k h ô n g có m ộ t lá n à o
trong cây chứa t r ạ n g t h á i k ế t t h ú c t h ì ta nói M k h ô n g đ o á n
n h ậ n x â u vào đó.
ụ

C h ẳ n g h ạ n k h i cho x â u v à o (0, = 01001 đ ố i v ố i m á y M t h ì
ta có cây đ o á n n h ậ n x â u co ị n h ư sau:

qj } đối vối ôtômat không đơn định

qj có k cung gán cùng một nhãn a.

2

Đỉnh vào của đồ thị chuyển là đỉnh ứng vói trạng thái ban
đầu q,,. Các đỉnh có các trạng thái k ế t thúc được khoanh vòng
tròn hai lần. Các đỉnh còn l ạ i khoanh bởi một vòng tròn.
Ví dụ 4: Cho ôtômat đơn định M = < I , Q, 5, q , F>,
ì = {0.1}, Q = {q . q,. q . q }. F = {q }. h à m chuyển 5: Q X ì -> Q
được cho dưới dạng đồ thì chuyển n h ư sau:
0

0

2

3

0

Ì
Ví dụ 5: Cho ôtômat không đơn định M = <s. Q. 5, q . F>.
ì ={0,1}, Q = {q,„ q,, q . q }. F ={q , q ỉ còn h à m chuyển
5: Q X E -> 2 cho dưối dạng đồ thị
0

2


Thêm u vào A -Closure(T);
Đặt u vào Stack;
end;
end;

T h u ậ t t o á n m ô phỏng ô t ô m a t k h ô n g đơn đ ị n h đ o á n n h ậ n
x â u vào:
Đ ầ u vào:

M ộ t x â u v à o to, k ế t t h ú c b
i ký h i ệ u file eof. M ộ t
ô t ô m a t k h ô n g đơn định N v ố i t r ạ n g t h á i ban đ ầ u q,,
và t ậ p t r ạ n g t h á i k ế t t h ú c F c Q .

Đ ầ u ra:

T r ả l ồ i "True" n ế u N đoán n h ậ n x â u co, "False" trong
trường hợp ngược l ạ i :

248


Thuật toán :
Begin
S:= A -Closure(q );
0

C:=ký tự tiếp;
While c eof do
begin

ngữ do ôtômat đơn định đoán nhận. Thật vậy, giả sử p e ì"
đoán nhận được bởi ôtômat không đơn định N = < I , Q. ỗ, q . F>
hay p 6 L(N).
0

Ta xây dựng ôtômat đơn định M = <E\ Q\ ố', So, F'> đoán
nhận p như sau: r = I ; Q' = 2 ; s ={q }; F'={U c Q / U n F * 0 Ị
còn ố: Q'xl -> Q' được xác định như sau:
Q

0

0

V u e Q'. V X € ì thì ố(U.x) = ỊJ S(q,x)
qeU

Với M định nghĩa như trên thì ta có: p e L(M) hay
UN) C L(M).
Ví du 6: Cho ôtómat không đơn định N = <z. Q. ỗ. q„. F>
vối I={a,b}. Q={s,j. s,}. F={s,}. còn h à m chuy
n ô: Q X ì ~> 2
được cho bằníỊ bảng chuy
n sau:
Q

Ký hiệu vào

Trạng thái
a

3

4

teo.

3

s,} còn F' = {q , q }.
3

4

4


H à m chuyển ố cho dưới dạng bảng chuyển như sau:
Trạng thái

q

3

q

4

Ký hiệu vào
a



Trong đồ thị chuyển trên thì A là xâu rỗng. Ta xây dựng
ôtômat đơn định M như sau:
M = <L. Q, 5. q , F>,
0

ở đây: ì = {a,b} là bảng ký hiệu vào,
Q = {A. B, c, D, E} là tập các trạng thái,
A là trạng thái ban đầu,
F = {E} tập trạng t h á i kết thúc,
A = {q , qi, q2,
c

B

c

D

B

E

E

B

c

hay ôtômat được biểu diễn dưới dạng đồ t h ị chuyển như sau:

Ta chỉ ra rằng L(N) = L(M) ={(a/b)" abb}.
Thật vậy. giả sử xét xâu vào là co = ababb
Ta chỉ ra rằng hai ôtômat N và M cùng đoán nhận xâu
co = ababb.
Thật vậy, đối vối ôtômat M ta xây d
n g chuỗi trạng thái
ứng với xâu vào co là:
co = a
b
a


nghĩa p h é p hợp E j

3

E

E

E

-

E

(

n

l ủ n

>-

n=l

G i ả sử ì = {a!,a ,
2

a j , n g ô n ngữ 0 v à n g ô n n g ữ {ã,}

(i = l,2,...,n) được gọi là n g ô n ngữ sơ cấp t r ê n L.
Định


(r)' là biểu thức chính quy biểu diễn ngôn ngữ R .
Từ định nghĩa vê ngôn ngữ chính quy và biểu thức chính
quy trên ì ta có:
Định lý 2: M ọ i ngôn ngữ chính quy trên bảng ì đều nhộn
được từ các ngôn ngữ hữu hạn bằng cách áp dụng một số hữu
hạn lần các phép toán hợp, phép nhân, phép lặp.
Định lý 3 : Một ngôn ngữ trên ì là chính quy khi và chỉ
khi nó biểu diễn được bởi một biển thức chính quy.
Chú ý: a) Một ngôn ngữ chính quy là vô hạn khi và chỉ khi
biểu thức chính quy biểu diễn nó có dấu + (phép lặp).
b) Lóp t ấ t cả các ngôn ngữ chính quy trên E là lốp bé nhất
chứa các tộp hữu hạn và đóng đôi vói các phép toán hợp, nhân
và lặp.
255


2.3. Thuật toán Thompson
Bài

toán:

Cho m ộ t b i ể u thức c h í n h quy. H ã y xây dựng

ô t ô m a t k h ô n g đơn định N đ o á n n h ậ n n g ô n n g ữ c h í n h quy t ừ
b i ể u thức c h í n h quy đã cho.
Thuật

toán:
Vào: M ộ t b i ể u thức chính quy r t r ê n bộ ì .

A

định N đ o á n n h ậ n n g ô n ngữ { } n h ư sau:
Start

A

KĐ—*®
v ố i i là t r ạ n g t h á i ban đ ầ u còn f là t r ạ n g t h á i k ế t t h ú c .
- Luật

2: V ố i a € ì , x â y dựng ô t ô m a t k h ô n g đơn định

đ o á n n h ậ n {a} n h ư sau:
Start

a

—CD——•©
vói i là t r ạ n g t h á i ban đ ầ u , f là t r ạ n g t h á i k ế t t h ú c .
- Luật 3: G i ả s
N(s), N(r) là các ô t ô m a t t h à n h p h ầ n ứng
v ố i các b i ể u thức c h í n h quy s v à r :
256


a) Đ ố i v ố i b i ể u thức c h í n h quy (s) u (r) ta x â y dựng
ô t ô m a t k h ô n g đơn định N đ o á n n h ậ n n g ô n ngữ s U I R n h ư sau:

ỏ đ â y i là t r ạ n g t h á i b a n đ ầ u , f là t r ạ n g t h á i k ế t t h ú c của N v à

A

-o

Start

-ỏ-ue^ò-

A

A

ở đ â y i là t r ạ n g t h á i ban đ ầ u , f là t r ạ n g t h á i k ế t t h ú c của N .
2.4. T í n h c h ấ t c ủ a n g ô n n g ữ c h í n h quy
Định

lý 4 : Lớp t ấ t cả các ngôn ngữ c h í n h quy t r ê n ì là

đ ó n g đ ố i v ố i các p h é p t o á n : hợp. n h â n , h i ệ u . l ấ y p h ầ n bù. n h â n
ghép và lặp.
Ì

Chứng

minh:

T í n h đóng đôi v ố i các p h é p t o á n hợp. n h â n

g h é p và l ặ p chứng m i n h theo định nghĩa b i ể u thức c h í n h quy.
Ta chứng m i n h t í n h đóng đối vói các p h é p t o á n còn l ạ i sau

0

2

F = F, X ( Q A F , ) ,
còn ỗ: Q X ì -> Q được xác đ ị n h n h ư sau:
ô((q,q').x) = <ô,(q,x). Ô (q'.x)> v ớ i q € Q,. q- e Q . X 6 ì .
2

2

Kiểm tra l ạ i L ( M ) = R. hay R là ngôn ngữ c h í n h quy t r ê n ì .
b) P h é p l ấ y p h ầ n bù: N ê u R là n g ô n ngữ c h í n h quy t r ê n ì
t h ì ta có R cũng n g ô n ngữ c h í n h quy t r ê n ì .

258


T h ậ t v ậ y , g i ả sử M = <E, Q, ô, q , F> là ô t ô m a t đ o á n n h ậ n
0

R. K h i đó ô t ô m a t M ' =_<z. Q,_ỗ, q,„ F'> với F' = Q \ F là ô t ô m a t
đ o á n n h ậ n ngôn ngữ R, hay R là n g ô n ngữ c h í n h quy t r ê n X.
c) P h é p t o á n giao giữa hai n g ô n ngữ c h í n h quy R[ v à R .
2

Vì Ri n R = R]
2


bao giò cũng xâv dựng được v ă n p h ạ m c h í n h quy G' sao

ri.

L(G') = L(G) \
Định

cho

nghĩa

4: V ă n p h ạ m c h í n h quy suy rộng là v ă n

p h ạ m c h í n h quy m ẫ u n ê u nó k h ô n g có quy tệc A —> a.
Định

lý 6 : Đôi v ố i v ă n p h ạ m c h í n h quy suy rộng có t h ể

xây dựng được v ă n p h ạ m c h í n h quy m ẫ u t ư ơ n g đương v ố i nó.
Chứng

minh:

G i ả sử G = <z. A. ì. R> là v ă n p h ạ m c h í n h

quy suy rộng. T h ê m ký h i ệ u K v à o A v à đ ặ t A' = A a e R thay bởi cặp quy
A -> aK, K ->

A

Đ a đồ t h ị vừa được đ ị n h nghĩa n h í t t r ê n gọi là đồ h ì n h của
văn phạm.
Ví dụ: Cho v ă n p h ạ m c h í n h q u y m ẫ u :
G = < I . A. ì, R > , v ố i

ĩ, = {a. b . c. ả. e, í } . A = { I . A , B .

R = { I -> aA. I -> b A . A -> dA. A ->

c

-> eD.

c

A

be. c
A

c,

D}

-> cB. B -> bA.

-> f D . B -> e l . I -> . B -> . D ->

A


v à là đường đ ầ v đ ạ n ế u Ao = ì còn A„ là đ ỉ n h k ế t t h ú c (tức
A„ —>

A

là m ộ t quy tắc trong R cạa G).

T ừ các k h á i n i ệ m t r ê n ta suy ra: t ậ p d ẫ n x u ấ t đ ầ y đ ạ
trong v ă n p h ạ m G v à t ậ p các đ ư ờ n g đ ầ y đ ạ trong đa đồ t h ị cạa
G có t ư ơ n g ứ n g 1-1. đồng t h ờ i x â u X e L(G) k h i và chỉ k h i X
được sinh ra bởi đường đầy đ ạ t r o n g đ a đồ t h ị cạa G.
Chú ý: Đ ố i với v ă n p h ạ m c h í n h quv suv rộng k h ô n g p h ả i
là m ẫ u t h ì cũng lý l u ậ n n h ư t r ê n ta x â y d ự n g được đồ h ì n h cạa
nó.
Ví dụ: Cho G = <z. A. ì, R> là v ă n p h ạ m chính quy suy
rộng với R = {ì -> a i . I -> aB. B -> bB. B - » b}. Đồ h ì n h cạa G
được xây dựng n h ư san: đ ư a G v ề v ă n p h ạ m m ẫ u G' bằng cách
A

thay quy tắc B —» b bởi 2 quy tắc B -> b K v à K -> . Đồ h ì n h
cạa v ă n p h ạ m m ẫ u G' cũng là đồ h ì n h cạa G có dạng dưới đây:
a

ỏ đây ì là đ ỉ n h ban đ ầ u . K là đ ỉ n h k é t t h ú c .
Định

nghĩa

6: T ư ơ n g t ự n h ư đồ h ì n h cạa v ă n p h ạ m


dựng được ô t ô m a t h ữ u h ạ n tương đương với nó.
b) Đ ố i vói ô tô mat h ữ u h ạ n b ấ t kỳ có t h ể x â y dựng được
v ă n p h ạ m c h í n h quy suy rộng tương đương v ố i nó.
T ừ các k ế t q u ả t r ê n ta có định lý quan t r ọ n g sau đây:
Định

lý s :

a) Lốp các ngôn ngữ c h í n h quy t r ù n g với lớp n g ô n ngữ do
v ă n p h ạ m c h í n h quy sinh ra.
b) Ngôn ngữ t r ê n b ả n g ì là đ o á n n h ậ n được bởi ô t ô m a t
h ữ u h ạ n k h i và chỉ k h i ngôn ngữ đó là ngôn ngữ c h í n h quy.

262


BÀI T Ậ P
1. Ô t ô m a t M được cho dưới d ạ n g b ả n g chuyển sau
Trạng thái

Ký h i ệ u vào
0

1

qo

q2

q

a) V i ế t đ ầ y đ ủ theo định nghĩa của M .
b) M là ô t ô m a t đơn định hay k h ô n g đơn định ? Vì sao ?
c)

Đ ư a ô t ô m a t M vê dạng đồ t h ị chuyển.

d) K i ể m tra l ạ i sự (toán n h ậ n của M đối v ố i các x â u sau:
co, = 001110111000;
© 2 = 110111101111.
Theo định nghĩa L ( M ) = {co / ra e X* và ơ(q , 0) 6 F}.
0

2.

Ô t ô m a t M được cho dưới b ả n g chuyển n h ư sau:
Trạng thái

Ký h i ệ u vào
a

b

{q.,q }
0
3

0

{qo.q.}
q-2


a)

V i ế t đ ầ y đ ủ M dưới dạng định nghĩa.

b)

M l à ô t ô m a t đ ơ n đ ị n h h a y k h ô n g đ ơ n đ ị n h ? V ì sao ?

c)

V i ế t M dưới d ạ n g đồ t h ị chuyển.

d)

M ô t ả s ự đ o á n n h ậ n c ủ a M đ ố i v ố i x â u co t h e o c á c h x â v
dựng cây đoán nhận với :
co = a"ba"

( v ố i n > 1).

n

m

(n>l,m>2),

n

m