Ngôn ngữ hình thức

CÂU HỎI VÀ BÀI TẬP CHƯƠNG 3

3.1. Nêu định nghĩa văn phạm phi ngữ cảnh (CFG); cho ví dụ.

3.2. Nêu các khái niệm: dẫn xuất, ngôn ngữ sinh bởi CFG; cho ví dụ.

3.3. Nêu định nghĩa cây dẫn xuất; phương pháp xây dựng cây dẫn xuất; cho ví dụ.

3.4. Nêu quan hệ giữa dẫn xuất và cây dẫn xuất.

3.5. Nêu định nghĩa dẫn xuất trái nhất, dẫn xuất phải nhất, văn phạm nhập nhằng; cho ví dụ.

3.6. Nêu khái niệm ký hiệu thừa, không thừa; cho ví dụ.

3.7. Nêu giải thuật loại bỏ các biến không dẫn ra xâu các ký hiệu kết thúc; cho ví dụ.

3.8. Nêu giải thuật loại bỏ các ký hiệu không được dẫn ra từ ký hiệu bắt đầu của văn phạm; cho ví dụ.

Có thể bạn quan tâm!

Xem toàn bộ 254 trang tài liệu này.

3.9. Nêu khái niệm luật sinh . Phương pháp loại bỏ luật sinh ; cho ví dụ.

3.10. Nêu khái niệm luật sinh đơn vị. Phương pháp loại bỏ luật sinh đơn vị; cho ví dụ.

3.11. Nêu dạng chuẩn Chomsky - CNF và phương pháp đưa một CFG về dạng chuẩn Chomsky; cho ví dụ.

3.12. Nêu dạng chuẩn Greibach - GNF và phương pháp đưa một CFG về dạng chuẩn Greibach; cho ví dụ.

3.13. Nêu tính chất của CFL.

3.14. Nêu các giải thuật quyết định CFL. Cho ví dụ.

3.15. Mô tả PDA và sự hoạt động của nó.

3.16. Nêu định nghĩa PDA; ngôn ngữ đoán nhận bởi PDA; cho ví dụ.

3.17. Nêu sự dịch chuyển của PDA và khái niệm hình trạng của PDA; cho ví dụ.

3.18. Nêu các định lý về sự tương đương giữa việc đoán nhận ngôn ngữ bởi trạng thái kết thúc và bởi stack rỗng; cho ví dụ.

3.19. Nêu phương pháp xây dựng PDA tương đương với CFL; cho ví dụ.

3.20. Nêu phương pháp xây dựng PDA tương đương với CFL; cho ví dụ.

3.21. Cho các văn phạm có tập các luật sinh tương ứng:

1) S → aS | Sb | aSb | c

2) S → SS | a | b

3) S → SaS | b

4) S → aSS | b

5) S → aA | bB| c; A → Sa; B → Sb.

6) S → AB; A → Sc | a; B → dB | b.

7) S → TT; T → aTa | bTb | c.

a) Nêu đầy đủ các thành phần của mỗi văn phạm.

b) Mô tả ngôn ngữ sinh bởi mỗi văn phạm.

3.22. Hãy chỉ ra một văn phạm phi ngữ cảnh sinh ra tập hợp:

1) Tập hợp các xâu đọc xuôi đọc ngược như nhau (đối xứng) trên bộ chữ cái Σ = {0,1}.

2) Tập hợp chuỗi các dấu ngoặc đúng trong biểu thức số học.

3) Tập hợp {aibicj | i, j ≥ 0}

4) Tập hợp {ambn | m, n > 0}

5) Tập hợp {aicaj | i , j ≥ 0}

6) Tập hợp {ajbjcidi | i, j ≥ 1}

3.23. Chứng minh rằng văn phạm phi ngữ cảnh G với tập luật sinh:

1) P: S  aAb | , A  aAb |  sinh ra ngôn ngữ {anbn  n  0};

2) P: S AB, AaA| a, BbB| b sinh ra ngôn ngữ {ambn | m, n > 0};

3) P: S ABC, AaAb|ab, BcB|c, C dC|d sinh ra ngôn ngữ {aibicjdk | i, j, k ≥ 1}.

3.24. Cho các văn phạm G có tập các luật sinh tương ứng:

1) S  abSba | 

2) S  01S | A; A  Aabc | 

3) S  Sabc | A; A  01A | 

Hãy biểu diễn ngôn ngữ sinh bởi mỗi văn phạm trên dưới dạng tập hợp.

3.25. Cho văn phạm G với các luật sinh sau:

S → aB | bA; A → a | aS | bAA; B → b | bS | aBB và xâu w = aaabbabbba.

Hãy tìm:

1) Dẫn trái nhất xuất, dẫn xuất phải nhất ra xâu w.

2) Cây dẫn xuất trái nhất, cây dẫn xuất phải nhất ra xâu w.

3.26. Cho văn phạm G với các luật sinh sau:

E → T | E + T | E - T; T → F | T × F | T / F; F → a | b | c | d | (E).

1) Nêu đầy đủ các thành phần của G.

2) Vẽ cây dẫn xuất sinh ra các xâu vào sau:

a) (a + b) / c

b) a × (b - c)

c) a – (b × c / d)

3.27. Cho văn phạm: S → aSbS | bSaS | ε

1) Chứng tỏ văn phạm này là văn phạm nhập nhằng (mơ hồ).

2) Xây dựng dẫn xuất trái nhất, phải nhất và cây dẫn xuất tương ứng cho xâu abab.

3.28. Cho văn phạm sinh ra câu lệnh rẽ nhánh trong ngôn ngữ lập trình Pascal: S → If b then S else S; S → If b then S; S → a;

Trong đó a, b, if, then, else là các ký hiệu kết thúc và S là biến.

1) Chứng tỏ văn phạm trên là nhập nhằng (mơ hồ).

2) Hãy đưa ra một văn phạm không nhập nhằng tương đương.

3.29. Cho văn phạm:

S → S+S | S-S | S*S | S/S | (S) |a.

1) Chứng tỏ văn phạm là nhập nhằng (mơ hồ):

2) Hãy đưa ra một văn phạm không nhập nhằng tương đương ? T → ( S ) | a .

3.30. Hãy loại bỏ các ký hiệu thừa trong mỗi văn phạm sau:

1) S → A | aSb | a; A → AB; B → b.

2) S → AB | CA; A → a; B → BC | AB; C → aB | b.

3.31. Tìm văn phạm chỉ có chứa một luật sinh ε duy nhất S → ε tương đương với văn phạm sau:

S → AB; A → SA | BB | bB; B → b | aA | ε.

3.32. Cho văn phạm có tập luật sinh:

S → AB | A | ; A → aBb | bS | b; B → AB | Ba |; C → Aa | D | .

Hãy tìm văn phạm tương đương thỏa mãn một trong các điều kiện:

1) Không chứa ký hiệu thừa

2) Không chứa luật sinh  nào khác ngoài luật sinh S → ε

3.33. Cho văn phạm có tập luật sinh:

S → AB | A | ; A → aBb | bS | b; B → AB | Ba |; C → Aa | D | .

Hãy tìm văn phạm tương đương thỏa mãn các điều kiện:

1) Không chứa ký hiệu thừa.

2) Không chứa luật sinh  nào khác ngoài luật sinh S → ε.

3) Không chứa luật sinh đơn vị.

3.34. Tìm văn phạm không chứa ký hiệu thừa, luật sinh ε ngoại trừ luật sinh S → ε và luật sinh đơn vị tương đương với mỗi văn phạm sau:

1) S → aSbS | bSaS | ε

2) S → A | B; A → aB | bS | b; B → AB | Ba; C → AS | b.

3) S → ABC; A → BB | ε; B → CC | a; C → AA | b.

4) S → A | B; A → C | D; B → D | E; C → S | a | ε; D → S | b; E → S | c | ε.

3.35. Cho văn phạm với các luật sinh sau:

S → A | aCA; A → D | a | ε; B → C | AbcB; C → aB | b | c | ε.

1) Nêu các thành phần của văn phạm trên.

2) Tìm văn phạm tương đương với văn phạm trên không chứa ký hiệu thừa, luật sinh ε và luật sinh đơn vị.

3.36. Cho văn phạm với các luật sinh sau:

S → A| AcBC; A → B | ε; B → bCA | C |a; C → ABc | b| ε.

1) Nêu các thành phần của văn phạm trên.

2) Tìm văn phạm tương đương với văn phạm trên không chứa ký hiệu thừa, luật sinh ε và luật sinh đơn vị.

3.37. Biến đổi các văn phạm sau đây về dạng chuẩn CHOMSKY:

1) S → bA | aB; A → bAA | aS | a; B → aBB | bS | b. 2) S → 0S1 | 01.

3) S → aAB | BA; A → BBB| a; B → AS| b.

4) S → adAda | aSa | aca; A → bAb | bdSdb.

3.38. Biến đổi các văn phạm sau đây về dạng chuẩn GREIBACH:

1) G = ( {S, A}, {0, 1}, P, S) với các luật sinh P: S → AA | 0; A → SS | 1.

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.

3) G = ( {A1, A2, A3, A4}, {a, b}, P, A1) với các luật sinh P:

A1 → A2A3 | A3A4; A2 → A3A2 | a; A3 → A4A4 | b; A4 → A2A3 | a.

3.39. Cho văn phạm G với các luật sinh sau:

S → BA | 0; A → SS | 1;

B → AB | 0 | 1.

1) Xác định các thành phần và dạng chuẩn của văn phạm trên

2) Biến đổi văn phạm trên về dạng chuẩn GREIBACH

3.40. Cho Automat pushdown M = < Q, , , , q0 , Z0 , F >; Trong đó: Q = {q0, q1, q2};  = {a, b};  = {Z0 , X, Y}; F = ;

: (q0 , a, Z0 ) = {(q0, XXX)};

(q0 , a, X ) = {(q0, XX)};

(q0 , b, X) = {(q1, )};

(q1 , b, X ) = {(q1, ), (q2, Y )};

(q2 , , Y) = {(q1, )}.

Hãy kiểm tra xem M có đoán nhận được từ w bằng stack rỗng không:

- w = aaaabbbbbb;

- w = aabbb.

3.41. Cho Automat pushdown M = < Q, , , , q0 , Z0 , F >;

Trong đó: Q = {q0, q1, q2};  = {a, b};  = {Z0 , X, Y}; F = {q2};

: (q0 , a, Z0 ) = {(q0, XXX)};

(q0 , a, X ) = {(q0, XX)};

(q0 , b, X ) = {(q1, )};

(q1 , b, X ) = {(q1, ), (q2, YX)};

(q2 , b,Y ) = {(q2, ), (q2, YX )}.

Hãy kiểm tra xem M có đoán nhận được từ w bằng trạng thái kết thúc không:

- w = aaaabbbbbb;

- w = aabbbbb.

3.42. Chứng minh rằng các ngôn ngữ sau không phải là CFL:

i j k

1) L = {a b c | i < j < k }

i j 2

2) L = {a b | j = i }

3) L = {a | i là số nguyên tố }

n n n n

4) L = {a b c d | n ≥ 0}

3.43. Viết chương trình loại bỏ các ký hiệu thừa trong một CFG.

3.44. Viết chương trình loại bỏ các luật sinh  và luật sinh đơn vị trong một CFG.

3.45. Viết chương trình chuẩn hóa một CFG thành dạng chuẩn CHOMSKY (CNF).

3.46. Viết chương trình chuẩn hóa một CFG thành dạng chuẩn GREIBACH (GNF).

3.47. Xây dựng PDA tương đương với văn phạm:

1) S → +SS | *SS | a.

2) S → aS | bS | aA; A → bB| b; B → aC; C → b.

3.48. Xây dựng PDA đoán nhận một trong các ngôn ngữ:

n n

1) Tập hợp {a b | n ≥ 0}

m n

2) Tập hợp {a b | m, n > 0}

i j

3) Tập hợp {a ca | i, j ≥ 0}

m m n

4) {0 1 2 | m, n ≥ 1}

m m n n

5) {a b c d | m, n ≥ 0}

3.49. Xây dựng văn phạm CFG tương đương với các PDA sau:

1) M = <{q , q }, {0, 1}, {Z , X}, δ, q , Z , ∅>; trong đó δ được cho như sau:

0 1 0 0 0

δ(q0, 1, Z0) = {(q0, XZ0)}

δ(q0, 0, X) = {(q0, XX)}

δ(q0, 1, X) = {(q1, ε)}

δ(q1, 1, X) = {(q1, ε)}

δ(q1, ε, X) = {(q1, ε)}

δ(q , ε, Z ) = {(q , ε)}

1 0 1

2) M = <{q , q }, {0, 1}, {Z , X}, δ, q , Z , ∅>; trong đó δ được cho như sau:

0 1 0 0 0

δ(q0, 1, Z0) = {(q0, XZ0)};

δ(q0, 1, X) = {(q0, XX)};

δ(q0, 0, X) = {(q1, X)};

δ(q0, ε, Z0) = {(q0, ε)};

δ(q1, 1, X) = {(q1, ε)};

δ(q1, 0, Z0) = {(q0, Z0)}.

3) M ({q0, q1}, {a, b, c}, {Z0, X}, δ, q0, Z0, ∅), trong đó δ được cho như sau: δ(q0, a, Z0) = {(q0, X)};

δ(q0, a, X) = {(q0, XX)};

δ(q0, c, X) = {(q1, X)};

δ(q0, b, Z0) = {(q0, X)};

δ(q0, b, X) = {(q0, XX)};

δ(q1, c, X) = {(q1, ε)}.

3.50. Cho Automat pushdown M = < Q, , , , q0 , Z0 , F >;

Trong đó: Q = {q0, q1, q2};  = {a, b};  = {Z0 , X, Y}; F = {q2};

: (q0 , a, Z0 ) = {(q0, XXX)};

(q0 , a, X ) = {(q0, XX)};

(q0 , b, X ) = {(q1, )};

(q1 , b, X ) = {(q1, ), (q2, YX)};

(q2 , b,Y ) = {(q2, ), (q2, YX )}.

Xây dựng văn phạm CFG tương đương với PDA trên.

LỜI GIẢI TÓM TẮT HOẶC HƯỚNG DẪN

1. Bài tập chương 1

1.13. 1) T* = {, 0, 1, 00, 11, 000, 001, 010, 011, 100, 101, 110, 111, ...}

2)  L  T* đều là ngôn ngữ trên bảng chữ cái T. Chẳng hạn: L1= ;

L2 = T* = {, 0, 1, 00, 11, 000, 001, 010, 011, 100, 101, 110, 111, ...};

L3 = {};

L4 = {, 0, 1};

L5 = { 0, 11, 000, 111, 0110}; …

1.14. 1) L1  L2 = {, 0, 1, 00, 11, 000, 001, 010, 011, 100}= L2

2) L1  L2 = {0, 1}= L1

3) L1 - L2 = 

4) L2 - L1 = {, 00, 11, 000, 001, 010, 011, 100}

5) L1L2 = {0, 1, 00, 10, 01, 11, 000, 100, 011, 111, 0000, 1000, 0001, 1001,

0010, 1010, 0011, 1011, 0100, 1100}.

1.15. 1) * = {, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, …};

L = * - L = {aa, ab, ba, bb, aaa, aab, aba, abb, …}.

2) L0 = {};

L1 = {, a, b};

L2 = LL = {, a, b, aa, ab, ba, bb};

L3 = L2 L = {, a, b, aa, ab, ba, bb, aa, ba, aaa, aba, baa, bba, aab, abb, bab, bbb};

1.16. 1) L1 = {ai bi  i  N* } 2) L2 = {0i 1j  i, j  N* }

1.17. 1a) - G không là văn phạm loại 3 vì luật sinh AB aADb vi phạm điều kiện của văn phạm loại 3;

- G không là văn phạm loại 2 vì luật sinh AB aADb vi phạm điều kiện của văn phạm loại 2;