Giáo trình Tin học lý thuyết - Chương 5: Văn phạm phi ngữ cảnh

, C → a và S → AB 
Chương V : Văn phạm phi ngữ cảnh 
 88 
Hay S ∈ V1 có nghĩa là S có thể sinh ra các chuỗi ký hiệu kết thúc. Vậy ngôn 
ngữ sinh bởi văn phạm G : L(G) không rỗng. 
. Để kiểm tra tính hữu hạn của văn phạm, ta vẽ đồ thị có hướng tương ứng với 
các luật sinh trong văn phạm như sau : 
B
S
A 
C
 Hình 5.6 - Đồ thị có hướng tương ứng 
 Rõ ràng, ta thấy đồ thị không có chu trình. Hạng của S, A, B, C lần lượt là 3, 2, 
1 và 0. Chẳng hạn, một đường đi dài nhất từ S là S → A → B → C. Vậy văn phạm 
này là hữu hạn, nó sinh ra hữu hạn chuỗi và độ dài các chuỗi không lớn hơn 23 = 8. 
 Thực tế, chuỗi dài nhất dẫn xuất được từ S là : 
 S ⇒ AB ⇒ BCB ⇒ CCCB ⇒ CCCCC ⇒* aaaaa ,với độ dài chuỗi là 5. 
 Nếu ta thêm vào văn phạm một luật sinh mới : C → AB, thì đồ thị có hướng 
tương ứng lúc đó có dạng như sau : 
BA
C
S
 Hình 5.7 - Đồ thị có hướng tương ứng văn phạm bổ sung 
 Đồ thị mới này có nhiều chu trình, chẳng hạn A → B → C → A. Vậy ta phải 
tìm được một dẫn xuất dạng A ⇒* α3Aβ3 , cụ thể là A ⇒ BC ⇒ CCC ⇒ CABC, 
trong đó α3 = C và β3 = BC. Vì C ⇒* a và BC ⇒* ba nên A ⇒* aAba. 
 Mặt khác, S ⇒* Ab và A ⇒* a, suy ra : S ⇒* aia(ba)ib, ∀i. Vậy ngôn ngữ sinh 
từ văn phạm mới là vô hạn. 
5.2. Giải thuật thành viên (Membership) 
ĐỊNH LÝ 5.10 : Tồn tại giải thuật để xác định với một CFL nào đó sinh ra từ 
CFG G(V, T, P, S) và một chuỗi x bất kỳ thì x có thuộc L(G) hay không ? 
Chứng minh 
Chương V : Văn phạm phi ngữ cảnh 
 89
Có một vài giải thuật được đề nghị cho bài toán thành viên này. Sau đây trình bày 
một giải thuật theo vòng lặp đơn giản, ta gọi là giải thuật CYK (Cocke-Younger-
Kasami) với thời gian tỷ lệ với | x |3. 
Giả sử văn phạm G (V, T, P, S) đã có dạng chuẩn Chomsky và | x | = n ≥ 1. 
Trước hết, ta phải xác định với mỗi i, j và mỗi biến A, phải chăng A ⇒* xij , trong đó 
xij là một chuỗi con của chuỗi x tính từ vị trí thứ i và có độ dài j. 
Ta chứng minh quy nạp theo độ dài j : 
- Với j = i : ta có A ⇒* xij khi và chỉ khi A → xij là một luật sinh. 
- Với j > i : ta có A ⇒* xij khi và chỉ khi có một luật sinh dạng A → BC và 
số k, 1 ≤ k < j sao cho B dẫn xuất ra k ký hiệu đầu tiên của xij và C dẫn xuất 
ra j – k ký hiệu cuối của xij. Có nghĩa là : 
B ⇒* xik và C ⇒* x i+ k, j - k
Vì cả k và j – k đều nhỏ hơn j, nên theo giả thiết quy nạp ta đã xác định được 
liệu hai chuỗi dẫn xuất này có tồn tại hay không ? Thế thì cũng có thể c]xác 
định được liệu A ⇒* xij hay không ? 
Với cách thực hiện như thế, ta sẽ xác định được phải chăng S ⇒* x1n , nhưng x1n = x, 
vậy x ∈ L(G) khi và chỉ khi S ⇒* x1n. 
 Sau đây trình bày giải thuật CYK theo giải thuật trên, trong đó Vij là tập hợp 
tất cả các biến A sao cho A ⇒* xij . Chú ý rằng ta có thể giả thiết 1 ≤ i ≤ n – j + 1, bởi 
vì lúc đó chuỗi con xij với độ dài j mới thực sự tồn tại. 
 Bước (1) và (2) xử lý trường hợp j = i. Vì văn phạm G đã cho sẵn, cho nên 
bước (2) chiếm mộ thời gian cố định. Vậy các bước (1) và (2) chiếm thời gian O(n). 
các vòng lặp For ở các dòng (3) và (4) làm cho các bước từ (5) đến (7) lặp lại nhiều 
nhất là n2 lần (do i, j ≤ n). Bước (5) mỗi lần thực hiện cũng chiếm một khoảng thời 
gian cố định. Vậy tổng thời gian để thực hiện bước (5) là O(n2). Vòng lặp For ở dòng 
(6) làm cho bước (7) lặp lại n lần hoặc ít hơn. Vì bước (7) cũng chiếm một thời gian 
cố định, nên các bước (6) và (7) gộp lại chiếm thời gian O(n). Vì các bước này được 
thực hiện O(n2), nên tổng thời gia thực hiện cho bước (7) là O(n3). Vậy thời gian thực 
hiện toàn bộ giải thuật là ở cấp O(n3). 
Giải thuật CYK: 
 Begin 
 (1) For i := 1 to n do 
 (2) Vij := { A | A → a là một luật sinh và a là ký hiệu thứ i trong x } 
 (3) For j := 2 to n do 
 (4) for i := 1 to n – j + 1 do 
 begin 
 (5) Vij := 0; 
 (6) for k := 1 to j - 1 do 
 (7) Vij := Vij ∪ { A | A → BC là một luật sinh, B ∈ Vik 
và C ∈ Vi+ k, j – k } 
 end; 
Chương V : Văn phạm phi ngữ cảnh 
 90 
End; 
Thí dụ 5.17 : Cho văn phạm G có dạng chuẩn Chomsky chứa các luật sinh sau : 
 S → AB | BC 
 A → BA | a 
 B → CC | b 
 C → AB | a 
 Xét chuỗi nhập x = baaba. 
 Bảng các Vij cho ở hình 5.8 dưới đây. Dòng đầu tiên trong bảng được cho bởi 
các bước (1) và (2) trong giải thuật. Vì x11 = x41 = b nên V11 = V41 = {B} vì B là biến 
duy nhất dẫn xuất ra b, còn x21 = x31 = x51 = a, suy ra V21 = V31 = V51 = {A, C} vì A 
và C có các luật sinh với a bên vế phải. 
 b a a b a 
 1 2 3 4 5 
 1 B A, C A, C B A, C 
2 S, A B S, C S, A 
3 ∅ B B 
4 ∅ S, A, C 
5 S, A, C 
Vij
Hình 5.8 – Bảng các Vij
Để tính Vij với j > i, ta phải thực hiện vòng lặp For ở bước (6) và (7). Ta phải đối 
chiếu Vik với Vi+ k, j – k với k = 1, 2, …, j - 1 để tìm biến D trong Vik và biến E trong 
Vi+ k, j – k sao cho DE là vế phải của một hay nhiều luật sinh. Các vế trái của những 
luật sinh đó được đưa vào trong Vij. Quá trình đối chiếu đó diễn ra bằng cách giảm 
dần giá trị cột i, đồng thời tăng dần lên theo đường chéo qua Vij về phía phải như các 
chiều mũi tên vẽ trong hình 5.9. 
 • 
i
j 
Hình 5.9 – Quá trình tính các Vij
Chẳng hạn, để tính V24, đầu tiên ta đối chiếu V21 = {A, C} với V33 = {B}. Ta có V21 
V33 = {AB, CB}. Vì có các luật sinh S → AB và C → AB nên S và C được đưa vào 
Chương V : Văn phạm phi ngữ cảnh 
 91
V24. Tiếp đến ta lại xét V22 V42 = {A}{S, A} = {BS, BA}. Vì có luật sinh A → BA, 
vậy ta đưa thêm A vào V24. Cuối cùng ta xét V23 V51 = {B}{A, C} = {BA, BC} gặp 
lại các vế phải đã xét, vậy không thể thêm gì vào V24. Vậy V24 = {S, AC}. 
Cuối cùng, vì S ∈ V15 , vậy chuỗi baaba là thuộc ngôn ngữ sinh ra bởi văn phạm đã 
cho. 
Tổng kết chương V: Việc mô tả ngôn ngữ phi ngữ cảnh bằng phương tiện văn phạm 
phi ngữ cảnh tỏ ra rất hữu hiệu, cũng tương tự như việc sử dụng văn phạm BNF trong 
định nghĩa các ngôn ngữ lập trình. Trong chương này, chúng ta đã khảo sát tương đối 
cặn kẽ các phương tiện mô tả ngôn ngữ của văn phạm CFG thông qua các giải thuật 
tối ưu biến, giản lược, quy chuẩn và các tính chất của lớp ngôn ngữ mà nó mô tả. Câu 
hỏi đặt ra tiếp theo là có hay không một lớp ôtômát tương ứng để nhận dạng lớp ngôn 
ngữ phi ngữ cảnh. Như chúng ta đã thấy, lớp ngôn ngữ phi ngữ cảnh thực sự chứa lớp 
ngôn ngữ chính quy trong đó, nên ôtômát hữu hạn không thể nhận biết tất cả ngôn 
ngữ phi ngữ cảnh. Một cách trực quan, ôtômát hữu hạn có bộ nhớ bị hạn chế nghiêm 
ngặt, trong khi việc nhận dạng CFL có thể yêu cầu phải lưu trữ một lượng thông tin 
khá lớn. Khả năng cho sự mở rộng này sẽ được chúng ta xét đến trong nội dung của 
chương tiếp theo. 
Chương V : Văn phạm phi ngữ cảnh 
 92 
BÀI TẬP CHƯƠNG V 
5.1 . Hãy mô tả ngôn ngữ sinh bởi các văn phạm sau : 
a) S → aS | Sb | aSb | c 
b) S → SS | a | b 
c) S → SaS | b 
d) S → aSS | b 
e) S → aA | bB| c 
A → Sa 
B → Sb 
f) S → AB 
A → Sc | a 
B → dB | b 
g) S → TT 
T → aTa | bTb | c 
5.2. Hãy chỉ ra một văn phạm phi ngữ cảnh sinh ra tập hợp : 
a) Tập hợp các chuỗi đọc xuôi đọc ngược như nhau trên bộ chữ cái Σ = {0,1}. 
b) Tập hợp chuỗi các dấu ngoặc đúng trong biểu thức số học. 
 c) Tập hợp {aibicj | i, j ≥ 0} 
 d) Tập hợp {ambn | m, n > 0} 
e) Tập hợp {aicaj | i ≥ j ≥ 0} 
f) Tập hợp {ajbjcidi | i, j ≥ 1} 
5.3. Cho văn phạm G với các luật sinh sau : 
S → aB | bA 
A → a | aS | bAA 
B → b | bS | aBB 
Với chuỗi aaabbabbba , hãy tìm: 
a) Dẫn xuất trái nhất. 
b) Dẫn xuất phải nhất. 
c) Cây dẫn xuất. 
d) Văn phạm này có là văn phạm mơ hồ không ? 
5.4. Cho văn phạm G với các luật sinh sau : 
E → T | E + T | E - T 
T → F | T × F | T / F 
F → a | b | c | (E) 
Hãy vẽ cây dẫn xuất sinh ra các chuỗi nhập sau : 
a) a – (b × c / a) 
b) a × (b - c) 
Chương V : Văn phạm phi ngữ cảnh 
 93
c) (a + b) / c 
5.5. Cho văn phạm : S → aSbS | bSaS | ε 
a) Chứng tỏ văn phạm này là văn phạm mơ hồ . 
b) Xây dựng dẫn xuất trái (phải) và cây dẫn xuất tương ứng cho chuỗi abab. 
c) Văn phạm này sinh ra ngôn ngữ gì ? 
5.6. Chứng tỏ văn phạm sau đây là mơ hồ : 
S → If b then S else S 
S → If b then S 
S → a 
 Trong đó a, b, if, then, else là các ký hiệu kết thúc và S là biến. 
5.7. Chứng tỏ văn phạm sau đây là mơ hồ : 
S → aBS | aB | bAS | bA 
A → bAA | a 
B → aBB | b 
 Hãy đề nghị một văn phạm không mơ hồ tương đương ? 
5.8. Tìm CFG không có chứa ký hiệu vô ích tương đương với văn phạm: 
a) S → A | a 
A → AB 
B → b 
 b) S → AB | CA 
A → a 
B → BC | AB 
C → aB | b 
5.9. Tìm văn phạm tương đương với văn phạm sau không có chứa ký hiệu vô ích, luật 
sinh ε và luật sinh đơn vị : 
a) S → aSbS | bSaS | ε 
b) S → A | B 
A → aB | bS | b 
B → AB | Ba 
C → AS | b 
c) S → ABC 
A → BB | ε 
B → CC | a 
C → AA | b 
d) S → A | B 
A → C | D 
B → D | E 
C → S | a | ε 
D → S | b 
Chương V : Văn phạm phi ngữ cảnh 
 94 
E → S | c | ε 
5.10. Tìm văn phạm chỉ có chứa một luật sinh ε duy nhất S → ε tương đương với văn 
phạm sau : 
 S → AB 
A → SA | BB | bB 
B → b | aA | ε 
5.11. Biến đổi các văn phạm sau đây về dạng chuẩn CHOMSKY: 
a) S → bA | aB 
A → bAA | aS | a 
B → aBB | bS | b 
b) S → aAB | BA 
A → BBB| a 
B → AS| b 
c) S → adAda | aSa | aca 
A → bAb | bdSdb 
 d) S → 0S1 | 01 
e) S → #S | [ S ⊃ S] | p | q 
5.12. Biến đổi các văn phạm sau đây về dạng chuẩn GREIBACH: 
a) G ( {S, A}, {0, 1}, P, S) với các luật sinh : 
S → AA | 0 
A → SS | 1 
b) G ( {A1, A2, A3}, {a, b}, P, A1) với các luật sinh : 
A1 → A2A3
A2 → A3A1 | b 
A3 → A1A2 | a 
c) G ( {A1, A2, A3, A4}, {a, b}, P, A1) với các luật sinh : 
A1 → A2A3 | A3A4
A2 → A3A2 | a 
A3 → A4A4 | b 
A4 → A2A3 | a 
5.13. Chứng minh rằng các ngôn ngữ sau không phải là CFL: 
a) L = {a
i b
j c
k⏐ i < j < k } 
b) L = {a
i 
b
j⏐ j = i2 } 
c) L = {ai⏐ i là số nguyên tố } 
d) L = {anbncndn | n ≥ 0} 
BÀI TẬP LẬP TRÌNH 
5.14. Viết chương trình loại bỏ các ký hiệu vô ích trong một CFG. 
5.15. Viết chương trình chuẩn hóa một CFG thành dạng chuẩn CHOMSKY (CNF). 
Chương V : Văn phạm phi ngữ cảnh 
 95
5.16. Viết chương trình chuẩn hóa một CFG thành dạng chuẩn GREIBACH (GNF).