bài tập chương V Văn phạm phi ngữ cảnh

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

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 {aⁱbⁱc^j | i, j ≥ 0}

d) Tập hợp {a^mbⁿ | m, n > 0}

e) Tập hợp {aⁱca^j | i ≥ j ≥ 0}

f) Tập hợp {a^jb^jcⁱdⁱ | i, j ≥ 1}

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 ?

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

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ì ?

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.

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 ?

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

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 | ε

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 | ε

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

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 ( {A₁, A₂, A₃}, {a, b}, P, A₁) với các luật sinh :

A₁ ® A₂A₃

A₂ ® A₃A₁ | b

A₃ ® A₁A₂ | a

c) G ( {A₁, A₂, A₃, A₄}, {a, b}, P, A₁) với các luật sinh :

A₁ ® A₂A₃ | A₃A₄

A₂ ® A₃A₂ | a

A₃ ® A₄A₄ | b

A₄ ® A₂A₃ | a

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

a) L = {aⁱ b^j c^k i < j < k }

b) L = {aⁱ b^j j = i² }

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

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

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

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

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