Giáo trình Tin học lý thuyết - Chương 3: Ôtômát hữu hạn và biểu thức chính quy

p nhận bởi 
DFA sau : 
 1 
1 
q1 q2 q
3 
0 
0 0, 1 
Start 
Hình 3.10 – DFA cho ví dụ 3.13 
Gọi DFA được chỉ ra trong hình 3.10 là M ({q1, q2, q3}, {0, 1}, δ, q1, {q2, q3}). Ta 
thấy, tập hợp tất cả các chuỗi được chấp nhận bởi DFA trên là các chuỗi làm cho 
ôtômát chuyển từ trạng thái bắt đầu q1 đến một trong hai trạng thái kết thúc q2 và q3 
và không chuyển qua số tối đa là 3 (k = 3) trạng thái của ôtômát. Vậy ta cần viết biểu 
thức chính quy ký hiệu cho tập hợp này như sau : 
r = r312 + r313 
Theo công thức đã được chứng minh trong Định lý, ta có thể tính được các giá trị rkij 
với i, j là chỉ số các trạng thái từ 1 đến 3 và với k = 0, 1 và 2, như chỉ ra trong bảng 
sau: 
 k = 0 k = 1 k = 2 
rk11 ε ε (00)*
Chương III : Ôtômát hữu hạn và biểu thức chính quy 
 45
rk12 0 0 0(00)*
rk13 1 1 0*1 
rk21 0 0 0(00)*
rk22 ε ε + 00 (00)*
rk23 1 1 + 01 0*1 
rk31 ∅ ∅ (0 + 1)(00)*0 
rk32 0 + 1 0 + 1 (0 + 1)(00)*
rk33 ε ε ε + (0 + 1)0*1 
Bằng cách dùng các công thức tương đương như (r + s) t = rt + st và (ε + r)* = r* để 
đơn giản các biểu thức, chẳng hạn khi tính biểu thức : 
r122 = r021 (r011 )* r012 + r022 = 0(ε)*0 + ε = 00 + ε 
Tương tự, khi đơn giản biểu thức 
r213 = r112 (r122 )* r123 + r113 = 0(00 + ε)*(1 + 01) + 1 
ta nhận thấy (00 + ε)* tương đương với (00)* và (1 + 01) thì tương đương với (ε + 0)1 
nên ta rút gọn : 
r213 = 0(00)*(ε + 0)1 + 1 
Mặt khác, chú ý rằng (00)*(ε + 0) thì tương đương với 0*, vì thế 0(00)*(ε + 0)1 + 1 
cũng bằng 00*1 + 1 hay cuối cùng là 0*1. 
Để hoàn thành việc xây dựng biểu thức chính quy cho M, ta cần tính r312 và r313. Ta 
viết: 
 r312 = r213 (r233 )* r232 + r212 
= 0*1(ε + (0 + 1)0*1)*(0 + 1)(00)* + 0(00)* 
= 0*1((0 + 1)0*1)*(0 + 1)(00)* + 0(00)* 
và 
 r313 = r213 (r233 )* r233 + r213 
= 0*1(ε + (0 + 1)0*1)*(ε + (0 + 1))0*1) + 0*1 
= 0*1((0 + 1)0*1)* 
Vậy biểu thức chính quy có dạng : 
 r = r312 + r313 = 0*1((0 + 1)0*1)*(ε + (0 + 1)(00)*) + 0(00)* 
Iv. MỘT VÀI ỨNG DỤNG CỦA ÔTÔMÁT HỮU HẠN 
Có nhiều kiểu phần mềm thiết kế nhằm đặc tả sự chuyển đổi tự động từ dạng biểu 
thức chính quy sang việc cài đặt máy tính một cách hiệu quả tương ứng với ôtômát 
hữu hạn. Trong phần này, ta sẽ đề cập đến hai ứng dụng trong số chúng. 
4.1. Bộ phân tích từ vựng 
Chương III : Ôtômát hữu hạn và biểu thức chính quy 
 46 
Các ký hiệu từ vựng (token) trong một ngôn ngữ lập trình thì hầu hết không có sự 
ngọai lệ, được biểu diễn như các tập hợp chính quy. Chẳng hạn, các định danh của 
ALGOL: các chữ cái viết hoa hoặc thường, theo sau bởi một dãy bất kỳ của chữ cái 
(letter) hoặc chữ số (digit) với độ dài không giới hạn có thể được biểu diễn như sau : 
(letter) (letter + digit)*
trong đó "letter" thay thế cho A + B +...+ Z + a + b +...+ z và "digit" là 0 + 1 +...+ 9. 
Một ví dụ khác, các định danh của FORTRAN có độ dài giới hạn là 6 và các chữ cái 
chỉ cho phép dùng chữ viết hoa hoặc ký hiệu $ được biểu diễn như sau : 
(letter) (ε + letter + digit)5
với "letter" là $ + A + B + ... + Z . 
Trong SNOBOL, các hằng số số học có thể được biểu diễn như sau : 
(ε + −) (digit + (• digit * + ε) + • digit+ ) 
Một số công cụ phát sinh bộ phân tích từ vựng nhận input như một dãy các biểu thức 
chính quy mô tả các ký hiệu từ vựng và phát sinh một ôtômát hữu hạn đơn giản nhận 
dạng mọi ký hiệu từ vựng. Thông thường, chúng chuyển đổi biểu thức chính quy 
thành một NFA với ε-dịch chuyển và sau đó xây dựng tập hợp con các trạng thái để 
có thể phát sinh DFA một cách trực tiếp hơn là tìm cách loại bỏ các phép chuyển 
nhãn ε. Mỗi trạng thái kết thúc xác định ký hiệu từ vựng cụ thể đã tìm thấy. Hàm 
chuyển của FA sẽ được mã hóa bằng một trong vài cách nhằm chiếm ít không gian 
hơn so với bảng hàm chuyển tổ chức dưới dạng mảng hai chiều. Bộ phân tích từ vựng 
được thiết lập bằng cách phát sinh một chương trình cố định thông dịch các bảng mã, 
cùng với các bảng minh họa cụ thể sự nhận dạng của FA trên các ký hiệu từ vựng 
(viết dưới dạng các biểu thức chính quy). Bộ phân tích từ vựng dạng này có thể được 
dùng như một chương trình con độc lập (module) trong một trình biên dịch ngôn ngữ. 
4.2. Trình soạn thảo văn bản 
Hiển nhiên, các trình soạn thảo văn bản hoặc các chương trình tương tự cho phép thay 
thế một chuỗi bởi mọi chuỗi kết hợp với một biểu thức chính quy cho trước. 
Chẳng hạn, trình soạn thảo văn bản ed trong UNIX cho phép một câu lệnh như sau : 
/aba*c/ 
để tìm sự xuất hiện đầu tiên của chuỗi có dạng như trên. Hay câu lệnh : 
s/bbb*/b/ 
cho phép thay thế các chuỗi có dạng bbb* thành chuỗi có một ký tự b. 
Hay trong các câu lệnh của MS-DOS và NC, ví dụ câu lệnh : 
Del tmp*.??? 
sẽ cho phép xóa đi tất cả các file với tên tập tin bắt đầu bằng tmp, sau đó là một chuỗi 
bắt kỳ và có phần mở rộng là 3 ký tự tùy ý. Dấu * trong trường hợp này ký hiệu cho 
một chuỗi bất kỳ, còn dấu ? ký hiệu cho một ký tự tùy ý. Đây cũng là một dạng ký 
hiệu của biểu thức chính quy thay thế cho chuỗi. 
Chương III : Ôtômát hữu hạn và biểu thức chính quy 
 47
Hay chẳng hạn, một ví dụ về xử lý chuỗi khác được áp dụng cho việc tìm kiếm theo 
mẫu trên các trang Web. 
Trong tất cả các ví dụ trên, ký hiệu * xác định “mọi” biểu thức a1 + a2 + ... + an trong 
đó các ai là tất cả các ký tự cho phép trong máy tính trừ ký tự xuống dòng (newline). 
Ta có thể chuyển một biểu thức chính quy r sang DFA chấp nhận mọi r. Chú ý rằng 
sự hiện diện của ký hiệu * sẽ cho phép ta nhận dạng một thành phần của L(r) bắt đầu 
từ bất kỳ vị trí nào trong dòng. Để làm được điều này, các ứng dụng phải thực hiện 
quá trình chuyển đổi từ một biểu thức chính quy sang NFA. Và vì cơ chế hoạt động 
của NFA khá phức tạp nên thông thường ngay sau đó, NFA lại phải được biến đổi 
tiếp thành dạng DFA tương đương. Tuy nhiên, sự chuyển đổi từ một biểu thức chính 
quy sang DFA tốn nhiều thời gian hơn việc sử dụng DFA để kiểm tra các mẫu bằng 
cách duyệt qua chúng một lần, tuy DFA có thể có số trạng thái là hàm mũ của độ dài 
biểu thức chính quy. 
Thực tế, trong trình soạn thảo văn bản UNIX, biểu thức chính quy với mọi r được 
chuyển thành một NFA có ε-dịch chuyển và sau đó NFA này được mô phỏng một 
cách trực tiếp. 
Câu hỏi : 
Hãy tự liên hệ một số các ứng dụng thực tế khác dùng cơ 
chế ôtômát hữu hạn ? 
Tổng kết chương III: Phần nội dung chương III tập trung nghiên cứu cơ chế hoạt 
động của các dạng ôtômát hữu hạn, mối tương quan giữa chúng, cũng như sự tương 
đương của chúng với biểu thức chính quy. Tùy theo các yêu cầu thực tế của ứng 
dụng, ta có thể chuyển từ dạng phức tạp nhất sang các dạng đơn giản hơn. Có thể tóm 
tắt sự tương quan giữa các Định lý trong chương này theo sơ đồ sau : 
Định lý 4 Định lý 2 
DFA NFA 
Định lý 1 
 NFAε 
Định lý 3 
RE 
Chương III : Ôtômát hữu hạn và biểu thức chính quy 
 48 
BÀI TẬP CHƯƠNG III 
3.1. Mô tả ngôn ngữ được chấp nhận bởi các ôtômát hữu hạn với sơ đồ chuyển được 
cho như sau : 
 a) 
A B C1 
0 1 0,1
0 
 b) 
A B C1 
1 1
1 0 
 D 
0 
0 
3.2. Xây dựng các sơ đồ chuyển ôtômát hữu hạn chấp nhận các ngôn ngữ sau trên bộ 
chữ cái Σ = {0, 1} 
a) Tập các chuỗi kết thúc là 00. 
b) Tập các chuỗi có 3 ký hiệu 0 liên tiếp. 
c) Tập các chuỗi mà ký hiệu thứ 3 kể từ cận phải của chuỗi là 1. 
d) Tập mọi chuỗi mà bất cứ chuỗi con nào có độ dài bằng 5 đều có chứa ít 
nhất 2 con số 0. 
3.3. Tìm các sơ đồ chuyển ôtômát hữu hạn đoán nhận các ngôn ngữ sau : 
 a) Tập các chuỗi trên {0, 1} có chứa một số chẵn các số 0 và một số lẻ các số 1 
 b) Tập các chuỗi trên {0, 1} có độ dài chia hết cho 3. 
 c) Tập các chuỗi trên {0, 1} không chứa 101 như một chuỗi con. 
3.4. Xây dựng DFA tương đương với mỗi NFA sau : 
a) N1({0,1,2,3},{a,b},δ1,0,{3}) với δ1 b) N2 ({0,1,2,3}, {a,b}, δ2,0, {1,3}) với δ2
δ1 a b δ2 a b 
 0 {0, 1} {1} 0 {1, 3} {1} 
 1 {2} {2} 1 {2} {1, 2} 
 2 {3} ∅ 2 {3} {0} 
3 {3} {3} 3 ∅ {0} 
Chương III : Ôtômát hữu hạn và biểu thức chính quy 
 49
c) 
 1 2 3
a a, b 
d) 
3.5. Tìm NFA không có ε-dịch chuyển nhận dạng cùng ngôn ngữ với các NFA sau : 
 a) 
b) 
3.6. Viết biểu thức chính quy và vẽ NFA đoán nhận các ngôn ngữ sau : 
a) Tập hợp các chuỗi trên Σ = {1, 2, 3} sao cho ký hiệu cuối cùng đã có xuất 
hiện trước đó . 
b) Tập hợp các chuỗi trên Σ = {0, 1} trong đó có một cặp ký tự 0 cách nhau 
bởi một chuỗi con có độ dài 4i, với i ≥ 0 nào đó. 
3.7. Viết biểu thức chính quy cho mỗi ngôn ngữ sau trên Σ = { 0, 1} : 
a) Tập hợp các chuỗi trong đó mọi cặp 0 liên tiếp đều xuất hiện trước mọi cặp 
1 liên tiếp. 
 4 a, b 
a, b 
1 2 3
a, b 0 4 
a 
a 
a, b 
a a, b 
a, b 
q0 q1 q2 a, ε a, b q3 c, ε 
a a 
1
0 
1ε 0
q2q0
q3q1 ε 
ε 
Chương III : Ôtômát hữu hạn và biểu thức chính quy 
 50 
b) Tập hợp các chuỗi chứa nhiều nhất một cặp 0 liên tiếp và nhiều nhất một 
cặp 1 liên tiếp. 
3.8. Mô tả (bằng lời) ngôn ngữ được các biểu thức chính quy sau đặc tả : 
a) 0(0 + 1)* 0 
b) (0+ 1)*0(0 + 1) (0 + 1) 
c) (11+ 0)*(00+ 1) 
d) (1+ 01+ 001)*(ε + 0 + 00) 
e) [ 00 + 11 + (01+ 10) (00+ 11)*(01+ 10)]* 
3.9. Chứng tỏ các biểu thức chính quy sau ký hiệu cho cùng một ngôn ngữ : 
 (aa)* , (aa)* + (∅a) , (aa + aaaa)* , (aa)* (aa)*
3.10. Vẽ NFA với ε-dịch chuyển được cho bởi các biểu thức chính qui sau. Sau đó, 
hãy chuyển sang DFA tương đương : 
a) ( a* + b*)* 
b) ((ε + a) b*)* 
c) (a + b)* abb (a + b)* 
d) ab + (a + bb) a*b 
e) (a + ab + aab)*(ε+ a+ aa) 
f) 10 + (0 + 11)0*1 
g) 01 [ (( 10)*+ 111)* + 0]*1 
3.11. Hãy tìm các biểu thức chính qui tương ứng với các sơ đồ chuyển trạng thái sau: 
 a) b) 
BÀI TẬP LẬP TRÌNH 
3.12. Viết chương trình trong Pascal / C mô phỏng một FA chấp nhận ngôn ngữ được 
biểu diễn bởi biểu thức chính quy sau : 
 [ A ... Z, a ... Z ]+ [ A ... Z, a ... Z, 0 ... 9, _ ]* + [ 0 ... 9]+ + op 
3.13. Viết chương trình cho ra một FA tương ứng khi đầu vào là một biểu thức chính 
quy. 
A B 
C 
1 
0 
0 
0 
1 
1 
A B
C 
0 
1 0 
1 
0 
1 
Chương III : Ôtômát hữu hạn và biểu thức chính quy 
 51
3.14. Viết chương trình cho ra DFA khi đầu vào là một NFA.