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ú

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.

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ú trang 1

Trang 1

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ú trang 2

Trang 2

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ú trang 3

Trang 3

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ú trang 4

Trang 4

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ú trang 5

Trang 5

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ú trang 6

Trang 6

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ú trang 7

Trang 7

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ú trang 8

Trang 8

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ú trang 9

Trang 9

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ú trang 10

Trang 10

Tải về để xem bản đầy đủ

pdf 140 trang xuanhieu 3180
Bạn đang xem 10 trang mẫu của tài liệu "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ú", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

Tóm tắt nội dung tài liệu: 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ú

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 

File đính kèm:

  • pdfbai_giang_ngon_ngu_hinh_thuc_chuong_3_van_pham_phi_ngu_canh.pdf