Giáo trình Tin học lý thuyết - Chương 4: Văn phạm chính quy và các tính chất

0 
B → 0D⏐1C 
C → 0B⏐1D⏐0 
D → 0D⏐1D 
 Trong văn phạm trên, biến D không có ích nên ta có thể loại bỏ D và tất cả các 
luật sinh liên quan tới D, rút gọn văn phạm thành : 
A → 0B⏐0 
B → 1C 
C → 0B⏐0 
A 
C B0 
1
0, 1
Start 
D
0 
11 0 
Hình 4.3 - DFA cho 0(10)*
Ii. MỘT SỐ TÍNH CHẤT CỦA TẬP HỢP CHÍNH QUY 
Một câu hỏi khá quan trọng được đặt ra là: Cho ngôn ngữ L với một số tính chất đặc 
tả nào đó, liệu L có phải là tập chính quy không ? Phần này cung cấp một số lý thuyết 
giúp trả lời câu hỏi này. 
2.1. Bổ đề bơm cho tập hợp chính quy 
Một trong những nguyên lý hiệu quả là "Bổ đề bơm", đây là một công cụ mạnh giúp 
chứng minh các ngôn ngữ không là chính quy. Đồng thời, nó cũng thực sự hữu ích 
trong việc phát triển các giải thuật liên quan đến các ôtômát, chẳng hạn như một ngôn 
ngữ được chấp nhận bởi một FA cho trước là hữu hạn hay vô hạn ? 
BỔ ĐỀ 4.1: (BỔ ĐỀ BƠM) 
Chương IV : Văn phạm chính quy và các tính chất 
 57
Nếu L là tập hợp chính quy thì có tồn tại hằng số n sao cho nếu z là một từ bất 
kỳ thuộc L và | z | ≤ n, ta có thể viết z = uvw với | uv | ≤ n, | v | ≥ 1 và ∀i ≥ 0, ta có 
uviw ∈ L. 
Hơn nữa n không lớn hơn số trạng thái của FA nhỏ nhất chấp nhận L. 
Chứng minh 
Nếu một ngôn ngữ L là ngôn ngữ chính quy thì nó sẽ được chấp nhận bởi một 
DFA M (Q, Σ, δ, q0, F) với n trạng thái. 
Xét chuỗi nhập z có m ký hiệu được cho như trong bổ đề, vậy z = a1a2 ... am, m ≥ n, và 
với mỗi i = 1, 2, ..., m , ta đặt δ(q0, a1a2...ai) = qi. Do m ≥ n nên cần phải có ít nhất n+1 
trạng thái trên đường đi của ôtômát chấp nhận chuỗi z. Trong n+1 trạng thái này phải 
có hai trạng thái trùng nhau vì ôtômát M chỉ có n trạng thái phân biệt, tức là có hai số 
nguyên j và k sao cho 0 ≤ j < k ≤ n thỏa mãn qj = qk. Đường đi nhãn a1a2 ... am trong 
sơ đồ chuyển của M có dạng như sau: 
q0
a1. . . aj 
q0qj=qk 
ak+1. . am 
aj+1. . ak 
Hình 4.4 - Đường đi trong sơ đồ chuyển của DFA M 
Vì j < k nên chuỗi aj+1...ak có độ dài ít nhất bằng 1 và vì k ≤ n nên độ dài đó không thể 
lớn hơn n. 
Nếu qm là một trạng thái trong F, nghĩa là chuỗi a1a2...am thuộc L(M), thì chuỗi 
a1a2...aj ak+1ak+2...am cũng thuộc L(M) vì có một đường dẫn từ q0 đến qm ngang qua qj 
nhưng không qua vòng lặp nhãn aj+1... ak. Một cách hình thức, ta có : 
 δ(q0, a1a2...aj ak+1ak+2...am) = δ (δ(q0, a1a2...aj), ak+1ak+2...am) 
= δ (qj, ak+1ak+2...am) 
= δ (qk, ak+1ak+2...am) 
= qm 
Vòng lặp trong hình trên có thể được lặp lại nhiều lần - thực tế, số lần muốn lặp là tùy 
ý, do đó chuỗi a1...aj (aj+1...ak)i ak+1...am ∈ L(M), ∀i ≥ 0. Điều ta muốn chứng tỏ ở đây 
là với một chuỗi có độ dài bất kỳ được chấp nhận bởi một FA, ta có thể tìm được một 
chuỗi con gần với chuỗi ban đầu mà có thể "bơm" - lặp một số lần tùy ý - sao cho 
chuỗi mới thu được cũng được chấp nhận bởi FA. 
Đặt u = a1...aj, v = aj+1...ak và w = ak+1...am. 
Ta có điều phải chứng minh. 
Ứng dụng của bổ đề bơm 
Chương IV : Văn phạm chính quy và các tính chất 
 58
Bổ đề bơm rất có hiệu quả trong việc chứng tỏ một tập hợp không là tập hợp chính 
quy. Phương pháp chung để ứng dụng nó dùng phương pháp chứng minh “phản 
chứng” theo dạng sau : 
1) Chọn ngôn ngữ mà bạn cần chứng tỏ đó không là ngôn ngữ chính quy. 
2) Chọn hằng số n, hằng số được đề cập đến trong bổ đề bơm. 
3) Chọn chuỗi z thuộc L. Chuỗi z phải phụ thuộc nghiêm ngặt vào hằng số n đã 
chọn ở bước 2. 
4) Giả thiết phân chuỗi z thành các chuỗi con u, v, w theo ràng buộc | uv | ≤ n và 
| v | ≥ 1 
5) Mâu thuẫn sẽ phát sinh theo bổ đề bơm bằng cách chỉ ra với u, v và w xác định 
theo giả thiết, có tồn tại một số i mà ở đó uviw ∉ L. Từ đó có thể kết luận rằng 
L không là ngôn ngữ chính quy. Chọn lựa giá trị cho i có thể phụ thuộc vào n, 
u, v và w. 
Ta có thể phát biểu một cách hình thức nội dung của bổ đề bơm như sau : 
(∀L)(∃n)(∀z)[ z thuộc L và | z | ≥ n ta có 
 (∃u, v, w)(z = uvw, | uv | ≤ n, | v | ≥ 1 và (∀i)(uviw thuộc L))] 
Thí dụ 4.5 : Chứng minh tập hợp L = { 0i2 | i là số nguyên, i ≥ 1} (L chứa tất cả các 
chuỗi số 0 có độ dài là một số chính phương) là tập không chính quy. 
Chứng minh 
Giả sử L là tập chính quy và tồn tại một số n như trong bổ đề bơm. 
Xét từ z =0n2. Theo bổ đề bơm, từ z có thể viết là z = uvw với 1 ≤ | v | ≤ n và 
uviw ∈ L, ∀i ≥ 0. Trường hợp cụ thể, xét i = 2 : ta phải có uv2w ∈ L. 
Mặt khác : n2 < | uv2w | ≤ n2 + n < (n+1)2. 
Do n2 và (n+1)2 là 2 số chính phương liên tiếp nên | uv2w | không thể bằng một 
số chính phương, vậy uv2w ∉ L. 
Điều này dẫn đến sự mâu thuẫn, vậy giả thiết ban đầu là sai. Suy ra L không là 
tập chính quy. 
Câu hỏi : 
 Hãy tự liên hệ một số tập ngôn ngữ khác mà bạn nghĩ chúng không thuộc lớp 
 ngôn ngữ chính quy vì không thể thỏa mãn các tính chất của Bổ đề bơm ? 
2.2. Tính chất đóng của tập hợp chính quy 
Có nhiều phép toán trên ngôn ngữ chuyên sử dụng cho tập hợp chính quy, mà cho 
phép khi áp dụng chúng vào tập hợp chính quy thì vẫn giữ được các tính chất của tập 
Chương IV : Văn phạm chính quy và các tính chất 
 59
chính quy. Nếu một lớp ngôn ngữ nào đó "đóng" với một phép toán cụ thể, ta gọi đó 
là tính chất đóng của lớp ngôn ngữ này. 
ĐỊNH LÝ 4.3 : Tập hợp chính quy đóng với các phép toán: hợp, nối kết và bao 
đóng Kleen. 
Chứng minh 
Hiển nhiên từ định nghĩa của biểu thức chính quy. 
ĐỊNH LÝ 4.4 : Tập hợp chính quy đóng với phép lấy phần bù. Tức là, nếu L là 
tập chính quy và L ⊆ Σ* thì Σ* - L là tập chính quy. 
Chứng minh 
Gọi L là L(M) cho DFA M (Q, Σ1, δ, q0, F) và L ⊆ Σ*. 
Trước hết, ta giả sử Σ1 = Σ vì nếu có ký hiệu thuộc Σ1 mà không thuộc Σ thì ta 
có thể bỏ các phép chuyển trong M liên quan tới các ký hiệu đó. Do L ⊆ Σ* nên việc 
xóa như vậy không ảnh hưởng tới M. Nếu có ký hiệu thuộc Σ nhưng không thuộc Σ1 
thì các ký hiệu này không xuất hiện trong L. Ta thiết kế thêm một trạng thái "chết" d 
trong M sao cho δ(d, a) = d, ∀a ∈Σ và δ(q, a) = d, ∀q ∈ Q và a ∈ Σ - Σ1. 
Bây giờ, để chấp nhận Σ* - L, ta hoàn thiện các trạng thái kết thúc của M. 
Nghĩa là, đặt M’ = (Q, Σ, δ, q0, Q - F). Ta có M’ chấp nhận từ w nếu δ(q0,w) ∈ Q - F, 
suy ra w ∈ Σ* - L. 
ĐỊNH LÝ 4.5: Tập hợp chính quy đóng với phép giao 
Chứng minh 
Do ta có công thức biến đổi : 
1L ∩ = 2L 21 LL ∪ 
Nên theo các định lý trên, suy ra được tập L1 ∩ L2 là tập chính quy. 
Iii. các GIẢI THUẬT xác đỊnh TẬP hỢp CHÍNH QUY 
Một vấn đề khác, cũng rất cần thiết là xác định các giải thuật giúp giải đáp nhiều câu 
hỏi liên quan đến tập hợp chính quy, chẳng hạn như : Một ngôn ngữ cho trước là 
rỗng, hữu hạn hay vô hạn ? Ngôn ngữ chính quy có tương đương với ngôn ngữ nào 
khác không ? ... Để xác định các giải thuật này, trước hết cần giả sử mỗi tập chính 
quy thì được biểu diễn bởi một ôtômát hữu hạn. Như đã biết, biểu thức chính quy 
dùng đặc tả cho tập hợp chính quy, do đó chỉ cần cung cấp thêm một cơ chế dịch từ 
dạng biểu thức này sang dạng ôtômát hữu hạn. Một số định lý sau có thể xem là nền 
tảng cho việc chuyển đổi này. 
Chương IV : Văn phạm chính quy và các tính chất 
 60
ĐỊNH LÝ 4.6: Tập hợp các chuỗi được chấp nhận bởi ôtômát M có n trạng thái 
là: 
1) Không rỗng nếu và chỉ nếu ôtômát chấp nhận một chuỗi có độ dài < n. 
2) Vô hạn nếu và chỉ nếu ôtômát chấp nhận một chuỗi có độ dài l với n ≤ l < 2n. 
Chứng minh 
1) Phần "nếu " là hiển nhiên. 
Ta chứng minh "chỉ nếu": Giả sử M chấp nhận một tập không rỗng. Gọi w là 
chuỗi ngắn nhất được chấp nhận bởi M. Theo bổ đề bơm, ta có | w | < n vì nếu w là 
chuỗi ngắn nhất và | w | ≥ n thì ta có thể viết w = uvy, và uy là chuỗi ngắn hơn trong 
L hay | uy | < | w | ⇒ Mâu thuẫn. 
2) Nếu w ∈ L và n ≤ | w | < 2n thì theo bổ đề bơm ta có w = w1w2w3 và w1w2 i w3 ∈ L 
với mọi i ≥ 0, suy ra L(M) vô hạn . 
Ngược lại, nếu L(M) vô hạn thì tồn tại w ∈ L(M) sao cho | w | ≥ n. Nếu | w |< 
2n thì xem như đã chứng minh xong. Nếu không có chuỗi nào có độ dài nằm giữa n 
và 2n-1 thì gọi w là chuỗi có độ dài ít nhất là 2n nhưng ngắn hơn mọi chuỗi trong 
L(M), nghĩa là | w | ≥ 2n. Một lần nữa, cũng theo bổ đề bơm, ta có thể biểu diễn w = 
w1w2w3, trong đó 1 ≤ | w2 | ≤ n và w1w3 ∈ L(M). Ta có hoặc w không phải là chuỗi 
ngắn nhất có độ dài ≥ 2n, hoặc là n ≤ | w1w3 | ≤ 2n-1 ⇒ Mâu thuẫn. Vậy có tồn tại 
chuỗi có độ dài l sao cho n ≤ l < 2n. 
ĐỊNH LÝ 4.7 : Có giải thuật để xác định hai ôtômát tương đương (chấp nhận 
cùng một ngôn ngữ). 
Chứng minh 
Đặt M1, M2 là hai ôtômát chấp nhận L1, L2. 
Theo các định lý 4.3, 4.4, 4.5, ta có ( ∩ 1L 2L ) ∪ ( 1L ∩ ) được chấp nhận 
bởi ôtômát M
2L
3 nào đó. Dễ thấy M3 chấp nhận một chuỗi nếu và chỉ nếu L1 ≠ L2. Theo 
định lý 4.6, ta thấy có giải thuật để xác định xem liệu L1 = L2 hay không. 
Chương IV : Văn phạm chính quy và các tính chất 
 61
Tổng kết chương IV: Qua chương này, chúng ta có thể thấy rõ hơn các tính chất của 
lớp ngôn ngữ chính quy và cách xác định chúng bằng một số giải thuật. Mối liên quan 
giữ hai cơ chế đoán nhận ngôn ngữ (ôtômát hữu hạn) và phát sinh ngôn ngữ (văn 
phạm) cũng đã được thiết lập và chứng minh rõ ràng. Đây là lớp ngôn ngữ nhỏ nhất 
theo sự phân cấp của Noam Chomsky. Trong những chương tiếp theo, chúng ta sẽ 
khảo sát những lớp ngôn ngữ rộng lớn hơn chứa cả ngôn ngữ chính quy trong nó. 
BÀI TẬP CHƯƠNG IV 
4.1. Xây dựng văn phạm tuyến tính trái và tuyến tính phải cho các ngôn ngữ sau : 
 a) (0 + 1)*00(0 + 1)*
 b) 0*(1(0 + 1))*
 c) (((01 + 10)*11)*00)*
4.2. Xây dựng văn phạm chính quy sinh ra các ngôn ngữ trên bộ chữ cái Σ = {0,1} 
như sau : 
 a) Tập các chuỗi có chứa 3 con số 0 liên tiếp. 
 b) Tập các chuỗi kết thúc bằng 2 con số 0. 
4.3. Xây dựng văn phạm chính quy sinh ra các ngôn ngữ sau : 
 a) { w | w ∈ (0 + 1)* } 
 b) { am bn | m, n > 0 } 
4.4. Chứng tỏ rằng ngôn ngữ L = {0n1n | n là số nguyên dương} không chính qui. 
4.5. Ngôn ngữ nào trong các ngôn ngữ sau không là ngôn ngữ chính qui? Chứng minh 
câu trả lời: 
a) L = {02n | n là số nguyên dương } 
b) L = {0n1m0 n+m | m, n là số nguyên dương} 
c) L = {0n | n là số nguyên tố }