Bài giảng Ngôn ngữ hình thức - Chương 3: Văn phạm phi ngữ cảnh và Automat đẩy xuống - Phạm Hùng Phú

 
| bA
2 
| a 
 A
3 
→ bA
2
A
3
A
4
 | 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 → A
4 
A
2
A
3 
| A
4 
A
2
A
3
B. 
Bước 5: Thay thế các B
- luật sinh về đúng dạng chuẩn. 
 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 
 Cuối cùng, ta thu đƣợc văn phạm có dạng GNF với các luật sinh. 
 A
1 
→ bA
2
A
3
A
4
A
2
A
3
 | aA
3
A
4
A
2
A
3 
| bA
2
A
3
BA
4
A
2
A
3
 | aA
3
BA
4
A
2
A
3 
| bA
2
A
3 
| 
aA
3 
| bA
2
A
3
A
4
A
4
 | aA
3
A
4
A
4 
| bA
2
A
3
BA
4
A
4
 | aA
3
BA
4
A
4 
| bA
4
; 
 A
2 
→ bA
2
A
3
A
4
A
2
 | aA
3
A
4
A
2 
| bA
2
A
3
BA
4
A
2
 | aA
3
BA
4
A
2 
| bA
2 
| a 
 A
3 
→ bA
2
A
3
A
4
 | 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