Giáo trình Ôtômát và ngôn ngữ hình thức (Phần 2)

 Ôtômát và ngôn ngữ hình thức 
 - 109 - 
CHƢƠNG V 
Các ngôn ngữ phi ngữ cảnh 
Nội dung của chương năm đề cập đến: 
 Cây dẫn xuất và các phương pháp xác định văn phạm phi ngữ cảnh, 
 Tính nhập nhằng và quá trình giản lược văn phạm phi ngữ cảnh, 
 Các dạng chuẩn: dạng chuẩn Chomsky và dạng chuẩn Greibach, 
 Bổ đề Bơm (điều kiện cần) cho các ngôn ngữ phi ngữ cảnh và một số 
thuật toán quyết định được. 
5.1 Các ngôn ngữ phi ngữ cảnh và các cây dẫn xuất 
Ngôn ngữ phi ngữ cảnh thường được sử dụng trong thiết kế các bộ chương trình 
phân tích cú pháp. Nó cũng được sử dụng để mô tả các khối cấu trúc trong các 
ngôn ngữ lập trình. Trong phần này chúng ta sử dụng cây dẫn xuất để biểu diễn cho 
ngôn ngữ phi ngữ cảnh. 
Trước tiên chúng ta nhắc lại định nghĩa của văn phạm phi ngữ cảnh. G là phi ngữ 
cảnh nếu mọi qui tắc dẫn xuất đều có dạng: 
 A , trong đó A VN và (VN  )
*
Ví dụ 5.1 Xây dựng một văn phạm phi ngữ cảnh G để sinh ra tất cả các số nguyên. 
Giải. Giả sử G = (VN, , P, S), trong đó 
 VN = {S, , , } 
  = {0, 1, 2, . . ., 9, +, - } 
 P bao gồm các qui tắc: S , 
 + | -, 
 | 
 0 | 1 | 2 | . . .| 9. 
Dễ dàng kiểm chứng được là L(G) là tập tất cả các số nguyên. 
Mỗi dẫn xuất của một văn phạm có thể biểu diễn dưới dạng một cây, dc gọi là cây 
dẫn xuất. 
Định nghĩa 5.1 Cây dẫn xuất (còn gọi là cây phân tích cú pháp) cho văn phạm phi 
ngữ cảnh G = (VN, , P, S) là cây thoả mãn các tính chất sau: 
(i) Các đỉnh đều được gán nhãn là biến, ký tự kết thúc hoặc , 
 Ôtômát và ngôn ngữ hình thức 
 - 110 - 
(ii) Gốc có nhãn S, 
(iii) Nhãn các đỉnh bên trong (không phải là lá) là các biến, 
(iv) Nếu các đỉnh n1, n2, ..., nk được viết với các nhãn X1, X2, ..., Xk là các con của 
đỉnh n có nhãn A thì trong P có tương ứng qui tắc A X1X2 ...Xk 
(v) Đỉnh n là lá nếu nhãn của nó là a  hoặc là ký hiệu rỗng . 
Ví dụ 5.2 Cho trước văn phạm G = ({S, A}, {a, b}, P, S), trong đó P gồm: 
 S aAS | a | SS, A SbA | ba 
Cây dẫn xuất của G để sinh ra xâu w = aabaa sẽ là: 
Hình H5-1 Cây dẫn xuất cho văn phạm G để sinh ra xâu w = aabaa 
Sắp xếp các đỉnh lá từ trái qua phải 
 + Các đỉnh con của đỉnh gốc được sắp xếp từ trái qua phải, nghĩa là các đỉnh ở 
mức 1 được sắp xếp từ bên trái, 
 + Nếu hai đỉnh v1, v2 ở mức 1 và v1 ở bên trái của v2 thì ta nói rằng v1 bên trái 
của tất cả các đỉnh con của v2 và các đỉnh con của v1 cũng là ở bên trái của v2, 
đồng thời cũng ở bên trái của các đỉnh con của v2. 
 + Lặp lại quá trình trên cho mức 2, 3, ..., k. 
Điều mà chúng ta quan tâm nhất là sự sắp xếp các lá của cây dẫn xuất. 
Ví dụ: trong cây ở Hình H5-1 thì các đỉnh lá được sắp xếp từ trái 10-4-7-8-9 cho 
giá trị là xâu aabaa và xâu này được sinh ra bởi G. 
Định nghĩa 5.2 Kết quả của một cây dẫn xuất là dãy ghép các nhãn của các đỉnh lá 
từ trái qua phải. 
Ví dụ: Kết quả của cây dẫn xuất ở Hình H5-1 là aabaa. 
Sử dụng các qui tắc của văn phạm G: 
 S SS aS aaAS aabaS aabaa 
Vậy kết quả của một cây dẫn xuất cũng là một từ được sinh ra bởi văn phạm G. 
Định nghĩa 5.3 Cây con của cây dẫn xuất T là một cây có 
(i) Gốc của nó là một đỉnh v của cây T, 
1 
S 
2 
S 
10 
a 
3 
S 
4 
a 
5 
A 
6 
S 
9 
a 
8 
a 
7 
b 
 Ôtômát và ngôn ngữ hình thức 
 - 111 - 
(ii) Các đỉnh của nó cũng là con cháu của v cùng với các nhãn tương ứng, 
(iii) Các cung nối các con cháu tương ứng của v. 
Ví dụ: cây trong hình H5-2 là cây con của cây ở hình H5-1 
Hình H5-2 Một cây con của cây T ở hình H5-1 
Lưu ý: Cây con cũng giống như cây dẫn xuất, chỉ khác nhau là nhãn của cây con có 
thể không phải là ký hiệu bắt đầu S. Nếu nhãn của gốc của cây con là A thì cây con 
đó được gọi là A-cây. 
Định lý 5.1 Giả sử G = (VN, , P, S) là văn phạm phi ngữ cảnh. Khi đó 
 S 
*
 khi và chỉ khi tồn tại cây dẫn xuất T của G để T có kết quả là . 
Chứng minh: 
Chỉ cần chứng minh rằng A 
*
 khi và chỉ khi A-cây có kết quả là . (4.17) 
Giả sử là kết quả A-cây T1. Chúng ta chứng minh A 
*
 bằng phương pháp qui 
nạp theo số các đỉnh bên trong của T1. 
Cơ sở qui nạp: Nếu T1 chỉ có một đỉnh bên trong, nghĩa là tất cả các đỉnh con của 
gốc đều là lá. Khi đó cây T1 có dạng: 
Hình H5-3 (a) A-Cây có một đỉnh bên trong 
Theo (iv) trong định nghĩa 5.1 suy ra A A1A2...Am = là một qui tắc trong G. 
Vậy A . 
Giả thiết qui nạp: Giả sử (4.17) đúng với các cây con có k – 1 đỉnh bên trong, k > 1. 
Chúng ta xét A-cây T1 có k đỉnh bên trong (k 2). Giả thiết gốc của T1 có v1, v2, ..., 
vm là các đỉnh con được gắn nhãn tương ứng X1, X2, ..., Xm. Theo (iv) trong định 
nghĩa 5.1 suy ra A X1X2...Xm là một qui tắc trong P. Do vậy, 
 A X1X2...Xm (4.18) 
Bởi vì k 2 nên trong số các đỉnh con của A có ít nhất một đỉnh là đỉnh bên trong. 
Nếu vi là một đỉnh bên trong thì lại xét tiếp cây con của T1 có gốc chính là v1. Hiển 
3 
S 
4 
a 
5 
A 
8 
a 
7 
b 
A 
A1 
Am 
A2 
. . . 
 Ôtômát và ngôn ngữ hình thức 
 - 112 - 
nhiên là số các đỉnh bên trong của cây con gốc vi là nhỏ hơn k, vậy theo giả thiết 
qui nạp suy ra Xi 
*
 i, Xi là nhãn của vi. 
Nếu vi không phải là đỉnh bên trong, thì Xi = i. 
Sử dụng (5.1) chúng ta nhận được: 
 A X1X2...Xm 
*
 1X2...Xm . . . 
*
 1 2 . . . m = 
Nghĩa là A 
*
 . 
Để chứng minh chiều ngược lại, chúng ta giả thiết rằng A 
*
 . Chúng ta đi xây 
dựng A-cây để có kết quả là . Thực hiện điều này bằng phương pháp qui nạp theo 
số bước trong dẫn xuất A 
*
 . 
Khi A , A là qui tắc trong P. Nếu = X1X2...Xm , A-cây cho kết quả có 
thể xây dựng dễ dàng và có dạng như hình H5-3 (b). 
Hình H5-3 (b) Cây dẫn xuất cho dẫn xuất một bước 
Giả sử dẫn xuất A 
*
 thực hiện qua k bước, k > 1. Khi đó ta có thể chia nó thành 
 A X1X2...Xm 
1 
k
 . Dẫn xuất A X1X2...Xm kéo theo A X1X2...Xm là 
một qui tắc trong P. Còn trong dẫn xuất X1X2...Xm 
1 
k
 thì: 
(i) Hoặc Xi không chuyển trạng thái suốt trong quá trình dẫn xuất, Xi = i 
(ii) Hoặc Xi biến đổi trong quá trình dẫn xuất. Giả sử i là xâu nhận được 
từ Xi, Xi
*
 i. 
Cây dẫn xuất cho kết quả = 1 2 . . . m được xây dựng như sau: 
 Khi A X1X2...Xm là một qui tắc trong P, ta xây dựng cây có m lá: X1, X2, 
..., Xm. Từ Xi suy dẫn ra i được thực hiện nhỏ hơn k bước, vậy theo giả thiết qui 
nạp thì Xi-cây sẽ cho kết quả là i. Do đó, A-cây sẽ cho kết quả là . 
Ví dụ 5.3 Xét văn phạm có các qui tắc S aAS | a, A SbA | SS | ba. Chỉ ra rằng 
S 
*
 aabbaa và xây dựng cây dẫn xuất để cho kết quả aabbaa. 
Giải: 
 S aAS aSbAS aabAS a2bbaS a2b2a2, nghĩa S 
*
 a
2
b
2
a
2
. 
A 
X1 
Xm 
 X2 
 Ôtômát và ngôn ngữ hình thức 
 - 113 - 
Cây dẫn xuất cho kết quả trên là: 
Hình H5-4 Cây dẫn xuất cho kết quả a2b2a2 
Trong các dẫn xuất ở trên chúng ta nhận thấy biến bên trái nhất luôn có thể áp dụng 
một qui tắc nào đó trong P để dẫn xuất tiếp. 
Định nghĩa 5.3 Dẫn xuất A 
*
 w là dẫn xuất trái nhất nếu chỉ áp dụng qui tắc dẫn 
xuất cho biến bên trái nhất trong mọi bước dẫn xuất. 
Định nghĩa 5.4 Dẫn xuất A 
*
 w là dẫn xuất phải nhất nếu chỉ áp dụng qui tắc dẫn 
xuất cho biến bên phải nhất trong mọi bước dẫn xuất. 
Lưu ý: Trong ví dụ 5.3, xét dẫn xuất S aAS, biến bên trái nhất của dẫn xuất này 
là A. Mặt khác trong G trên có qui tắc A SbA, áp dụng vào dẫn xuất ta có dẫn 
xuất trái nhất aAS aSbAS. 
Định lý 5.2 Nếu A 
*
 w là một dẫn xuất trong văn phạm phi ngữ cảnh G thì sẽ tồn 
tại một dẫn xuất trái nhất cho w. 
Chứng minh: 
Chúng ta chứng minh bằng qui nạp theo số bước dẫn xuất trong A 
*
 w. 
Bước cơ sở: Nếu chỉ dẫn xuất qua một bước thì A w, nghĩa là vế trái chỉ có một 
biến, suy ra đó là dẫn xuất trái nhất. 
Giả thiết: Định lý 5.2 đúng với k bước dẫn xuất, nghĩa là nếu A 
k
 w thì tồn tại 
dẫn xuất bên trái nhất để dẫn ra w. 
Xét A 
1 
k
w. Ta có thể chia dẫn xuất này thành A X1X2...Xm 
k
 w. Tương tự, có 
thể tách w = w1w2 . . .wm và Xi 
*
 wi qua nhiều nhất là k bước. Theo giả thiết qui 
nạp, tất cả các dẫn xuất Xi 
*
 wi đều tồn tại dẫn xuất bên trái nhất, do vậy: 
 A X1X2...Xm 
*
 w1X2...Xm 
*
 w1w2X3...Xm 
*
 w1w2...wm = w 
Hệ quả 5.1 Mọi cây dẫn xuất của w đều tạo ra dẫn xuất trái nhất của w. 
S 
a 
S 
X2 
 S 
b 
a 
A 
b
 X2 
a 
a 
 Ôtômát và ngôn ngữ hình thức 
 - 114 - 
Ví dụ 5.4 Cho trước văn phạm G có các qui tắc S 0B | 1A, A 0 | 0S | 1AA, 
B 1 | 1S | 0BB và cho biết w = 00110101. 
(i) Tìm dẫn xuất trái nhất, 
(ii) Tìm dẫn xuất phải nhất, 
(iii) Xác định cây dẫn xuất. 
Giải: 
(i) S 0B 00BB 0011S 02120B 021201S 0212010B 02120101 
(ii) S 0B 00BB 00B1S 02B10B 02B101S 02B1010B 
0
2
1B10101 02120101 
(iii) Cây dẫn xuất cho 02120101 là 
Hình H5-5 Cây dẫn xuất cho kết quả 02120101 
5.2 Sự nhập nhằng trong văn phạm phi ngữ cảnh 
Đôi khi chúng ta gặp phải sự nhập nhằng trong dẫn xuất các xâu trong một văn phạm G. 
Định nghĩa 5.5 w L(G) được gọi là nhập nhằng nếu tồn tại nhiều hơn một cây 
dẫn xuất sinh ra w (hoặc có nhiều hơn một dẫn xuất trái nhất). 
Ví dụ 5.4 Xét G = ({S}, {a, b, +, *}, P, S), trong đó P có S S + S | S * S | a | b. 
Có hai cây dẫn xuất cho a + a * b: 
Hình H5-6 Hai cây dẫn xuất cùng cho kết quả a + a * b 
0 
S 
B 
B 
 0 
1 
1 
S 
B
 X2 
S 
B 
1 
1 
0 
0 
 B 
S 
S 
S S 
 * 
 a 
S 
 + 
 a 
 b 
S 
S 
S 
 + 
* 
a 
S 
 a 
S 
 b 
 Ôtômát và ngôn ngữ hình thức 
 - 115 - 
Định nghĩa 5.6 Văn phạm phi ngữ cảnh G là nhập nhằng nếu có w L(G) là nhập 
nhằng. 
Ví dụ: Văn phạm ở ví dụ 5.4 là nhập nhằng. 
5.3 Giản lƣợc các văn phạm phi ngữ cảnh 
Trong văn phạm phi ngữ cảnh có thể có nhiều yếu tố dư thừa, ví dụ có những ký 
hiệu trong VN   không được sử dụng, không xuất hiện trong các qui tắc của P, 
hoặc có những qui tắc dạng A B chỉ làm mất thời gian suy diễn mà không cho 
được những thông tin gì mới. 
Ví dụ 5.5 Xét văn phạm G = ({S, A, B, C, E }, {a, b, c}, P, S), trong đó 
 P = {S AB, A a, B b, B C, E c | } 
Dễ nhận thấy là L(G) = {ab} và G có các dư thừa sau cần phải loại bỏ: 
(i) Những biến không dẫn ra các xâu kết thúc, ví dụ C. 
(ii) Những biến không xuất hiện ở vế phải, hoặc không xuất hiện ở vế trái 
của các qui tắc, ví dụ E không xuất hiện ở vế phải và không dẫn đến 
được từ ký hiệu bắt đầu S. 
(iii) Các qui tắc rỗng, ví dụ E . 
(iv) Các qui tắc dạng A B (suy diễn giữa hai biến với nhau), ví dụ 
B C. 
Văn phạm rút gọn sẽ là G = ({S, A, B}, {a, b}, P , S) với 
 P = {S AB, A a, B b} 
Hiển nhiên, L(G ) = L(G). 
Lưu ý: Những biến sau được gọi là các biến dư thừa 
 + Những biến không dẫn ra được xâu kết thúc được gọi là biến vô sinh. 
 + Những biến không dẫn xuất ra được từ S được gọi là không dẫn đến được. 
Vì lẽ đó cần loại bỏ các biến dư thừa mà không làm ảnh hưởng tới quá trình sinh ra 
các ngôn ngữ của văn phạm phi ngữ cảnh. 
5.3.1 Lƣợc giản các văn phạm phi ngữ cảnh 
Định lý 5.3 Nếu G là văn phạm phi ngữ cảnh và L(G)  thì có thể tìm được văn 
phạm G tương đương sao cho mọi biến trong G đều có thể dẫn xuất ra xâu kết 
thúc. 
Chứng minh: Cho văn phạm G = (VN, , P, S). 
Chúng ta định nghĩa G = (VN , , P , S) như sau: 
(i) Xây dựng VN . Định nghĩa Wi  VN bằng đệ qui: 
 + W1 = { A VN | nếu tồn tại A w và w 
*
} 
 Ôtômát và ngôn ngữ hình thức 
 - 116 - 
 + Wi +1 = Wi  { A VN | nếu tồn tại A và (  Wi )
*
} 
Theo định nghĩa đệ qui trên thì Wi  Wi +1 với mọi i. Bởi vì VN là hữu hạn, nên tồn 
tại k |VN| để Wi = Wi +1. Cuối cùng đặt VN = Wi . 
(ii) Kiến thiết P . P = {A | , (  VN )
*
}  P 
Chúng ta cần chỉ ra G chính là văn phạm cần tìm. 
Trước tiên, S thuộc VN , vì nếu S VN thì L(G) = , điều này mâu thuẫn với giả 
thiết là L(G) . 
Tiếp theo cần chứng minh: 
(i) Nếu A VN thì A 
*
'G
 w, w 
*
 và ngược lại nếu A 
*
G
 w thì A VN 
(ii) L(G ) = L(G). 
Để chứng minh (i) chúng ta lưu ý rằng Wk = W1  W2 ...  Wk. Chứng minh qui 
nạp theo i = 1, 2, ..., k, A Wi kéo theo A 
*
'G
 w với w 
*
. 
Nếu A W1 thì A w và w 
*, do đó A 
G
 w. Theo định nghĩa thì A w cũng 
thuộc P (cơ sở qui nạp đúng). 
Giả sử nó đúng với i < k. 
Xét A Wi +1. Theo định nghĩa thì 
+ Hoặc A Wi. Khi đó A 
*
'G
 w, w 
*
 theo giả thiết qui nạp. 
+ Hoặc tồn tại A và (  Wi )
*. Theo định nghĩa thì A sẽ 
thuộc P . Ta có thể viết = X1X2 ... Xm, Xj   Wi . Nếu Xj Wi thì theo 
giả thiết qui nạp suy ra Xj 
*
'G
 wj, wj 
*. Cuối cùng dẫn tới 
A 
*
'G
 w1w2 ...wm 
*
. 
Chiều ngược lại chứng minh tương tự qui nạp theo các bước suy dẫn trong dẫn 
xuất A 
G
 w. 
Để chứng minh (ii) thì chúng ta thấy ngay L(G )  L(G) bởi vì VN  VN và P  P. 
Chứng minh chiều ngược lại phải dựa vào bổ đề: 
 A 
*
'G
 w nếu A 
*
G
 w và w 
* 
(4.19)
Bổ đề này có thể chứng qui nạp theo số bước trong dẫn xuất A 
*
G
 w. 
Áp dụng (4.19) cho trường hợp A = S suy ra L(G)  L(G ) . 
Định lý 5.4 (Loại bỏ các ký hiệu không dẫn đến được) 
 Ôtômát và ngôn ngữ hình thức 
 - 117 - 
Cho trước văn phạm phi ngữ cảnh G = (VN, , P, S), chúng ta xây dựng văn phạm 
G = (VN ,  , P , S) tương đương sao cho với mọi ký hiệu X VN   đều tồn 
tại ,  VN   để S 
*
 X, nghĩa là mọi biến đều dẫn đến xâu kết thúc và 
xuất phát từ S. 
Chứng minh: G = (VN ,  , P , S) được xây dựng như sau 
 (a) Xây dựng Wi với i 1 
 + W1 = {S} 
 + Wi +1 = Wi  {X VN   | nếu tồn tại A và Wi và chứa X} 
Tương tự như trên Wi  VN   và Wi  Wi+1 nên sẽ tồn tại k để Wk = Wk+1. 
 + VN ,  , P được xây dựng như sau: 
 VN = VN  Wk,  =   Wk và P = {A | A P, A Wk} 
Với cách xây dựng chi tiết tương tự như trên, chúng ta có L(G ) = L(G). 
Định nghĩa 5.7 Văn phạm phi ngữ cảnh G = (VN, , P, S) được gọi là tối giản 
(không có ký hiệu dư thừa) nếu mọi ký hiệu trong VN   đều xuất hiện ít nhất 
trong một dẫn xuất dẫn đến xâu kết thúc. Nghĩa là, với mọi X trong VN  , tồn tại 
một dẫn xuất S 
*
 X 
*
 w L(G). 
Định lý 5.5 Với mọi văn phạm phi ngữ cảnh G luôn tồn tại văn phạm G tối giản 
tương đương. 
Chứng minh: Xây dựng văn phạm không dư thừa theo hai bước. 
Bước 1. Xây dựng văn phạm G1 tương đương với G sao cho mọi biến đều dẫn xuất 
ra các xâu kết thúc (định lý 5.3). 
Bước 2. Xây dựng G = (VN ,  , P , S) tương đương với G1 sao cho mọi ký hiệu 
trong VN   đều dẫn đến được (định lý (5.4). 
Ví dụ 5.6 Tìm văn phạm không dư thừa tương đương với văn phạm G có các qui 
tắc sau: 
 S AB | CA, B BC | AB, A a, C aB | b 
Giải: 
Bước 1. W1 = {A, C} bởi A a và C b 
 W2 = {A, C}  {A1 | A1 , (  {A, C}
*
} 
 = {A, C}  {S} bởi S CA 
 W3 = {A, C, S}  {A1 | A1 , (  {A, C, S}
*
} 
 = {A, C, S}   
Vậy W3 = W2. Do đó, 
 Ôtômát và ngôn ngữ hình thức 
 - 118 - 
 VN = W2 = {S, A, C} 
 P = {A1 , (VN  {a, b}
*
}  P 
 = {S CA, A a, C b} 
Kết thúc bước 1: G1 = {{S, A, C}, {a, b}, {S CA, A a, C b}, S} 
Bước 2. Áp dụng định lý 5.4 cho G1. 
 W1 = {S} 
 W2 = {S}  {A, C} bởi vì S CA và S W1. 
 W3 = {S, A, C}  {a, b} bởi vì A a, C b và A, C W2. 
Tương tự W4 = W3 = VN  , đồng thời P = {A1 | A1 , A1 W3} = P . 
Vậy, G = {{S, A, C}, {a, b}, {S CA, A a, C b}, S} là không dư thừa. 
5.3.2 Loại bỏ các qui tắc rỗng 
Văn phạm phi ngữ cảnh có thể có các qui tắc dạng A  được gọi là qui tắc rỗng. 
Qui tắc này chỉ sử ...  (n+1)
2, với k, n là không thể có. 
5.15 Điều kiện cần: L = L(G), G là chính qui. Với mọi biến A trong G, A 
*
 , suy 
ra = uB, với u * và B VN. Vậy, G không phải là văn phạm tự nhúng. 
Điều kiện đủ: giả sử G là văn phạm phi ngữ cảnh không tự nhúng. Xây dựng 
văn phạm G1 ở dạng GNF tương đương với G. Dễ dàng nhận thấy G1 là 
không tự nhúng. Đặt || = n và m là số ký hiệu cực đại của các vế phải trong 
các qui tắc trong G1. Giả sử VN
+. Quá trình áp dụng những dẫn xuất trái 
nhất ta có thể chỉ ra số các biến trong là nm. Ta định nghĩa 
 G2 = (VN
’, , P2, S2), trong đó 
 VN
’
 = {[ ] | | | nm và VN
+
} 
 S2 = [S1] 
 P2 = {[A] b[ ] | A b P1,  VN
’và | | nm 
Dễ dàng nhận thấy G2 là chính qui và L(G2) = L(G1) = L(G). 
 Ôtômát và ngôn ngữ hình thức 
 - 197 - 
Chƣơng 6 
6.1 (a) PDA đoán nhận {anbmcn | m, n 1} được định nghĩa như sau: 
A = ({q0, q1}, {a, b}, {a, Z0}, , q0, Z0, }, trong đó  được xác định như sau: 
 R1: (q0, a, Z0) = {(q0, aZ0)} 
 R2: (q0, a, a) = {(q0, aa)} 
 R3: (q0, b, a) = {(q1, a)} 
 R4: (q1, b, a) = {(q1, a)} 
 R5: (q1, a, a) = {(q1, )} 
 R6: (q1, , Z0) = {(q1, )} 
Bắt đầu vào từ việc xếp các ký hiệu a vào kho đẩy xuống cho đến khi gặp b 
(luật R1, R2). Khi b xuất hiện, ôtômát thay đổi trạng thái nhưng vẫn không 
thay đổi kho đẩy xuống (luật R3). Khi các ký hiệu b được đọc hết (luật R4), 
sau đó xoá đi các ký hiệu a (luật R5). 
Vậy, (q0, a
n
b
m
a
n
, Z0) ⊢
*
 (q1, , Z0) ⊢ (q1, , ), nghĩa là a
n
b
m
a
n
 N(A). 
Sau đó chứng minh N(A) = {anbman | m, n 1}. 
(b) Ôtômát PDA để đoán nhận {anb2n | n 1} được định nghĩa như sau: 
A = ({q0, q1, q2}, {a, b}, {a, Z0}, , q0, Z0, }, trong đó  được xác định bởi: 
 (q0, a, Z0) = {(q1, aZ0)}, (q1, a, a) = {(q1, aa)}, (q1, b, a) = {(q2, a)} 
 (q2, b, a) = {(q1, )}, (q1, , Z0) = {(q1, )}. 
(c) Ôtômát PDA để đoán nhận {ambmcn | m, n 1} được định nghĩa như sau: 
A = ({q0, q1}, {a, b, c}, {Z0, Z1}, , q0, Z0, }, trong đó  được xác định bởi: 
 (q0, a, Z0) = {(q0, Z1Z0)}, (q0, a, Z1) = {(q0, Z1Z1)}, 
(q0, b, Z1) = {(q1, )}, (q1, b, Z1) = {(q1, )}, 
(q1, c, Z0) = {(q1, Z0)}, (q1, , Z0) = {(q1, )}. 
6.3 (a) G = ({S, S1, S2}, {a, b}, P, S) để sinh ra {a
n
b
n
 | n 1}  {amb2m | m 1}, 
trong đó P có các qui tắc: S S1 | S2, S1 aS1b | ab, S2 aS2bb | abb. 
Ôtômát PDA để đoán nhận L(G) được định nghĩa như sau: 
A = ({q}, {a, b}, {S, S1, S2, a, b}, , q, S, }, trong đó  được xác định bởi: 
 (q, , S) = {(q, S1), (q, S2)}, 
(q, , S1) = {(q, aS1b), (q, ab)}, 
(q, , S2) = {(q, aS2bb), (q, abb)}, 
 Ôtômát và ngôn ngữ hình thức 
 - 198 - 
(q, a, a) = (q, b, b) = {(q, )}. 
6.4 Ôtômát PDA để đoán nhận L được định nghĩa như sau: 
A = ({q0, q1}, {a, b}, {Z0, a, b}, , q0, Z0, }, trong đó  được xác định bởi: 
 (q0, a, Z0) = {(q0, aZ0)}, (q0, b, Z0) = {(q0, bZ0)}, 
 (q0, a, b) = {(q0, ab)}, (q0, b, a) = {(q0, ba)}, 
(q0, a, a) = {(q0, aa), (q1, )}, 
(q0, b, b) = {(q0, bb), (q1, )}, 
(q0, , Z0) = {(q, aS2bb), (q, abb)}, 
(q1, a, a) = {(q1, )}, (q1, b, b) = {(q1, )} 
(q1, , Z0) = {(q1, )}. 
6.7 M = (Q, , , q0, F) là ôtômát hữu hạn đoán nhận ngôn ngữ tập chính qui. 
Định nghĩa PDA A = (Q, , {Z0}, 1, q0, Z0, F}, trong đó 1 được xác định 
bởi: 
 1(q, a, Z0) = {(q‟, Z0) } nếu (q, a) = q‟. 
 Dễ dàng chỉ ra rằng T(M) = T(A). 
6.8* (i) Văn phạm phi ngữ cảnh G để sinh ra L = {ancbmcdk | n > m > 0, k > 0} 
có các qui tắc: S AC, A aB, B aBb | aB | acb, C cD, D dD | d. 
 (ii) Dẫn xuất để sinh ra a3cb2cd2: S AC aBC a2BbC a3cb2C 
 a3cb2cD a3cb2cdD a3cb2cd2 
 (iii) Cây cú pháp của từ a3cb2cd2: 
 (iv) Ôtômát đẩy xuống M để đoán nhận L được định nghĩa như sau: 
M = ({q}, {a, b, c, d}, {A, B, C, D, a, b, c, d}, , q, S, }, với 
 (q, , S) = {(q, AC)}, (q, , A) = {(q, aB)}, 
 (q, , B) = {(q, ab), (q, acb), (q, aB)}, (q, , C) = {(q, cD)}, 
(q, , D) = {(q, dD), (q, d)}, 
S 
A C 
a B c 
a B b 
D 
d D 
a c b b 
 Ôtômát và ngôn ngữ hình thức 
 - 199 - 
(q, a, a) = (q, b, b) = (q, c, c) = (q, d, d) = {(q, )} 
Dễ dàng chỉ ra rằng N(M) = L(G). 
(iv) (q, a3cb2cd2, S) ⊢ (q, a3cb2cd2, AC) ⊢ (q, a3cb2cd2, aBC) 
⊢ (q, a2cb2cd2, BC) ⊢ (q, a2cb2cd2, aBC) ⊢* (q, , ). 
6.9* (i) Ngôn ngữ sinh L(G) = {wdwT | w {a, b, c}*, wT là đảo ngược của w} 
(ii) Ôtômát đẩy xuống M để đoán nhận L được định nghĩa như sau: 
M = ({q}, {a, b, c, d}, {S, a, b, c, d}, , q, S, }, với 
(q, , S) = {(q, aSa), (q, bSb), (q, cSc), (q, d)}, 
(q, a, a) = (q, b, b) = (q, c, c) = (q, d, d) = {(q, )} 
Dễ dàng chỉ ra rằng N(M) = L(G). 
(iii) w1 = aababbccdccbbabaa L(G) vì 
S aSa aaSaa aabSbaa aabaSabaa aababSbabaa 
 aababbSbbabaa aababbcScbbabaa aababbccSccbbabaa 
 aababbccdccbbabaa. 
Tương tự w1 L(M) vì 
(q, aababbccdccbbabaa, S) ⊢ (q, aababbccdccbbabaa, aSa) 
⊢ (q, ababbccdccbbabaa, Sa) ⊢ (q, ababbccdccbbabaa, aSaa) 
⊢ (q, babbccdccbbabaa, Saa) ⊢ (q, babbccdccbbabaa, bSbaa) 
⊢ (q, abbccdccbbabaa, Saa) ⊢ (q, abbccdccbbabaa, aSabaa) 
⊢* (q, , ). 
Nhưng w1 L(G) vì không có dãy chuyển trạng thái nào để sinh ra w1. Tương tự, 
không có dãy chuyển trạng thái nào trong M để chuyển w1 về được trạng thái kết 
thúc, w1 L(M). 
Chƣơng 7 
7.1 L(G) = {a
n+1
b
n
 | n 0}. Với từ dạng an+1bn, A a được áp dụng ở bước cuối 
khi a đứng trước ab. Vậy A a là qui tắc điều khiển khi và chỉ khi ký hiệu 
bên phải của a là b. Tương tự A aAb là qui tắc điều khiển khi và chỉ khi ký 
hiệu bên phải của aAb là b và S aAb là qui tắc điều khiển khi và chỉ khi ký 
hiệu bên phải của aAb là . Từ đó suy ra G là LR(1) và không phải là LR(0). 
7.2 Văn phạm G cho trước không phải là LR(k), k 0. Giả sử G là LR(k), với k 
nào đó. Hãy xét dẫn xuất phải nhất của 012k+12 và 012k+3: 
 Ôtômát và ngôn ngữ hình thức 
 - 200 - 
 S 
*
R
 01kA1k2 R 01
2k+1
2 w (A7.1) 
khi = 01k,  = A và w = 1k2. 
 S 
*
R
 01k+1A1k+12 R 01
2k+3
2 ’’w’ (A7.2) 
với ’ = 01k+1, ’= A, w’= 1k+12. Vì các xâu được tạo ra bởi 2k + 1 ký 
tự đầu tiên (lưu ý | | + k = 2k + 1) của w và ’’w’là một, = ’, 
nghĩa là 01k = 01k+1, dẫn đến mâu thuẫn. 
7.3 Văn phạm G là nhập nhằng vì ab có hai cây dẫn xuất, do đó không có một số 
nguyên k nào đó để văn phạm này là LR(k). 
7.4 Vì anbncn xuất hiện trong cả hai tập, do đó sẽ có hai cây dẫn xuất khác nhau. 
Vậy G là nhập nhằng, suy ra không phải là LR(k) với mọi k nguyên dương. 
Chƣơng 8 
8.2 Dãy tính toán đối với xâu con 12 của 1213 là 
q11213 ⊢ Bq2213 ⊢ BBq313. 
Vì (q3, 1) không xác định nên MT dừng. Đối với 2133, 312 thì máy Turing 
cho trước ở ví dụ 8.7 không bắt đầu được. 
8.3 Xây dựng M có ba trang thái: q0, q1, qf, trong đó q0 là trạng thái bắt đầu được 
sử dụng để ghi nhận chẵn số lần số 1 đã gặp và q1 được sử dụng để ghi nhận 
lẻ lần số 1 đã gặp, qf là trạng thái kết thúc. M được xác định bởi bảng chuyển 
trạng thái như sau: 
Trạng thái 0 1 B 
 q0 0Rq0 1Rq1 BRqf 
 q1 0Rq1 1Rq0 
 qf 
8.5 Máy Turing để đoán nhận tất cả các Palindrrome có độ dài chẵn trên tập {0, 1} được 
xây dựng như sau: 
(a) MT đọc ký tự vào từ băng vào (0 hoặc 1), xoá ký tự đó đi và chuyển sang 
trạng thái khác (q1 hoặc q2). 
(b) MT đọc phần còn lại và không thay đổi các ký hiệu trên băng cho đến khi 
gặp dấu trắng B. 
(c) Đầu đọc R/W chuyển sang trái. Nếu ký hiệu bên phải nhất phù hợp với ký 
hiệu bên trái nhất thì ký hiệu phải nhất được xoá đi, ngược lại MT dừng. 
 Ôtômát và ngôn ngữ hình thức 
 - 201 - 
(d) R/W chuyển sang trái cho đến khi gặp B. 
Bảng chuyển trạng thái mô tả hoạt động của MT: 
Trạng thái 
hiện thời 
Ký hiệu vào 
0 1 B 
q0 
q1 
q2 
q3 
q4 
q5 
q6 
q7 
 BRq1 BRq2 BRq1 
 0Rq1 1Rq1 BRq3 
 0Rq1 1Rq2 BRq4 
 BLq5 
 BLq6 
 0Lq5 1Lq5 BRq0 
 0Lq6 1Lq6 BRq0 
8.6 Giả sử bài toán giải được. Khi đó sẽ tồn tại thuật toán để quyết định được một 
từ cho trước có thuộc L hay không, nghĩa là có MT để đoán nhận L. Do vậy, 
sẽ tồn tại G để L(G) = L. Điều này suy ra w L(G) khi và chỉ khi MT là 
dừng với w, nghĩa là bài toán dừng của MT là giải được, dẫn đến mâu thuẫn. 
8.8 Giả sử S = {x | x là tập hợp và x x}. Nếu S là tập hợp thì S S hoặc S S. 
Nếu S S, theo định nghĩa của S thì S S. Ngược lại, nếu S S thì theo 
định nghĩa của S, S S. Do đó ta không thể khẳng định S S hay S S. 
8.9 Đặt  = {a}, x = (x1, , xn) và y = (y1, , yn), trong đó xi = i
k
a , i = 1, 2, , n 
và yj = 
jla , j = 1, 2, , n. Khi đó 
1)( 1
l
x 2)( 2
l
x ... nlnx )( = 
1)( 1
k
y 2)( 2
k
y  nkny )( . Bởi cả hai về đều bằng 
 iilka , 
nghĩa là PCP là giải được khi || = 1. 
8.11 x1 = 01, y1 = 011, x2 = 1, y2 = 10, x3 = 1 và y3 = 11. Vì |xi| < |yi|, với i = 1, 2, 3. 
Nên x
1i
 x
mi
 y
1i
 y
mi
, với mọi ij. Suy ra PCP không có lời giải. 
8.12 x1 = 0, y1 = 01, x2 = 110, y2 = 000, x3 = 001, y3 = 10. Ở đây tất cả các cặp 
(x1,y1), (x2,y2), (x3,y3) đều không có phần đầu (dãy con tiếp đầu ngữ) chung 
nhau. Vậy suy ra x
1i
 x
mi
 y
1i
 y
mi
, với mọi ij. Suy ra rằng PCP với S = 
{(0, 10), (110, 0
3
), (0
21, 10)} không có lời giải. 
 Ôtômát và ngôn ngữ hình thức 
 - 202 - 
Danh sách các từ viết tắt và thuật ngữ 
A. Các ký hiệu 
 Ký hiệu Ý nghĩa 
 a A a thuộc tập A 
 a A a không thuộc tập A 
A  B A là tập con của B 
  Tập rỗng, tập trống 
  Phần tử rống, phần tử trống 
 A  B Hợp của tập A và B 
 A  B Giao của tập A và B 
 A – B Hiệu của tập A và B 
 A
C
 Phần bù của tập A 
 2
A
 Tập tất cả các tập con của A 
 A B Tích Đề Các của tập A và B 
 Ca Lớp tương đương chứa a 
 R
+
 Bao đóng bắc cầu của A 
 R
*
 Bao đóng phản xạ, bắc cầu của A 
 R1R2 Hợp thành (ghép) của hai quan hệ R1 và R2 
  Hội mệnh đề, phép “và” logic, “AND” 
 Tuyển mệnh đề, phép “hoặc logic, “OR” 
P Q Phép keo theo, P suy ra Q 
 Phép phủ định logic 
 Phép đồng nhất 
 Lượng tử (lượng từ) phổ dụng: với mọi 
 Lượng tử (lượng từ) tồn tại 
 Quan hệ tương đương 
f: X Y Hàm f từ X sang Y 
 |x| Độ dài (số phần tử, cỡ) của xâu (dãy) x, 
(Q, , , q0, F) Một ôtômát hữu hạn 
 ⊢ Một phép chuyển trạng thái 
(VN, , P, S) Một văn phạm 
A Qui tắc, suy diễn trong văn phạm 
G
 Một dẫn xuất trong văn phạm G 
*
 Một dãy dẫn xuất của văn phạm 
 R1 + R2 Hợp của các biểu thức chính qui R1 và R2 
 R1R2 Ghép của các biểu thức chính qui R1 và R2 
 R1
*
 Bao đóng (lặp) của các biểu thức chính qui R1 và R2 
 Ôtômát và ngôn ngữ hình thức 
 - 203 - 
 a Biểu thức chính qui được biểu diễn bởi {a} 
 (Q, , , , q0, Z0, F) Một ôtômát đẩy xuống 
 ID Một mô tả, hiện trạng của PDA 
P Lớp các ngôn ngữ đoán nhận được bởi máy Turing đơn 
định với thời gian là đa thức, 
NP Lớp các ngôn ngữ đoán nhận được bởi máy Turing 
không đơn định với thời gian là đa thức, 
⋞p Phép dẫn đa thức 
B. Danh sách các thuật ngữ viết tắt 
 Từ viết tắt Ý nghĩa 
 MĐ Tập các mệnh đề 
 T Giá trị đúng (True) 
 F Giá trị sai (False) 
 ÔTKĐĐ Ôtômát hữu hạn không đơn định 
 ÔTĐĐ Ôtômát hữu hạn đơn định 
 VN Tập các ký hiệu không kết thúc, các biến 
  Tập các chữ cái, các ký hiệu kết thúc 
 L(G) Tập các xâu được sinh bởi văn phạm G 
 £0 Lớp tất cả các ngôn ngữ loại 0 
 £1 Lớp tất cả các ngôn ngữ loại 1 
 £2 Lớp tất cả các ngôn ngữ phi ngữ cảnh (loại 2) 
 £3 Lớp tất cả các ngôn ngữ chính qui (loại 3) 
 CNF Dạng chuẩn Chomsky 
 GNF Dạng chuẩn Greibach 
 PDA Ôtômát đẩy xuống 
 PDS Kho đẩy xuống 
 N(A) Tập đoán nhận bởi PDA với kho PDS rỗng 
 T(M) Tập các xâu đoán nhận được bởi ôtômát M 
 LL(k) Tập con của văn phạm phi ngữ cảnh, đọc 
 trước k ký tự ở phía trước 
LR(k) Tập con của văn phạm phi ngữ cảnh, đọc 
 các ký tự từ trái qua phải 
LBA Ôtômát tuyến tính giới nội 
 Ôtômát và ngôn ngữ hình thức 
 - 204 - 
PCP Bài toán tương ứng Post 
 CSG Văn phạm cảm ngữ cảnh, văn phạm loại 1 
 CSL Ngôn ngữ cảm ngữ cảnh, ngôn ngữ loại 1 
SAT Bài toán thoả của công thức mệnh đề 
C. Danh sách các thuật ngữ 
 Tiếng Anh Tiếng Việt 
 Absorption law Luật hấp thụ 
Associative laws Luật kết hợp 
Binary operation Phép toán nhị nguyên 
Bottom-up parsing Phân tích cú pháp dưới lên trên 
Commutative law Luật giao hoán 
Commutative ring Vành giao hoán 
Commutative ring with identity Vành giao hoán có đơn vị 
Computable function Hàm tính được 
Concatenation Ghép xâu 
Conjunctive normal form Dạng chuẩn hội 
Constructive dilemma Định đề kiến thiết 
Context-free grammar Văn phạm phi ngữ cảnh, văn phạm loại 2 
Context-sensitive grammar Văn phạm cảm ngữ cảnh, văn phạm loại 1 
Derivation Dẫn xuất, qui tắc 
Derivation tree (Parse tree) Cây dẫn xuất, cây phân tích cú pháp 
Deterministic finite automaton Ôtômát hữu hạn đơn định, ÔTĐĐ 
Disjunctive normal form Dạng chuẩn tuyển 
Disjunctive syllogism Tam đoạn luận 
Destructive dilemma Định đề đối thiết 
Distributive law Luật phân phối 
Emigroup Nửa nhóm 
Field Trường 
Finite automaton Ôtômát hữu hạn (trạng thái) 
Formula SATisfiability Bài toán thoả của công thức mệnh đề 
Group Nhóm 
 Handle Cán điều khiển, điều khiển 
Hypothetical syllogism Suy luận bắc cầu 
Idempotent law Luật luỹ đẳng 
B0011B 
⊢ 
Bx011B 
 Ôtômát và ngôn ngữ hình thức 
 - 205 - 
Instance Description Thể hiện, mô tả hiện trạng, ID 
Left to Right Trái qua phải, LR 
Linear Bounded Automata Ôtômát tuyến tính giới nội 
Monotonic Đơn điệu 
Nondeterministic finite automaton Ôtômát hữu hạn không đơn định, ÔTKĐĐ 
Normal Form Dạng chuẩn 
NP-completeness NP-đầy đủ 
Paradox Nghịch lý 
Post Correspondence Problem Bài toán tương ứng Post, PCP 
Predicate Tân từ, vị từ 
Principal conjunctive normal form Dạng chuẩn hội chính tắc 
Principal disjunctive normal form Dạng chuẩn tuyển chính tắc 
Proposition (Statement) Mệnh đề 
 Pumping lemma Bổ đề Bơm 
 Pushdown automaton Ôtômát đẩy xuống 
Pushdown store Kho đẩy xuống, ngăn xếp 
Quantifier Lượng tử 
Random Access Machine Máy truy cập ngẫu nhiên, RAM 
Recursive Đệ qui 
 Recursively enumerable Đệ qui đếm được, đệ qui kể được 
Reflexive Phản xạ 
Regular Expression Biểu thức chính qui 
Regular grammar Văn phạm chính qui, văn phạm loại 3 
 Regular Set Tập chính qui 
Ring Vành 
 Rule of inference Qui tắc suy diễn 
Self-embedding Tự nhúng 
Shift register Thanh ghi dịch chuyển 
String Xâu, dãy ký tự 
Symmetric Đối xứng 
 Tautology Công thức hằng đúng 
 Top-down parsing Phân tích cú pháp trên xuống 
Transition function Hàm chuyển trạng thái, hàm chuyển 
Transitive Bắc cầu 
 Transition system Hệ thống chuyển trạng thái, hay chuyển đổi 
 Well-formed formula Công thức (mệnh đề), biểu thức logic 
 Ôtômát và ngôn ngữ hình thức 
 - 206 - 
Tài liệu tham khảo 
[1] Ding-Zhu Du, Ker-I Ko, Theory of Computational Complexity, John Wiley & 
Sons, INC, 2000. 
[2] Hopcroft J. and Ullman J., Formal languages and their relation to automata, 
Addison Wesley, London, 1969. 
[3] Johnsonbaugh R., Discrete Mathematics, Macmillan Publishing Company, 
1992. 
[4] Mishra K. and Chandrasekaran, Theory of Computer Science (Automata, 
Languages and Computation), Prentice Hall, 2001. 
[5] Nguyễn Văn Ba, Ngôn ngữ hình thức, ĐH Bách Khoa Hà Nội, 1997. 
[6] Rosen K. H., Discrete Mathematics and Its Application, Mc Graw- Hill, NY 
1994.