PDA tương đương M = <Q, Σ, Γ, δ, q , Z , >:
0 0
- Q = {q};
- Σ = {+, *, a};
- Γ = {S};
- q = q;
0
- Z = S;
0
Có thể bạn quan tâm!
Xem toàn bộ 254 trang tài liệu này.
- δ:
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 , Z , >:
0 0
- Q = {q};
- Σ = {a, b};
- Γ = {{S, A, B, C};
- q = q;
0
- Z = S;
0
- δ:
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 {anbn | 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.
m n
2) Tập hợp {a b | 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.
i j
3) Tập hợp {a ca | 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.
m m n
4) {0 1 2
| 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.
m m n n
5) { a b c d
| 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, [q0, X, q0], [q0, X, q1], [q1, X, q0], [q1, X, q1],
[q0, Z0, q0], [q0, Z0, q1], [q1, Z0, q0], [q1, Z0, q1]};
- 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 → [q0, Z0, q0] | [q0, Z0, q1];
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ì δ(q0, 1, Z0) = {(q0, XZ0)} nên
+ [q0, Z0, q0] → 1 [q0, X, q0][q0, Z0, q0] | 1 [q0, X, q1][q1, Z0, q0];
+ [q0, Z0, q1] → 1 [q0, X, q0][q0, Z0, q1] | 1 [q0, X, q1][q1, Z0, q1].
- Vì δ(q0, 1, X) = {(q0, XX)} nên
+ [q0, X, q0] → 1[q0, X, q0][q0, X, q0] | 1[q0, X, q1][q1, X, q0];
+ [q0, X, q1] → 1[q0, X, q0][q0, X, q1] | 1[q0, X, q1][q1, X, q1].
- Vì δ(q0, 1, X) = {(q1, ε)} nên [q0, X, q1] → 1.
- Vì δ(q1, 1, X) = {(q1, ε)} nên [q1, X, q1] → 1.
- Vì δ(q1, ε, X) = {(q1, ε)} nên [q1, X, q1] → ε.
- Vì δ(q1, ε, Z0) = {(q1, ε)} nên [q1, Z0, q1] → ε.
2) G = (N, T, P, S):
- N = { S, [q0, X, q0], [q0, X, q1], [q1, X, q0], [q1, X, q1],
[q0, Z0, q0], [q0, Z0, q1], [q1, Z0, q0], [q1, Z0, q1]};
- 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 → [q0, Z0, q0] | [q0, Z0, q1];
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ì δ(q0, 1, Z0) = {(q0, XZ0)} nên
+ [q0, Z0, q0] → 1 [q0, X, q0][q0, Z0, q0] | 1 [q0, X, q1][q1, Z0, q0];
+ [q0, Z0, q1] → 1 [q0, X, q0][q0, Z0, q1] | 1 [q0, X, q1][q1, Z0, q1].
- Vì δ(q0, 1, X) = {(q0, XX)} nên
+ [q0, X, q0] → 1[q0, X, q0][q0, X, q0] | 1[q0, X, q1][q1, X, q0];
+ [q0, X, q1] → 1[q0, X, q0][q0, X, q1] | 1[q0, X, q1][q1, X, q1].
- Vì δ(q0, 0, X) = {(q1, X)} nên
+ [q0, X, q0] → 0[q1, X, q0];
+ [q0, X, q1] → 0[q1, X, q1].
- Vì δ(q0, ε, Z0) = {(q0, ε)} nên [q0, Z0, q0] → ε.
- Vì δ(q1, 1, X) = {(q1, ε)} nên [q1, X, q1] → 1.
- Vì δ(q1, 0, Z0) = {(q0, Z0)} nên
+ [q1, Z0, q0] → 0[q0, Z0, q0];
+ [q1, Z0, q1] → 0[q0, Z0, q1].
3) G = (N, T, P, S):
- N = { S, [q0, X, q0], [q0, X, q1], [q1, X, q0], [q1, X, q1],
[q0, Z0, q0], [q0, Z0, q1], [q1, Z0, q0], [q1, Z0, q1]};
- 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 → [q0, Z0, q0] | [q0, Z0, q1];
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ì δ(q0, a, Z0) = {(q0, X)} nên
+ [q0, Z0, q0] → a[q0, X, q0];
+ [q0, Z0, q1] → a[q0, X, q1].
- Vì δ(q0, a, X) = {(q0, XX)} nên
+ [q0, X, q0] → a [q0, X, q0][q0, X, q0] | a [q0, X, q1][q1, X, q0];
+ [q0, X, q1] → a [q0, X, q0][q0, X, q1] | a [q0, X, q1][q1, X, q1].
- Vì δ(q0, c, X) = {(q1, X)} nên
+ [q0, X, q0] → c[q1, X, q0];
+ [q0, X, q1] → c[q1, X, q1].
- Vì δ(q0, b, Z0) = {(q0, X)} nên
+ [q0, Z0, q0] → b[q0, X, q0];
+ [q0, Z0, q1] → b[q0, X, q1].
- Vì δ(q0, b, X) = {(q0, XX)} nên
+ [q0, X, q0] → b[q0, X, q0][q0, X, q0] | b[q0, X, q1][q1, X, q0];
+ [q0, X, q1] → b[q0, X, q0][q0, X, q1] | b[q0, X, q1][q1, X, q1].
- Vì δ(q1, c, X) = {(q1, ε)} nên [q1, X, q1] → c.
3.50. G = (N, T, P, S):
- N = { S, [q , X, q ], [q , X, q ], [q , X, q ], [q , X, q ], [q , X, q ],
0 0 0 1 0 2 1 0 1 1
[q , X, q ], [q , X, q ], [q , X, q ], [q , X, q ],
1 2 2 0 2 1 2 2
[q , Y, q ], [q , Y, q ], [q , Y, q ], [q , Y, q ], [q , Y, q ],
0 0 0 1 0 2 1 0 1 1
[q , Y, q ], [q , Y, q ], [q , Y, q ], [q , Y, q ],
1 2 2 0 2 1 2 2
[q , Z0, q ], [q , Z0, q ], [q , Z0, q ], [q , Z0, q ], [q , Z0, q ],
0 0 0 1 0 2 1 0 1 1
[q , Z0, q ], [q , Z0, q ], [q , Z0, q ], [q , Z0, q ],
1 2 2 0 2 1 2 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 → [q0, Z0, q0] | [q0, Z0, q1] | [q0, Z0, q2];
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).
1
Tài liệu tham khảo
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 .