A → bCA | bA | bC | b | a | ABc | Bc | Ac | c | b; B → bCA | bA | bC | b | a | ABc | Bc | Ac | c | b; C → ABc | Bc | Ac | c | b.
3.37. 1) S → bA | aB; A → bAA | aS | a; B → aBB | bS | b.
1. Văn phạm không có luật sinh đơn vị
2. Thay thế các luật sinh có độ dài vế phải lớn hơn 1 và chứa kí tự kết thúc S → CbA | CaB; A → CbAA | CaS | a; B → CaBB | CbS | b;
Ca → a; Cb → b.
3. Thay thế các luật sinh có độ dài vế phải lớn hơn 2 các biến S → CbA | CaB; A → CbD | CaS | a; B → CaE| CbS | b;
Ca → a; Cb → b; D → AA; E →BB.
2) S → 0S1 | 01
Có thể bạn quan tâm!
Xem toàn bộ 254 trang tài liệu này.
Thực hiện tương tự câu 1, ta thu được:
S → C0A | C0 C1; C0 →0; C1→1; A → SC1.
3) S → aAB | BA; A → BBB| a; B → AS| b. Thực hiện tương tự câu 1, ta thu được:
S → Ca C | BA; A → BD| a; B → AS| b; Ca → a; C → AB; D →BB.
4) S → adAda | aSa | aca; A → bAb | bdSdb. Thực hiện tương tự câu 1, ta thu được:
S → CaD1 | CaA1 | CaB1; A → CbA2 | Cb E1 ; Ca → a;
Cb → b; Cc → c; Cd → d; D1 → CdD2 ; D2 → AD3; D3 → CdCa; A1 → SCa ; B1→ CcCa; A2 → ACb; E1→ CdE2; E2→ SE3; E3→ CdCb .
3.38. 1) S → AA | 0; A → SS | 1.
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} = {A1, A2} nên có tập luật sinh tương ứng: A1 → A2 A2 | 0; A2 → A1A1 | 1.
Bước 3: Thay thế các luật sinh sao cho nếu Ai → Aj γ là một luật sinh thì j > i.
Trong tập luật sinh, các luật sinh cho A1 đã thỏa điều kiện j > i. Chỉ có luật sinh A2 → A1A1 cần biến đổi. Ta lại có A1 → A2 A2 | 0, nên ta thay luật sinh này bằng A2 → A2A2A1 | 0A1 A2 → A2A2A1 | 0A1 | 1.
Sau đó, loại bỏ đệ quy trái trực tiếp cho A3 luật sinh, ta được tập luật sinh
mới có dạng như sau:
A2 → 0A1 | 1 | 0A1B | 1B ; B → A2A1 | A2A1 B.
Do đó, văn phạm có tập luật sinh:
A1 → A2 A2 | 0;
A2 → 0A1 | 1 | 0A1B | 1B; B → A2A1 | A2A1 B.
Bước 4: Thay thế các Ai -luật sinh về đúng dạng chuẩn.
Ta có, tất cả các A2 - luật sinh đã có dạng chuẩn.
Thay thế các A1 - luật sinh, ta thu được tập luật sinh mới như sau: A1 → 0A1A2 | 1A2 | 0A1BA2 | 1BA2 | 0;
A2 → 0A1 | 1 | 0A1B | 1B;
B → A2A1 | A2A1 B.
Bước 5: Thay thế các B - luật sinh về đúng dạng chuẩn.
B → 0A1A1 | 1A1 | 0A1BA1 | 1BA1 | 0A1A1B | 1A1B | 0A1B A1 B | 1BA1B
Cuối cùng, ta thu được văn phạm có dạng GNF với các luật sinh.
A1 → 0A1A2 | 1A2 | 0A1BA2 | 1BA2 | 0; A2 → 0A1 | 1 | 0A1B | 1B;
B → 0A1A1 | 1A1 | 0A1BA1 | 1BA1 | 0A1A1B | 1A1B | 0A1B A1 B | 1BA1B.
2) G = ( {A1, A2, A3}, {a, b}, P, A1) với các luật sinh P: A1 → A2A3 ; A2 → A3A1 | b; A3 → A1A2 | a.
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 = {A1, A2, A3}
Bước 3: Thay thế các luật sinh sao cho nếu Ai → Aj γ là một luật sinh thì j > i.
Trong tập luật sinh, các luật sinh cho A1 và A2 đã thỏa điều kiện j > i. Chỉ có luật sinh A3 → A1A2 cần biến đổi. Ta lại có A1 → A2A3, nên ta thay luật sinh này bằng A3 → A2A3A2. Ta lại có A2 → A3A1 | b, nên ta thay luật sinh này bằng A3 → A3A1A3A2 | bA3A2 A3 → A3A1A3A2 | bA3A2 | a.
Sau đó, loại bỏ đệ quy trái trực tiếp cho A3 luật sinh, ta được tập luật sinh
mới có dạng như sau:
A3 → bA3A2 | a | bA3A2B | aB; B → A1A3A2 | A1A3A2B.
Do đó, văn phạm có tập luật sinh:
A1 → A2A3; A2 → A3A1 | b;
A3 → bA3A2 | a | bA3A2B | aB;
B → A1A3A2 | A1A3A2B.
Bước 4: Thay thế các Ai - luật sinh về đúng dạng chuẩn. Ta có, tất cả các A3 - luật sinh đã có dạng chuẩn.
Thay thế các A2, A1 - luật sinh; ta thu được tập luật sinh mới như sau:
A1 → bA3A2A1A3 | aA1A3 | bA3A2BA1A3 | aBA1A3 | bA3;
A2 → bA3A2A1 | aA1 | bA3A2BA1 | aBA1 | b; A3 → bA3A2 | a | bA3A2B | aB;
B → A1A3A2 | A1A3A2B.
Bước 5: Thay thế các B - luật sinh về đúng dạng chuẩn.
B → bA3A2A1A3A3A2 | aA1A3A3A2 | bA3A2BA1A3A3A2 | aBA1A3A3A2 | bA3A3A2| bA3A2A1A3A3A2B | aA1A3A3A2B | bA3A2BA1A3A3A2B | aBA1A3A3A2B | bA3A3A2B.
Cuối cùng, ta thu được văn phạm có dạng GNF với các luật sinh.
A1 → bA3A2A1A3 | aA1A3 | bA3A2BA1A3 | aBA1A3 | bA3;
A2 → bA3A2A1 | aA1 | bA3A2BA1 | aBA1 | b; A3 → bA3A2 | a | bA3A2B | aB;
B → bA3A2A1A3A3A2 | aA1A3A3A2 | bA3A2BA1A3A3A2 | aBA1A3A3A2 |
bA3A3A2| bA3A2A1A3A3A2B | aA1A3A3A2B | bA3A2BA1A3A3A2B | aBA1A3A3A2B | bA3A3A2B.
3) G = ( {A1, A2, A3, A4}, {a, b}, P, A1) với các luật sinh:
A1 → A2A3 | A3A4; A2 → A3A2 | a; A3 → A4A4 | b; A4 → A2A3 | a.
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 = {A1, A2, A3, A4}
Bước 3: Thay thế các luật sinh sao cho nếu Ai → Aj γ là một luật sinh thì j > i.
Trong tập luật sinh, các luật sinh cho A1, A2 và A3 đã thỏa điều kiện j > i. Chỉ có luật sinh A4 → A2A3 cần biến đổi. Ta lại có A2 → A3A2 | a, nên ta thay luật sinh này bằng A4 → A3A2A3| aA3. Ta lại có A3 → A4A4 | b, nên ta thay luật sinh này bằng A4 → A4A4 A2A3| bA2A3 | aA3.
Sau đó, loại bỏ đệ quy trái trực tiếp cho A4 luật sinh, ta được tập luật sinh
mới có dạng như sau:
A4 → bA2A3 | aA3| bA2A3B | aA3B; B → A4 A2A3 | A4 A2A3B.
Do đó, văn phạm có tập luật sinh:
A1 → A2A3 | A3A4;
A2 → A3A2 | a;
A3 → A4A4 | b;
A4 → bA2A3 | aA3| bA2A3B | aA3B;
B → A4 A2A3 | A4 A2A3B.
Bước 4: Thay thế các Ai - luật sinh về đúng dạng chuẩn. Ta có, tất cả các A4 - luật sinh đã có dạng chuẩn.
Thay thế các A3, A2, A1 - luật sinh; ta thu được tập luật sinh mới như sau:
A1 → bA2A3A4A2A3 | aA3A4A2A3 | bA2A3BA4A2A3 | aA3BA4A2A3 | bA2A3 | aA3 | bA2A3A4A4 | aA3A4A4 | bA2A3BA4A4 | aA3BA4A4 | bA4;
A2 → bA2A3A4A2 | aA3A4A2 | bA2A3BA4A2 | aA3BA4A2 | bA2 | a
A3 → bA2A3A4 | aA3A4 | bA2A3BA4 | aA3BA4 | b;
A4 → bA2A3 | aA3| bA2A3B | aA3B; B → A4 A2A3 | A4 A2A3B.
Bước 5: Thay thế các B - luật sinh về đúng dạng chuẩn.
B → bA2A3A2A3 | aA3A2A3 | bA2A3BA2A3 | aA3BA2A3 | bA2A3A2A3B| aA3A2A3B | bA2A3BA2A3B | aA3BA2A3B
Cuối cùng, ta thu được văn phạm có dạng GNF với các luật sinh.
A1 → bA2A3A4A2A3 | aA3A4A2A3 | bA2A3BA4A2A3 | aA3BA4A2A3 | bA2A3 | aA3 | bA2A3A4A4 | aA3A4A4 | bA2A3BA4A4 | aA3BA4A4 | bA4;
A2 → bA2A3A4A2 | aA3A4A2 | bA2A3BA4A2 | aA3BA4A2 | bA2 | a
A3 → bA2A3A4 | aA3A4 | bA2A3BA4 | aA3BA4 | b;
A4 → bA2A3 | aA3| bA2A3B | aA3B;
B → bA2A3A2A3 | aA3A2A3 | bA2A3BA2A3 | aA3BA2A3 | bA2A3A2A3B| aA3A2A3B | bA2A3BA2A3B | aA3BA2A3B
3.39. 1) - G = (N, T, P, S):
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} = {A1, A2, A3} nên có tập luật sinh tương ứng: A1 → A3 A2 | 0; A2 → A1A1 | 1; A3 → A2 A3 | 0 | 1.
Bước 3: Thay thế các luật sinh sao cho nếu Ai → Aj γ là một luật sinh thì j > i.
Trong tập luật sinh, các luật sinh cho A1 đã thỏa điều kiện j > i. Chỉ có các luật sinh A2 → A1A1 và A3 → A2 A3 cần biến đổi.
Trước hết biến đổi luật sinh A2 → A1A1|1, ta được A2 → A3A2A1| 0A1|1.
Biến đổi luật sinh A3 → A2 A3 | 0 | 1, ta được
A3 → A3A2A1A3| 0A1A3|1A3 | 0 | 1
Sau đó, loại bỏ đệ quy trái trực tiếp cho A3 luật sinh, ta được tập luật sinh mới có dạng như sau:
A3 → 0A1A3|1A3 | 0 | 1| 0A1A3B |1A3B | 0B | 1B; B → A2A1A3 | A2A1A3B.
Do đó, văn phạm có tập luật sinh:
A1 → A3 A2 | 0;
A2 → A3A2A1| 0A1|1;
A3 → 0A1A3|1A3 | 0 | 1| 0A1A3B |1A3B | 0B | 1B; B → A2A1A3 | A2A1A3B.
Bước 4: Thay thế các Ai - luật sinh về đúng dạng chuẩn.
Ta có, tất cả các A3 - luật sinh đã có dạng chuẩn.
Thay thế các A2, A1 - luật sinh; ta thu được tập luật sinh mới như sau:
A1 → 0A1A3A2|1A3A2 | 0A2 | 1A2| 0A1A3BA2 |1A3BA2 | 0BA2 | 1BA2 | 0;
A2 → 0A1A3A2A1|1A3A2A1 | 0A2A1 | 1A2A1| 0A1A3BA2A1 |1A3BA2A1 | 0B A2A1 | 1BA2A1| 0A1|1;
A3 → 0A1A3|1A3 | 0 | 1| 0A1A3B |1A3B | 0B | 1B;
B → A2A1A3 | A2A1A3B.
Bước 5: Thay thế các B - luật sinh về đúng dạng chuẩn.
B → 0A1A3A2A1A1A3|1A3A2A1A1A3 | 0A2A1A1A3 | 1A2A1A1A3| 0A1A3BA2A1A1A3 | 1A3BA2A1A1A3 | 0B A2A1A1A3 | 1BA2A1A1A3|
0A1A1A3|1A1A3 |0A1A3A2A1A1A3B |1A3A2A1A1A3B | 0A2A1A1A3B|
1A2A1A1A3B | 0A1A3BA2A1A1A3B | 1A3BA2A1A1A3B | 0B A2A1A1A3B|
1BA2A1A1A3B | 0A1A1A3B |1A1A3B.
Cuối cùng, ta thu được văn phạm có dạng GNF với các luật sinh.
A1 → 0A1A3A2|1A3A2 | 0A2 | 1A2| 0A1A3BA2 |1A3BA2 | 0BA2 | 1BA2 | 0; A2 → 0A1A3A2A1|1A3A2A1 | 0A2A1 | 1A2A1| 0A1A3BA2A1 |1A3BA2A1 |
0B A2A1 | 1BA2A1| 0A1|1;
A3 → 0A1A3|1A3 | 0 | 1| 0A1A3B |1A3B | 0B | 1B;
B → 0A1A3A2A1A1A3|1A3A2A1A1A3 | 0A2A1A1A3 | 1A2A1A1A3| 0A1A3BA2A1A1A3 | 1A3BA2A1A1A3 | 0B A2A1A1A3 | 1BA2A1A1A3|
0A1A1A3|1A1A3 |0A1A3A2A1A1A3B |1A3A2A1A1A3B | 0A2A1A1A3B|
1A2A1A1A3B | 0A1A3BA2A1A1A3B | 1A3BA2A1A1A3B | 0B A2A1A1A3B|
1BA2A1A1A3B | 0A1A1A3B |1A1A3B.
3.40. - w = aaaabbbbbb
(q0, aaaabbbbbb, Z0) ⊢ (q0, aaabbbbbb, XXX) ⊢ (q0, aabbbbbb, XXXX) ⊢
(q0, abbbbbb, XXXXX) ⊢ (q0, bbbbbb, XXXXXX) ⊢ (q1, bbbbb, XXXXX)
⊢ (q1, bbbb, XXXX) ⊢ (q1, bbb, XXX) ⊢ (q1, bb, XX) ⊢ (q1, b, X) ⊢ (q2, , Y)
⊢
(q , , ) w L(M) và được đoán nhận bởi stack rỗng.
1
- aabbb
⊢ ⊢ ⊢
(q , aabbb, Z0) (q , abbb, XXX) (q , bbb, XXXX)
0 0 0
⊢ ⊢
(q , bb, XXX) (q , b, XX) (q , , X): Không chấp nhận
1 1 1
┬ ┬
(q , b, YXX): Không chấp nhận (q , b, YX): Không chấp nhận
2 2
3.41. - w = aaaabbbbbb
(q0, aaaabbbbbb, Z0) ⊢ (q0, aaabbbbbb, XXX) ⊢ (q0, aabbbbbb, XXXX) ⊢ (q0, abbbbbb, XXXXX) ⊢ (q0, bbbbbb, XXXXXX) ⊢ (q1, bbbbb, XXXXX) ⊢ (q1, bbbb, XXXX) ⊢ (q1, bbb, XXX) ⊢ (q1, bb, XX) ⊢ (q1, b, X) ⊢
(q2, , 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.