Ngôn ngữ hình thức - Chương 3: Văn phạm phi ngữ cảnh và automat đẩy xuống

Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống 
107 Phạm Hùng Phú 
Chƣơng 3. VĂN PHẠM PHI NGỮ CẢNH 
 VÀ AUTOMAT ĐẨY XUỐNG 
(Contexet free Grammar - CFG and push down Automata - PDA) 
 Mục tiêu: 
Giúp sinh viên có khả năng: 
- Hiểu đƣợc khái niệm và xác định đƣợc các thành phần của một CFG. 
- Nhận dạng đƣợc lớp ngôn ngữ phi ngữ cảnh (CFL) do văn phạm CFG sinh 
 ra và tính chất của CFL. 
- Xây dựng đƣợc các thành phần của CFG đặc tả một lớp CFL. 
- Hiểu và xây dựng đƣợc dẫn xuất và cây dẫn xuất. 
- Rút gọn và chuẩn hoá đƣợc CFG. 
- Hiểu đƣợc khái niệm và xác định đƣợc các thành phần của một PDA 
- Xây dựng đƣợc các thành phần của PDA đoán nhận ngôn ngữ sinh bởi 
 CFG và xây dựng đƣợc CFG sinh ra ngôn ngữ đƣợc đoán nhận bởi PDA. 
Nội dung chính: 
 - Văn phạm phi ngữ cảnh: định nghĩa, dẫn xuất và ngôn ngữ và cây dẫn xuất. 
 - Rút gọn văn phạm phi ngữ cảnh. 
 - Chuẩn hoá văn phạm phi ngữ cảnh. 
 - Tính chất của CFL. 
 - Automat đẩy xuống: định nghĩa, ngôn ngữ đoán nhận bởi PDA. 
 - Quan hệ của PDA và CFG. 
3.1. Văn phạm phi ngữ cảnh (CFG: Context Free Grammar) 
Xuất xứ của văn phạm phi ngữ cảnh là sự mô tả thông qua các ngôn ngữ tự 
nhiên. Ta có thể viết các quy tắc cú pháp để diễn tả câu “An là sinh viên giỏi“ nhƣ 
sau: 
 → 
 → 
 → 
 → 
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống 
Phạm Hùng Phú 108 
 → An 
 → sinh viên 
 → là 
 → giỏi 
Các từ trong cặp dấu nhƣ , , , ... là các 
phạm trù cú pháp, cho ta vai trò của các bộ phận hợp thành câu. Ta thấy một câu 
đƣợ sinh ra qua các bƣớc triển khai dần dần theo các quy tắc cú pháp. Đây cũng 
chính là dạng của các luật sinh trong văn phạm phi ngữ cảnh. Nhƣ vậy, văn phạm 
phi ngữ cảnh cũng có thể chọn làm mô hình cho các văn phạm của các ngôn ngữ tự 
nhiên. 
Tuy nhiên, trong khoa học máy tính, với nhu cầu biểu diễn các ngôn ngữ lập 
trình, văn phạm phi ngữ cảnh CFG còn đƣợc thiết kế thành một dạng tƣơng đƣơng 
gọi là văn phạm BNF (Backus - Naur Form). Đây cũng là văn phạm CFG với 
những thay đổi nhỏ về dạng thức và một số ký hiệu viết tắt mà các nhà khoa học 
máy tính thƣờng ứng dụng trong việc diễn tả cú pháp của các ngôn ngữ lập trình cấp 
cao (nhƣ ALGOL, PASCAL, ... ). Trong dạng thức của văn phạm BNF, ký hiệu::= 
đƣợc dùng thay cho ký hiệu →. Chẳng hạn, để định nghĩa một biểu thức số học 
(expression) bao gồm các danh biểu (identifier) tham gia vào các phép toán +, * 
hoặc biểu thức con lồng trong dấu ngoặc đơn , ta viết: 
::= + 
::= * 
::= ( ) 
::= 
Việc nghiên cứu các văn phạm phi ngữ cảnh đã tạo nên một cơ sở lý luận 
vững chắc cho việc biểu diễn ngôn ngữ lập trình, việc tìm kiếm các giải thuật phân 
tích cú pháp vận dụng trong chƣơng trình dịch và cho nhiều ứng dụng khác về xử lý 
xâu. Chẳng hạn, nó rất hữu ích trong việc mô tả các biểu thức số học với nhiều dấu 
ngoặc lồng nhau hoặc cấu trúc khối trong ngôn ngữ lập trình có cấu trúc mà biểu 
thức chính quy không thể đặc tả đƣợc. 
 Văn phạm phi ngữ cảnh là một tập hợp hữu hạn các biến (còn gọi là các ký 
hiệu chưa kết thúc), mỗi biến biểu diễn một ngôn ngữ. Ngôn ngữ đƣợc biểu diễn bởi 
Câu hỏi và bài tập chƣơng 3 
Phạm Hùng Phú 109 
các biến đƣợc mô tả một cách đệ quy theo thuật ngữ của một khái niệm khác gọi là 
ký hiệu kết thúc. Quy tắc quan hệ giữa các biến và các ký hiệu kết thúc đƣợc gọi là 
luật sinh. Mỗi luật sinh có dạng một biến ở vế trái sinh ra một xâu có thể gồm các 
biến lẫn các ký hiệu kết thúc trong văn phạm. 
3.1.1. Định nghĩa 
Văn phạm phi ngữ cảnh (CFG) là một hệ thống gồm bốn thành phần, ký hiệu 
là G = (N, T, P, S); trong đó: 
- N là tập hữu hạn các ký tự không kết thúc (hay các biến) ; 
- T là tập hữu hạn các ký tự kết thúc; N  T = ∅ ; 
- P là tập hữu hạn các luật sinh mà mỗi luật sinh có dạng A → α với A N và 
α (N  T)*; 
- S là một ký tự không kết thúc đặc biệt gọi là ký tự bắt đầu văn phạm. 
Ví dụ: Văn phạm phi ngữ cảnh G = (N, T, P, S); trong đó: 
 N = {S, A, B}; 
 T = {a, b}; 
 S = S; 
 P gồm các luật sinh sau: 
S → AB; 
A → aA; 
A → a; 
B → bB; 
B → b. 
Quy ƣớc ký hiệu: 
- Các chữ in hoa A, B, C, D, E, ... đầu bảng chữ cái La tinh và S ký hiệu cho 
các ký tự không kết thúc (S thƣờng đƣợc dùng làm ký tự bắt đầu ). 
- Các chữ nhỏ a, b, c, d, e, ..., các chữ số và một số ký tự khác ký hiệu cho 
các ký tự kết thúc. 
- Các chữ in hoa X, Y, Z ký hiệu cho các ký tự có thể kết thúc hoặc không 
kết thúc. 
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống 
Phạm Hùng Phú 110 
- Các chữ Hi-Lạp α, β, γ, ... ký hiệu cho các xâu gồm các ký tự kết thúc và 
không kết thúc. 
Ta sẽ biểu diễn văn phạm một cách tóm tắt bằng cách chỉ liệt kê các luật sinh 
của nó. Nếu A → α
1
; A → α
2 
; ... ; A → α
k 
là các luật sinh của biến A trong văn 
phạm nào đó, ta sẽ ghi ngắn gọn là A → α
1 
| α
2 
| ... | α
k 
Ví dụ: Văn phạm cho trong ví dụ trên có thể viết gọn là: 
S → AB; 
A → aA | a; 
B → bB | b‟ 
3.1.2. Dẫn xuất và ngôn ngữ 
1) Dẫn xuất 
Cho văn phạm CFG: G = (N, T, P, S), giả sử luật sinh A → β P và xâu 
αAγ (N T)*
 với α , β, γ (N T)*
. Nếu thay ký tự không kết thúc A trong xâu 
αAγ bằng xâu β để thu đƣợc xâu αβγ hay còn nói áp dụng luật sinh A → β vào xâu 
αAγ để thu đƣợc xâu αβγ; khi đó, ta nói rằng xâu αAγ dẫn xuất trực tiếp ra xâu αβγ 
hay xâu αβγ đƣợc dẫn xuất trực tiếp từ xâu αAγ trong văn phạm G và đƣợc ký hiệu 
là αAγ 
G 
αβγ. 
Giả sử α
1
, α
2
, ..., α
m 
là các xâu thuộc (N  T)* với m ≥ 1 và 
 α
1 
G 
α
2
; α
2 
G 
α
3
; ; α
m -1 
G 
α
m 
thì ta ký hiệu là α
1
* 
G 
α
m 
và nói là α
1 
dẫn xuất (không, một hoặc nhiều bƣớc) ra α
m 
hay α
m
đƣợc dẫn xuất từ α
1
trong văn phạm G. 
Nếu α
1
 dẫn xuất ra α
m
 bằng i bƣớc dẫn xuất thì ta ký hiệu là α
1
 i 
G
α
m
. 
Nếu α
1
 dẫn xuất ra α
m
 bằng một hoặc nhiều bƣớc dẫn xuất thì ta ký hiệu là 
α
1
 + 
G
α
m
. 
Chú ý rằng α * 
G 
α với mọi xâu α. và nếu α * 
G 
;  * 
G
 thì α * 
G 
 với 
mọi xâu α, , . 
Câu hỏ ... aA
3
A
4 
| bA
2
A
3
BA
4
 | aA
3
BA
4 
| b; 
 A
4 
→ bA
2
A
3
 | aA
3
| bA
2
A
3
B | aA
3
B; 
 B → bA
2
A
3
A
2
A
3
 | aA
3
A
2
A
3 
| bA
2
A
3
BA
2
A
3
 | aA
3
BA
2
A
3
 | bA
2
A
3
A
2
A
3
B| 
aA
3
A
2
A
3
B | bA
2
A
3
BA
2
A
3
B | aA
3
BA
2
A
3
B 
3.39. 1) - G = (N, T, P, S): 
Lời giải tóm tắt hoặc hƣớng dẫn 
Phạm Hùng Phú 238 
 N = {S, A, B}; T = {0, 1}; S = S; 
 P: S → BA | 0; A → SS | 1; B → AB | 0 | 1. 
 - G ở dạng chuẩn Chomsky 
 2) Biến đổi văn phạm trên về dạng chuẩn GREIBACH 
Bước 1: G đã thỏa mãn dạng chuẩn CNF và sinh ra CFL không chứa ε 
Bước 2: Ta có N = {S, A, B} = {A
1
, A
2
, A
3
} nên có tập luật sinh tƣơng ứng: 
 A
1
 → A
3
 A
2
 | 0; A
2
 → A
1
A
1
 | 1; A
3
 → A
2
 A
3
 | 0 | 1. 
Bước 3: Thay thế các luật sinh sao cho nếu A
i 
→ A
j 
γ là một luật sinh thì j > i. 
Trong tập luật sinh, các luật sinh cho A
1 
đã thỏa điều kiện j > i. Chỉ có các 
luật sinh A
2
 → A
1
A
1
 và A
3
 → A
2
 A
3
 cần biến đổi. 
Trƣớc hết biến đổi luật sinh A
2
 → A
1
A
1
|1, ta đƣợc A
2
 → A
3
A
2
A
1
| 0A
1
|1. 
Biến đổi luật sinh A
3
 → A
2
 A
3
 | 0 | 1, ta đƣợc 
 A
3
 → A
3
A
2
A
1
A
3
| 0A
1
A
3
|1A
3
 | 0 | 1 
Sau đó, loại bỏ đệ quy trái trực tiếp cho A
3 
luật sinh, ta đƣợc tập luật sinh 
mới có dạng nhƣ sau: 
 A
3 
→ 0A
1
A
3
|1A
3
 | 0 | 1| 0A
1
A
3
B |1A
3
B | 0B | 1B; 
 B → A
2
A
1
A
3 
| A
2
A
1
A
3
B. 
 Do đó, văn phạm có tập luật sinh: 
 A
1
 → A
3
 A
2
 | 0; 
 A
2
 → A
3
A
2
A
1
| 0A
1
|1; 
 A
3 
→ 0A
1
A
3
|1A
3
 | 0 | 1| 0A
1
A
3
B |1A
3
B | 0B | 1B; 
 B → A
2
A
1
A
3 
| A
2
A
1
A
3
B. 
Bước 4: Thay thế các A
i 
- luật sinh về đúng dạng chuẩn. 
Ta có, tất cả các A
3 
- luật sinh đã có dạng chuẩn. 
Thay thế các A
2
, A
1 
- luật sinh; ta thu đƣợc tập luật sinh mới nhƣ sau: 
 A
1
 → 0A
1
A
3
A
2
|1A
3
A
2
 | 0A
2
 | 1A
2
| 0A
1
A
3
BA
2
 |1A
3
BA
2
 | 0BA
2
 | 1BA
2
 | 0; 
Lời giải tóm tắt hoặc hƣớng dẫn 
Phạm Hùng Phú 239 
 A
2
 → 0A
1
A
3
A
2
A
1
|1A
3
A
2
A
1
 | 0A
2
A
1
 | 1A
2
A
1
| 0A
1
A
3
BA
2
A
1
 |1A
3
BA
2
A
1
 | 0B 
A
2
A
1
 | 1BA
2
A
1
| 0A
1
|1; 
 A
3 
→ 0A
1
A
3
|1A
3
 | 0 | 1| 0A
1
A
3
B |1A
3
B | 0B | 1B; 
 B → A
2
A
1
A
3 
| A
2
A
1
A
3
B. 
Bước 5: Thay thế các B
- luật sinh về đúng dạng chuẩn. 
 B → 0A
1
A
3
A
2
A
1
A
1
A
3
|1A
3
A
2
A
1
A
1
A
3
 | 0A
2
A
1
A
1
A
3
 | 1A
2
A
1
A
1
A
3
| 
0A
1
A
3
BA
2
A
1
A
1
A
3
 | 1A
3
BA
2
A
1
A
1
A
3
 | 0B A
2
A
1
A
1
A
3
 | 1BA
2
A
1
A
1
A
3
| 
0A
1
A
1
A
3
|1A
1
A
3 
|0A
1
A
3
A
2
A
1
A
1
A
3
B |1A
3
A
2
A
1
A
1
A
3
B | 0A
2
A
1
A
1
A
3
B| 
1A
2
A
1
A
1
A
3
B | 0A
1
A
3
BA
2
A
1
A
1
A
3
B | 1A
3
BA
2
A
1
A
1
A
3
B | 0B A
2
A
1
A
1
A
3
B| 
1BA
2
A
1
A
1
A
3
B | 0A
1
A
1
A
3
B |1A
1
A
3
B. 
 Cuối cùng, ta thu đƣợc văn phạm có dạng GNF với các luật sinh. 
 A
1
 → 0A
1
A
3
A
2
|1A
3
A
2
 | 0A
2
 | 1A
2
| 0A
1
A
3
BA
2
 |1A
3
BA
2
 | 0BA
2
 | 1BA
2
 | 0; 
 A
2
 → 0A
1
A
3
A
2
A
1
|1A
3
A
2
A
1
 | 0A
2
A
1
 | 1A
2
A
1
| 0A
1
A
3
BA
2
A
1
 |1A
3
BA
2
A
1
 | 
0B A
2
A
1
 | 1BA
2
A
1
| 0A
1
|1; 
 A
3 
→ 0A
1
A
3
|1A
3
 | 0 | 1| 0A
1
A
3
B |1A
3
B | 0B | 1B; 
 B → 0A
1
A
3
A
2
A
1
A
1
A
3
|1A
3
A
2
A
1
A
1
A
3
 | 0A
2
A
1
A
1
A
3
 | 1A
2
A
1
A
1
A
3
| 
0A
1
A
3
BA
2
A
1
A
1
A
3
 | 1A
3
BA
2
A
1
A
1
A
3
 | 0B A
2
A
1
A
1
A
3
 | 1BA
2
A
1
A
1
A
3
| 
0A
1
A
1
A
3
|1A
1
A
3 
|0A
1
A
3
A
2
A
1
A
1
A
3
B |1A
3
A
2
A
1
A
1
A
3
B | 0A
2
A
1
A
1
A
3
B| 
1A
2
A
1
A
1
A
3
B | 0A
1
A
3
BA
2
A
1
A
1
A
3
B | 1A
3
BA
2
A
1
A
1
A
3
B | 0B A
2
A
1
A
1
A
3
B| 
1BA
2
A
1
A
1
A
3
B | 0A
1
A
1
A
3
B |1A
1
A
3
B. 
3.40. - w = aaaabbbbbb 
 (q
0
, aaaabbbbbb, Z0) ⊢ (q
0
, aaabbbbbb, XXX) ⊢ (q
0
, aabbbbbb, XXXX) ⊢ 
 (q
0
, abbbbbb, XXXXX) ⊢ (q
0
, bbbbbb, XXXXXX) ⊢ (q
1
, bbbbb, XXXXX) 
 ⊢ (q
1
, bbbb, XXXX) ⊢ (q
1
, bbb, XXX) ⊢ (q
1
, bb, XX) ⊢ (q
1
, b, X) ⊢ (q
2
, , Y) 
Lời giải tóm tắt hoặc hƣớng dẫn 
Phạm Hùng Phú 240 
 ⊢ (q
1
, , ) w L(M) và đƣợc đoán nhận bởi stack rỗng. 
 - aabbb 
 (q
0
, aabbb, Z0) ⊢ (q
0
, abbb, XXX) ⊢ (q
0
, bbb, XXXX) ⊢ 
 (q
1
, bb, XXX) ⊢ (q
1
, b, XX) ⊢ (q
1
, , X): Không chấp nhận 
 ┬ ┬ 
 (q
2
, b, YXX): Không chấp nhận (q
2
, b, YX): Không chấp nhận 
3.41. - w = aaaabbbbbb 
 (q
0
, aaaabbbbbb, Z0) ⊢ (q
0
, aaabbbbbb, XXX) ⊢ (q
0
, aabbbbbb, XXXX) ⊢ 
 (q
0
, abbbbbb, XXXXX) ⊢ (q
0
, bbbbbb, XXXXXX) ⊢ (q
1
, bbbbb, XXXXX) ⊢ 
 (q
1
, bbbb, XXXX) ⊢ (q
1
, bbb, XXX) ⊢ (q
1
, bb, XX) ⊢ (q
1
, b, X) ⊢ 
 (q
2
, , Y) w L(M) và đƣợc đoán nhận bằng trạng thái kết thúc. 
 - w = aabbb (tƣơng tự - tự làm) 
3.42. Sử dụng ứng dụng của bổ đề Bơm đối với văn phạm phi ngữ cảnh để chứng 
minh (tƣơng tự ví dụ 1) 
3.43. Viết hai thủ tục, sử dụng các giải thuật: 
 - Loại bỏ các biến không sinh ra xâu các ký tự kết thúc; 
 - Loại bỏ các ký hiệu không đƣợc sinh ra từ ký tự bắt đầu. 
3.44. Viết hai thủ tục, sử dụng các giải thuật: 
 - Loại bỏ các luật sinh ; 
 - Loại bỏ các luật sinh đơn vị. 
3.45. Viết thủ tục, sử dụng giải thuật: biến đổi CFG về CNF 
3.46. Viết hai thủ tục, sử dụng các giải thuật: 
 - Biến đổi CFG về CNF 
 - Biến đổi CFG về GNF 
3.47. 1) S → +SS | *SS | a. 
 Ta có: CFG G = (N, T, P, S); 
 N = {S}; T = {+, *, a}; S = S; P: S → +SS | *SS | a. 
Lời giải tóm tắt hoặc hƣớng dẫn 
Phạm Hùng Phú 241 
 PDA tƣơng đƣơng M =
<Q, Σ, Γ, δ, q
0
, Z
0
,  >: 
 - Q = {q}; 
 - Σ = {+, *, a}; 
 - Γ = {S}; 
 - q
0 
= q; 
 - Z
0 
= S; 
 - δ: 
 1. δ (q, +, S) = (q, SS) vì S → +SS; 
 2. δ (q, *, S) = (q, SS) vì S → *SS; 
 3. δ (q, a, S) = (q, ) vì S → a. 
 2) S → aS | bS | aA; A → bB| b; B → aC; C → b. 
 Ta có: CFG G = (N, T, P, S); 
 N = {S, A, B, C}; T = {a, b}; S = S; 
 P: S → aS | bS | aA; A → bB| b; B → aC; C → b. 
 PDA tƣơng đƣơng M =
<Q, Σ, Γ, δ, q
0
, Z
0
,  >: 
 - Q = {q}; 
 - Σ = {a, b}; 
 - Γ = {{S, A, B, C}; 
 - q
0 
= q; 
 - Z
0 
= S; 
 - δ: 
 1. δ (q, a, S) = {(q, S), (q, A)} vì S → aS | aA; 
 2. δ (q, b, S) = (q, S) vì S → bS; 
 3. δ (q, a, B) = (q, C) vì B → aC; 
 4. δ (q, b, C) = (q, ) vì C → b. 
3.48. 1) Tập hợp {a
n
b
n 
| n ≥ 0} 
 - Đƣa văn phạm phi ngữ cảnh G sinh ra ngôn ngữ (xem bài tập trƣớc); 
 - Chuyển G về dạng chuẩn Greibach; 
- Áp dụng giải thuật xây dựng PDA biết CFG. 
Lời giải tóm tắt hoặc hƣớng dẫn 
Phạm Hùng Phú 242 
2) Tập hợp {a
m
b
n 
| m, n > 0} 
 - Đƣa văn phạm phi ngữ cảnh G sinh ra ngôn ngữ (xem bài tập trƣớc); 
 - Chuyển G về dạng chuẩn Greibach; 
 - Áp dụng giải thuật xây dựng PDA biết CFG. 
3) Tập hợp {a
i
ca
j 
| i, j ≥ 0} 
 - Đƣa văn phạm phi ngữ cảnh G sinh ra ngôn ngữ (xem bài tập trƣớc); 
 - Chuyển G về dạng chuẩn Greibach; 
 - Áp dụng giải thuật xây dựng PDA biết CFG. 
 4) {0
m 
1
m 
2
n 
| m, n ≥ 1} 
 - Đƣa văn phạm phi ngữ cảnh G sinh ra ngôn ngữ (xem bài tập trƣớc); 
 - Chuyển G về dạng chuẩn Greibach; 
 - Áp dụng giải thuật xây dựng PDA biết CFG. 
 5) { a
m 
b
m
c
n 
d
n 
| m, n ≥ 0} 
 - Đƣa văn phạm phi ngữ cảnh G sinh ra ngôn ngữ (xem bài tập trƣớc); 
 - Chuyển G về dạng chuẩn Greibach; 
 - Áp dụng giải thuật xây dựng PDA biết CFG. 
3.49. 1) G = (N, T, P, S): 
 - N = { S, [q
0
, X, q
0
], [q
0
, X, q
1
], [q
1
, X, q
0
], [q
1
, X, q
1
], 
 [q
0
, Z
0
, q
0
], [q
0
, Z
0
, q
1
], [q
1
, Z
0
, q
0
], [q
1
, Z
0
, q
1
]}; 
 - T = {0, 1}; 
- S = S (ký tự mới thêm vào) 
 - Tập luật sinh P chứa các luật sinh có dạng: 
 + S → [q
0
, Z
0
, q
0
] | [q
0
, Z
0
, q
1
]; 
Các luật sinh cho các biến khác trong N đƣợc xây dựng từ các hàm chuyển 
của PDA nhƣ sau: 
- Vì δ(q
0
, 1, Z
0
) = {(q
0
, XZ
0
)} nên 
 + [q
0
, Z
0
, q
0
] → 1 [q
0
, X, q
0
][q
0
, Z
0
, q
0
] | 1 [q
0
, X, q
1
][q
1
, Z
0
, q
0
]; 
 + [q
0
, Z
0
, q
1
] → 1 [q
0
, X, q
0
][q
0
, Z
0
, q
1
] | 1 [q
0
, X, q
1
][q
1
, Z
0
, q
1
]. 
 - Vì δ(q
0
, 1, X) = {(q
0
, XX)} nên 
Lời giải tóm tắt hoặc hƣớng dẫn 
Phạm Hùng Phú 243 
 + [q
0
, X, q
0
] → 1[q
0
, X, q
0
][q
0
, X, q
0
] | 1[q
0
, X, q
1
][q
1
, X, q
0
]; 
 + [q
0
, X, q
1
] → 1[q
0
, X, q
0
][q
0
, X, q
1
] | 1[q
0
, X, q
1
][q
1
, X, q
1
]. 
 - Vì δ(q
0
, 1, X) = {(q
1
, ε)} nên [q
0
, X, q
1
] → 1. 
 - Vì δ(q
1
, 1, X) = {(q
1
, ε)} nên [q
1
, X, q
1
] → 1. 
 - Vì δ(q
1
, ε, X) = {(q
1
, ε)} nên [q
1
, X, q
1
] → ε. 
 - Vì δ(q
1
, ε, Z
0
) = {(q
1
, ε)} nên [q
1
, Z
0
, q
1
] → ε. 
2) G = (N, T, P, S): 
 - N = { S, [q
0
, X, q
0
], [q
0
, X, q
1
], [q
1
, X, q
0
], [q
1
, X, q
1
], 
 [q
0
, Z
0
, q
0
], [q
0
, Z
0
, q
1
], [q
1
, Z
0
, q
0
], [q
1
, Z
0
, q
1
]}; 
 - T = {0, 1}; 
- S = S (ký tự mới thêm vào) 
 - Tập luật sinh P chứa các luật sinh có dạng: 
 + S → [q
0
, Z
0
, q
0
] | [q
0
, Z
0
, q
1
]; 
Các luật sinh cho các biến khác trong N đƣợc xây dựng từ các hàm chuyển 
của PDA nhƣ sau: 
- Vì δ(q
0
, 1, Z
0
) = {(q
0
, XZ
0
)} nên 
 + [q
0
, Z
0
, q
0
] → 1 [q
0
, X, q
0
][q
0
, Z
0
, q
0
] | 1 [q
0
, X, q
1
][q
1
, Z
0
, q
0
]; 
 + [q
0
, Z
0
, q
1
] → 1 [q
0
, X, q
0
][q
0
, Z
0
, q
1
] | 1 [q
0
, X, q
1
][q
1
, Z
0
, q
1
]. 
 - Vì δ(q
0
, 1, X) = {(q
0
, XX)} nên 
 + [q
0
, X, q
0
] → 1[q
0
, X, q
0
][q
0
, X, q
0
] | 1[q
0
, X, q
1
][q
1
, X, q
0
]; 
 + [q
0
, X, q
1
] → 1[q
0
, X, q
0
][q
0
, X, q
1
] | 1[q
0
, X, q
1
][q
1
, X, q
1
]. 
 - Vì δ(q
0
, 0, X) = {(q
1
, X)} nên 
 + [q
0
, X, q
0
] → 0[q
1
, X, q
0
]; 
 + [q
0
, X, q
1
] → 0[q
1
, X, q
1
]. 
 - Vì δ(q
0
, ε, Z
0
) = {(q
0
, ε)} nên [q
0
, Z
0
, q
0
] → ε. 
 - Vì δ(q
1
, 1, X) = {(q
1
, ε)} nên [q
1
, X, q
1
] → 1. 
 - Vì δ(q
1
, 0, Z
0
) = {(q
0
, Z
0
)} nên 
Lời giải tóm tắt hoặc hƣớng dẫn 
Phạm Hùng Phú 244 
 + [q
1
, Z
0
, q
0
] → 0[q
0
, Z
0
, q
0
]; 
 + [q
1
, Z
0
, q
1
] → 0[q
0
, Z
0
, q
1
]. 
 3) G = (N, T, P, S): 
 - N = { S, [q
0
, X, q
0
], [q
0
, X, q
1
], [q
1
, X, q
0
], [q
1
, X, q
1
], 
 [q
0
, Z
0
, q
0
], [q
0
, Z
0
, q
1
], [q
1
, Z
0
, q
0
], [q
1
, Z
0
, q
1
]}; 
 - T = {a, b, c}; 
- S = S (ký tự mới thêm vào) 
 - Tập luật sinh P chứa các luật sinh có dạng: 
 + S → [q
0
, Z
0
, q
0
] | [q
0
, Z
0
, q
1
]; 
Các luật sinh cho các biến khác trong N đƣợc xây dựng từ các hàm chuyển 
của PDA nhƣ sau: 
 - Vì δ(q
0
, a, Z
0
) = {(q
0
, X)} nên 
 + [q
0
, Z
0
, q
0
] → a[q
0
, X, q
0
]; 
 + [q
0
, Z
0
, q
1
] → a[q
0
, X, q
1
]. 
 - Vì δ(q
0
, a, X) = {(q
0
, XX)} nên 
 + [q
0
, X, q
0
] → a [q
0
, X, q
0
][q
0
, X, q
0
] | a [q
0
, X, q
1
][q
1
, X, q
0
]; 
 + [q
0
, X, q
1
] → a [q
0
, X, q
0
][q
0
, X, q
1
] | a [q
0
, X, q
1
][q
1
, X, q
1
]. 
 - Vì δ(q
0
, c, X) = {(q
1
, X)} nên 
 + [q
0
, X, q
0
] → c[q
1
, X, q
0
]; 
 + [q
0
, X, q
1
] → c[q
1
, X, q
1
]. 
 - Vì δ(q
0
, b, Z
0
) = {(q
0
, X)} nên 
 + [q
0
, Z
0
, q
0
] → b[q
0
, X, q
0
]; 
 + [q
0
, Z
0
, q
1
] → b[q
0
, X, q
1
]. 
 - Vì δ(q
0
, b, X) = {(q
0
, XX)} nên 
 + [q
0
, X, q
0
] → b[q
0
, X, q
0
][q
0
, X, q
0
] | b[q
0
, X, q
1
][q
1
, X, q
0
]; 
 + [q
0
, X, q
1
] → b[q
0
, X, q
0
][q
0
, X, q
1
] | b[q
0
, X, q
1
][q
1
, X, q
1
]. 
 - Vì δ(q
1
, c, X) = {(q
1
, ε)} nên [q
1
, X, q
1
] → c. 
Lời giải tóm tắt hoặc hƣớng dẫn 
Phạm Hùng Phú 245 
3.50. G = (N, T, P, S): 
 - N = { S, [q
0
, X, q
0
], [q
0
, X, q
1
], [q
0
, X, q
2
], [q
1
, X, q
0
], [q
1
, X, q
1
], 
 [q
1
, X, q
2
], [q
2
, X, q
0
], [q
2
, X, q
1
], [q
2
, X, q
2
], 
 [q
0
, Y, q
0
], [q
0
, Y, q
1
], [q
0
, Y, q
2
], [q
1
, Y, q
0
], [q
1
, Y, q
1
], 
 [q
1
, Y, q
2
], [q
2
, Y, q
0
], [q
2
, Y, q
1
], [q
2
, Y, q
2
], 
 [q
0
, Z0, q
0
], [q
0
, Z0, q
1
], [q
0
, Z0, q
2
], [q
1
, Z0, q
0
], [q
1
, Z0, q
1
], 
 [q
1
, Z0, q
2
], [q
2
, Z0, q
0
], [q
2
, Z0, q
1
], [q
2
, Z0, q
2
], 
 - T = {a, b}; 
- S = S (ký tự mới thêm vào) 
 - Tập luật sinh P chứa các luật sinh có dạng: 
 + S → [q
0
, Z
0
, q
0
] | [q
0
, Z
0
, q
1
] | [q
0
, Z
0
, q
2
]; 
Các luật sinh cho các biến khác trong N đƣợc xây dựng từ các hàm 
chuyển của PDA (tự làm, tƣơng tự các bài tập trên). 
Tài liệu tham khảo 
246 Phạm Hùng Phú 
TÀI LIỆU THAM KHẢO 
[1]. Phan Đình Diệu - Lý thuyết Automat và thuật toán - Nhà xuất bản Đại Học 
và Trung Học chuyên nghiệp - 1997. 
[2]. Hồ Văn Quân – Giáo trình lý thuyết ôtômát và ngôn ngữ hình thức – Nhà 
xuất bản Đại học quốc gia Tp. Hồ Chí Minh – 2002. 
[3]. Đặng Huy Ruận - Lý thuyết ngôn ngữ hình thức và otomat - Đại học Quốc 
gia Hà Nội - 2002 . 
[4]. Nguyễn Văn Xuất - Automat ngôn ngữ hình thức và nguyên lý chƣơng trình 
dịch - Nhà xuất bản thống kê - 2005. 
[5]. John E. Hopcroft, Jeffrey D.Ullman – Introduction to Automata Theory, Languages 
and Computation – Addison – Wesley Publishing Company, Inc – 1979 . 
1