<< Chapter < Page Chapter >> Page >

Cuối cùng, vì S  V15 , vậy chuỗi baaba là thuộc ngôn ngữ sinh ra bởi văn phạm đã cho.

Tổng kết chương V: Việc mô tả ngôn ngữ phi ngữ cảnh bằng phương tiện văn phạm phi ngữ cảnh tỏ ra rất hữu hiệu, cũng tương tự như việc sử dụng văn phạm BNF trong định nghĩa các ngôn ngữ lập trình. Trong chương này, chúng ta đã khảo sát tương đối cặn kẽ các phương tiện mô tả ngôn ngữ của văn phạm CFG thông qua các giải thuật tối ưu biến, giản lược, quy chuẩn và các tính chất của lớp ngôn ngữ mà nó mô tả. Câu hỏi đặt ra tiếp theo là có hay không một lớp ôtômát tương ứng để nhận dạng lớp ngôn ngữ phi ngữ cảnh. Như chúng ta đã thấy, lớp ngôn ngữ phi ngữ cảnh thực sự chứa lớp ngôn ngữ chính quy trong đó, nên ôtômát hữu hạn không thể nhận biết tất cả ngôn ngữ phi ngữ cảnh. Một cách trực quan, ôtômát hữu hạn có bộ nhớ bị hạn chế nghiêm ngặt, trong khi việc nhận dạng CFL có thể yêu cầu phải lưu trữ một lượng thông tin khá lớn. Khả năng cho sự mở rộng này sẽ được chúng ta xét đến trong nội dung của chương tiếp theo.

BÀI TẬP CHƯƠNG V

  • . Hãy mô tả ngôn ngữ sinh bởi các văn phạm sau :

a) S ® aS | Sb | aSb | c

b) S ® SS | a | b

c) S ® SaS | b

d) S ® aSS | b

e)S ® aA | bB| c

A ® Sa

B ® Sb

f)S ® AB

A ® Sc | a

B ® dB | b

g)S ® TT

T ® aTa | bTb | c

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

a) Tập hợp các chuỗi đọc xuôi đọc ngược như nhau trên bộ chữ cái  = {0,1}.

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

c) Tập hợp {aibicj  i, j  0}

d) Tập hợp {ambn  m, n>0}

e) Tập hợp {aicaj  i  j  0}

f) Tập hợp {ajbjcidi  i, j  1}

5.3. 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ới chuỗi aaabbabbba , hãy tìm:

a) Dẫn xuất trái nhất.

b) Dẫn xuất phải nhất.

c) Cây dẫn xuất.

d) Văn phạm này có là văn phạm mơ hồ không ?

5.4. 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 | (E)

Hãy vẽ cây dẫn xuất sinh ra các chuỗi nhập sau :

a) a – (b  c / a)

b) a  (b - c)

c) (a + b) / c

5.5. Cho văn phạm : S ® aSbS | bSaS | 

a) Chứng tỏ văn phạm này là văn phạm mơ hồ .

b) Xây dựng dẫn xuất trái (phải) và cây dẫn xuất tương ứng cho chuỗi abab.

c) Văn phạm này sinh ra ngôn ngữ gì ?

5.6. Chứng tỏ văn phạm sau đây là mơ hồ :

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.

5.7. Chứng tỏ văn phạm sau đây là mơ hồ :

S ® aBS | aB | bAS | bA

A ® bAA | a

B ® aBB | b

Hãy đề nghị một văn phạm không mơ hồ tương đương ?

5.8. Tìm CFG không có chứa ký hiệu vô ích tương đương với văn phạm:

a)S ® A | a

A ® AB

B ® b

b)S ® AB | CA

A ® a

B ® BC | AB

C ® aB | b

5.9. Tìm văn phạm tương đương với văn phạm sau không có chứa ký hiệu vô ích, luật sinh  và luật sinh đơn vị :

a)S ® aSbS | bSaS | 

b) S ® A | B

A ® aB | bS | b

B ® AB | Ba

C ® AS | b

c) S ® ABC

A ® BB | 

B ® CC | a

C ® AA | b

d) S ® A | B

A ® C | D

B ® D | E

C ® S | a | 

D ® S | b

E ® S | c | 

5.10. 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 | 

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

a)S ® bA | aB

A ® bAA | aS | a

B ® aBB | bS | b

b)S ® aAB | BA

A ® BBB| a

B ® AS| b

c)S ® adAda | aSa | aca

A ® bAb | bdSdb

d) S ® 0S1 | 01

e) S ® #S | [ S  S] | p | q

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

a) G ( {S, A}, {0, 1}, P, S) với các luật sinh :

S ® AA | 0

A ® SS | 1

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

A1 ® A2A3

A2 ® A3A1 | b

A3 ® A1A2 | a

c) 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

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

a)L = {ai bj ck i<j<k }

b)L = {ai bj j = i2 }

c)L = {ai i là số nguyên tố }

d) L = {anbncndn  n  0}

BÀI TẬP LẬP TRÌNH

5.14. Viết chương trình loại bỏ các ký hiệu vô ích trong một CFG.

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

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

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Giáo trình tin học lý thuyết. OpenStax CNX. Jul 30, 2009 Download for free at http://cnx.org/content/col10826/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Giáo trình tin học lý thuyết' conversation and receive update notifications?

Ask