Văn phạm phi ngữ cảnh (Context Free Grammar): Bài giảng Tin học lý thuyết

Chương 5:

Văn phạm phi ngữ cảnh (Context Free Grammar)

Nội dung:

• Văn phạm phi ngữ cảnh (CFG)

• Giản lược văn phạm phi ngữ cảnh

• Chuẩn hóa văn phạm phi ngữ cảnh

• Các tính chất của văn phạm phi ngữ cảnh

Văn phạm phi ngữ cảnh

(cid:0) (cid:0) (cid:0) (cid:0) (V(cid:0) T)*)

Định nghĩa: là hệ thống gồm 4 thành phần G(V, T, P, S) • V : tập hữu hạn các biến (ký tự chưa kết thúc) • T : tập hữu hạn các ký tự kết thúc (V (cid:0) T = Ø) (cid:0) ((cid:0) • P : tập hữu hạn các luật sinh dạng A (cid:0) • S : ký hiệu bắt đầu của văn phạm

Quy ước:

• V: chữ in hoa (A, B, C, ..); T: chữ in thường (a, b, c, .., w, x, y..) • (cid:0) , .. biểu diễn chuỗi ký hiệu kết thúc và biến , (cid:0) , (cid:0)

Ví dụ: G=({S, A, B}, {a, b}, P, S) với P gồm các luật sinh:

hay

S (cid:0) A (cid:0) B (cid:0) AB aA(cid:0) a bB(cid:0) b 2

S (cid:0) A (cid:0) A (cid:0) B (cid:0) B (cid:0) AB aA a bB b

Dẫn xuất và ngôn ngữ

(cid:0) (cid:0) Dẫn xuất: • Nếu A (cid:0) là 2 chuỗi bất kỳ,

(cid:0) là luật sinh trong văn phạm G và (cid:0) (cid:0) vào chuỗi (cid:0) A(cid:0) , (cid:0) ta sẽ thu được

(cid:0) (cid:0) thì khi áp dụng luật sinh A (cid:0) chuỗi (cid:0) :

G (cid:0)

(cid:0) (cid:0) (cid:0) (cid:0)

m-1

G (cid:0)

2, (cid:0)

G (cid:0)

m, ta có:

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) • Giả sử: (cid:0) (cid:0) A(cid:0) 3, ..., (cid:0) G (cid:0)

(cid:0) (cid:0) (cid:0)

(cid:0) (cid:0) với mọi chuỗi (cid:0)

G và (cid:0)

*G (cid:0) và (cid:0) * thay cho (cid:0) *G (cid:0) • Ta có: (cid:0) • Thông thường, ta sẽ dùng (cid:0) *G

T* và S (cid:0) Ngôn ngữ sinh bởi CFG: cho CFG G(V, T, P, S) L(G) = { w(cid:0) w (cid:0) *G w }

(chuỗi w gồm toàn ký hiệu kết thúc và được dẫn ra từ S)

Cây dẫn xuất

Định nghĩa: cây dẫn xuất (hay cây phân tích cú pháp) của một văn

(cid:0) {ε} ) (V (cid:0) (cid:0) T (cid:0)

phạm G(V, T, P, S) có đặc điểm (1) Mỗi nút có một nhãn, là một ký hiệu (cid:0) (2) Nút gốc có nhãn là S (ký hiệu bắt đầu) (3) Nếu nút trung gian có nhãn A thì A (cid:0) V (4) Nếu nút n có nhãn A và các đỉnh n1, n2, ..., nk là con của n theo thứ tự từ trái sang phải có nhãn lần lượt là X1, X2, ..., Xk thì A

(cid:0) X1X2...Xk là một luật sinh trong P

(5) Nếu nút n có nhãn là ε thì n phải là nút lá và là nút con duy nhất của nút cha của nó

Cây dẫn xuất

Ví dụ: xét văn phạm G({S, A}, {a, b}, P, S}, với P gồm: aAS(cid:0) a SbA(cid:0) SS(cid:0) ba

S (cid:0) A (cid:0) Một dẫn xuất của G: aAS (cid:0) S (cid:0) aSbAS (cid:0) aabAS (cid:0) aabbaS (cid:0) aabbaa

Định lý 5.1: nếu G(V, T, P, S) là một CFG thì S (cid:0) * (cid:0) 5 nếu và chỉ nếu

có cây dẫn xuất trong văn phạm sinh ra (cid:0) .

Dẫn xuất trái nhất - Dẫn xuất phải nhất

Dẫn xuất trái nhất (phải nhất): nếu tại mỗi bước dẫn xuất, luật sinh

được áp dụng vào biến bên trái nhất (phải nhất)

Ví dụ: xét văn phạm G với luật sinh:

S (cid:0) A (cid:0) B (cid:0) AB aA(cid:0) a bB(cid:0) b

• Các dẫn xuất khác nhau cho từ aaabb:

aaabb aaabb

aaabB (cid:0) aaAbb (cid:0) aaAbb (cid:0) aaabb

(a) S (cid:0) (b) S (cid:0) (c) S (cid:0) (d) S (cid:0) AB(cid:0) AB(cid:0) AB(cid:0) AB(cid:0) aAB (cid:0) AbB (cid:0) aAB (cid:0) aAB (cid:0) aaAB (cid:0) Abb (cid:0) aAbB (cid:0) aaAB (cid:0) aaaB (cid:0) aAbb (cid:0) aAbb (cid:0) aaAbB (cid:0) aaabB (cid:0) aaabb

• Dẫn xuất (a) là dẫn xuất trái nhất, (b) là dẫn xuất phải nhất • Các dẫn xuất tuy khác nhau, nhưng có cùng một cây dẫn xuất

Văn phạm mơ hồ

Khái niệm: một văn phạm phi ngữ cảnh G được gọi là văn phạm mơ hồ (ambiguity) nếu nó có nhiều hơn một cây dẫn xuất cho cùng một chuỗi w.

Ví dụ: xét văn phạm G với luật sinh:

E (cid:0) E + E (cid:0) (cid:0) E * E (cid:0) (cid:0) (E) (cid:0) (cid:0) a

Với chuỗi a + a * a, ta có thể vẽ đến 2 cây dẫn xuất khác nhau

Điều này có nghĩa là biểu thức a + a * a có thể hiểu theo 2 cách

khác nhau: (a + a) * a hoặc a + (a * a)

Văn phạm mơ hồ

Khắc phục văn phạm mơ hồ:

• Quy định rằng các phép cộng và nhân luôn được thực hiện theo thứ tự từ trái sang phải (trừ khi gặp ngoặc đơn)

E (cid:0) T (cid:0) E + T (cid:0) E * T (cid:0) T (E) (cid:0) a

• Quy định rằng khi không có dấu ngoặc đơn ngăn cách thì phép nhân luôn được thực hiện ưu tiên hơn phép cộng E + T (cid:0) T T * F (cid:0) F (E) (cid:0) a E (cid:0) T (cid:0) F (cid:0)

Giản lược văn phạm phi ngữ cảnh

● Các ký hiệu không tham gia vào quá trình dẫn xuất ra chuỗi ký hiệu kết thúc ● Luật sinh dạng A (cid:0)

Trong CFG có thể chứa các yếu tố thừa:

B (làm kéo dài chuỗi dẫn xuất)

(cid:0)

giản lược văn phạm nhằm loại bỏ những yếu tố vô ích, nhưng không được làm thay đổi khả năng sản sinh ngôn ngữ của văn phạm

• Mỗi biến và mỗi ký hiệu kết thúc của văn phạm đều xuất hiện trong dẫn xuất của một số chuỗi trong ngôn ngữ • Không có luật sinh A (cid:0) ● Nếu ngôn ngữ không chấp nhận chuỗi rỗng ε thì không cần luật sinh A (cid:0)

B (với A, B đều là biến)

ε .

Các ký hiệu vô ích

(cid:0) (cid:0) Khái niệm: một ký hiệu X được gọi là có ích nếu có một dẫn xuất * (cid:0) X(cid:0) * w S (cid:0)

với (cid:0) , (cid:0) là các chuỗi bất kỳ và w (cid:0) T*.

• X phải dẫn ra chuỗi ký hiệu kết thúc • X phải nằm trong dẫn xuất từ S

(cid:0) có 2 đặc điểm cho ký hiệu có ích

Các ký hiệu vô ích

Bổ đề 1: (loại bỏ các biến không dẫn ra chuỗi ký hiệu kết thúc)

Cho CFG G(V, T, P, S) với L(G) ≠ Ø, có một CFG G'(V', T', P', S) tương đương sao cho mỗi A (cid:0) V' tồn tại w (cid:0) T* để A (cid:0) * w

Giải thuật tìm V':

Begin

;

w với w (cid:0)

T* };

(cid:0) A (cid:0) NewV' do

{A (cid:0) A (cid:0)

(cid:0)

với (cid:0)

(cid:0)

(T (cid:0)

OldV')* }

(1) OldV' := (cid:0) (2) NewV' := { A (cid:0) (3) While OldV' (cid:0) begin (4) OldV' := NewV'; (5) NewV' := OldV' (cid:0) end; (6) V' := NewV';

End;

Các ký hiệu vô ích

Bổ đề 2: (loại bỏ các biến không được dẫn ra từ ký hiệu bắt đầu)

T') tồn tại (cid:0) (V' (cid:0) , (cid:0) (cid:0)

Cho CFG G(V, T, P, S), ta có thể tìm được CFG G'(V', T', P', S) tương đương sao cho mỗi X (cid:0) (V' (cid:0) T')* để S (cid:0) * (cid:0) X(cid:0)

Cách tìm:

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) • Đặt V' = {S} • Nếu A (cid:0)

1

2 n là các luật sinh trong P thì

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) V' và A (cid:0) ➢ Thêm các biến của (cid:0)

1,(cid:0)

n vào V'

2, • Lặp lại cho đến khi không còn biến nào được thêm vào nữa

Các ký hiệu vô ích

Định lý 5.2: mỗi ngôn ngữ phi ngữ cảnh (CFL) không rỗng được

sinh ra từ một văn phạm phi ngữ cảnh (CFG) không có ký hiệu vô ích

Ví dụ: xét văn phạm

S → A A → aBb | ε B → A | cB | cC C → AC | BCD D → ab

• Áp dụng bổ đề 1: V' = {S, A, B, D}

• Áp dụng bổ đề 2: V' = {S, A, B} S → A A → aBb | ε B → A | cB

S → A A → aBb | ε B → A | cB D → ab

Luật sinh ε

Cho CFG G(V, T, P, S) và L là ngôn ngữ sinh ra bởi G. Khi đó L – {ε} là ngôn ngữ sinh ra bởi CFG G'(V, T, P', S) không có ký hiệu vô ích và không có luật sinh ε.

Định lý 5.3: (loại bỏ luật sinh A (cid:0) ε)

➢ Bước 1: xác định tập biến rỗng Nullable

Cách tìm:

Nullable (cid:0)

(cid:0)

➢ Bước 2: xây dựng tập luật sinh P'

i. A (cid:0) ii.B (cid:0) A (cid:0) B (cid:0) Nullable Nullable ε X1X2...Xn, (cid:0) Xi (cid:0)

Với mỗi luật sinh A (cid:0) X1X2...Xn trong P, ta xây dựng luật sinh

n với điều kiện: Nullable thì (cid:0) Nullable thì (cid:0)

(cid:0) ε

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) A (cid:0)

i = Xi i = Xi (cid:0) i đều bằng ε

i. Nếu Xi (cid:0) ii. Nếu Xi (cid:0) iii. Không phải tất cả (cid:0)

Luật sinh ε

➢ Bước 1: xác định tập biến rỗng Nullable

Ví dụ: loại bỏ luật sinh ε trong văn phạm sau: S (cid:0) A (cid:0) B (cid:0) AB aA (cid:0) bB (cid:0) (cid:0) ε (cid:0) ε

(cid:0)

➢ Bước 2: xây dựng tập luật sinh P'

i. A (cid:0) ii. B (cid:0) iii.S (cid:0) ε ε AB (cid:0) A (cid:0) B (cid:0) S (cid:0) Nullable Nullable Nullable

(cid:0) εB

S (cid:0) A (cid:0) B (cid:0) AB (cid:0) aA (cid:0) bB (cid:0) (cid:0) Aε (cid:0) (cid:0) aε (cid:0) bε

Chú ý: văn phạm G' không chấp nhận chuỗi rỗng ε như văn phạm G.

15 (cid:0) ε vào G'.

Để G' tương đương G, ta cần thêm luật sinh S (cid:0)

Luật sinh đơn vị

Định lý 5.4: (loại bỏ luật sinh A (cid:0) B)

Mỗi CFL không chứa ε được sinh ra bởi CFG không có ký hiệu vô ích, không có luật sinh ε hoặc luật sinh đơn vị.

Cách tìm: đặt L=L(G) là CFL không chứa ε và được sinh ra bởi văn phạm G(V, T, P, S). Theo định lý 3, ta có thể loại bỏ tất cả luật sinh ε trong G.

V) do

Để loại bỏ luật sinh đơn vị, ta xây dựng tập P' mới theo giải thuật:

For (mỗi biến A (cid:0)

Begin

* B } ;

Tính ΔA = { B (cid:0) B (cid:0) For (mỗi biến B (cid:0)

(cid:0) (cid:0)

V và A (cid:0) ΔA) do For (mỗi luật sinh B (cid:0)

thuộc P) do

(cid:0) (cid:0)

If (B (cid:0)

không là luật sinh đơn vị) then 16

Thêm luật sinh A (cid:0)

vào P'

(cid:0) (cid:0)

End ;

Luật sinh đơn vị

Ví dụ: loại bỏ luật sinh đơn vị trong văn phạm

E (cid:0) T (cid:0) F (cid:0) E + T (cid:0) T T * F (cid:0) F (E) (cid:0) a

Ta có: ΔE = {E, T, F} (cid:0) E (cid:0) thêm vào P' các luật sinh E + T (cid:0) T * F (cid:0) (E) (cid:0) a

Tương tự:

(cid:0) (E) (cid:0) a

ΔT = {T, F} (cid:0) ΔF = {F} (cid:0)

thêm vào P' : T (cid:0) thêm vào P' : F (cid:0) T * F (cid:0) (E) (cid:0) a

Dạng chuẩn Chomsky (CNF)

Định lý 5.5: một ngôn ngữ phi ngữ cảnh bất kỳ không chứa ε đều

được sinh ra bằng một văn phạm nào đó mà các luật sinh có dạng A (cid:0) a, với A, B, C là biến và a là ký hiệu kết thúc. BC hoặc A (cid:0)

➢ Bước 1: thay thế tất cả các luật sinh có độ dài vế phải là 1 • Áp dụng định lý 4.4 để loại bỏ luật sinh đơn vị và ε

➢ Bước 2: thay thế tất cả luật sinh có độ dài vế phải lớn hơn 1 và có chứa ký hiệu kết thúc

Cách tìm: giả sử CFL L=L(G) với CFG G(V, T, P, S)

A (cid:0) X1X2...Xi...Xn

X1X2...Ca...Xn a A (cid:0) Ca (cid:0)

➢ Bước 3: thay thế các luật sinh mà vế phải có nhiều hơn 2 ký hiệu chưa kết thúc

B1 D1 B2 D2

A (cid:0) B1B2...Bm (m>2)

A (cid:0) D1 (cid:0) ... Dm-2 (cid:0) Bm-1 Bm

Dạng chuẩn Chomsky (CNF)

Ví dụ: tìm văn phạm có dạng CNF tương đương văn phạm sau:

S (cid:0) A (cid:0) B (cid:0) A (cid:0) ABA aA (cid:0) a (cid:0) B bB (cid:0) b

(cid:0) bB (cid:0) b (cid:0) ABA

Bước 1: Δs = {S, A, B} , ΔA = {A, B} , ΔB = {B} S (cid:0) A (cid:0) B (cid:0) aA (cid:0) a (cid:0) aA (cid:0) a (cid:0) bB (cid:0) b bB (cid:0) b

Bước 2: thay a bằng Ca và b bằng Cb trong các luật sinh có độ dài vế

phải > 1: (cid:0) CbB (cid:0) b (cid:0) ABA

CaA (cid:0) a (cid:0) CaA (cid:0) a (cid:0) CbB (cid:0) b CbB (cid:0) b a b S (cid:0) A (cid:0) B (cid:0) Ca (cid:0) Cb (cid:0)

Dạng chuẩn Chomsky (CNF)

(cid:0) CbB (cid:0) b (cid:0) AD1

Bước 3: thay thế các luật sinh có độ dài vế phải > 2: CaA (cid:0) a (cid:0) CaA (cid:0) a (cid:0) CbB (cid:0) b CbB (cid:0) b a b BA S (cid:0) A (cid:0) B (cid:0) Ca (cid:0) Cb (cid:0) D1 (cid:0)

Dạng chuẩn Greibach (GNF)

(cid:0) (cid:0)

1B(cid:0) 2 là luật sinh trong P r là các B - luật sinh; văn phạm G1(V, T, P1, S)

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) ...(cid:0)

2 và thêm vào

1B(cid:0)

(cid:0) (cid:0)

2 tương đương G

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) Bổ đề 3: (thay thế các luật sinh trực tiếp) Cho G(V, T, P, S) là một CFG, đặt A (cid:0) và B (cid:0) thu được từ G bằng cách loại bỏ luật sinh A (cid:0) luật sinh A (cid:0)

Bổ đề 4: (dùng loại bỏ văn phạm đệ quy trái)

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) A(cid:0) (cid:0) A(cid:0) (cid:0) A(cid:0)

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) ...(cid:0)

Đặt G(V, T, P, S) là CFG; A (cid:0) r là tập các A – luật 1 sinh có A là ký hiệu trái nhất của vế phải (luật sinh đệ quy trái). Đặt A (cid:0) (cid:0) {B}, T, P1, S) là s là các A - luật sinh còn lại; G1(V (cid:0) CFG được tạo thành bằng cách thêm biến mới B vào V và thay các A - luật sinh bằng các luật sinh dạng:

(cid:0) (cid:0) (cid:0) (cid:0)

iB (1 ≤ i ≤ r)

(1 ≤ i ≤ s) (cid:0) (cid:0) (cid:0) (cid:0) A (cid:0) A (cid:0) B (cid:0) B (cid:0)

Thì ta có G1 tương đương G, hay L(G) = L(G1)

Dạng chuẩn Greibach (GNF)

Định lý 5.6: mỗi CFL bất kỳ không chứa ε được sinh ra bởi một CFG

(cid:0) a(cid:0) với A là biến, a là ký hiệu kết

(cid:0) mà mỗi luật sinh có dạng A (cid:0) thúc và (cid:0) là một chuỗi các biến (có thể rỗng)

Đặt G là CFG sinh ra CFL không chứa ε

Bước 1: xây dựng G' có dạng CNF tương đương G Bước 2: đổi tên các biến trong G' thành A1, A2, ..., Am (m ≥1 ) với A1

là ký hiệu bắt đầu. Đặt V = {A1, A2, ..., Am}

(cid:0) thì j > i Bước 3: thay thế luật sinh sao cho nếu Ai (cid:0) (cid:0) Aj

(cid:0) (cid:0) a(cid:0) (j > i), Ai (cid:0) (cid:0) Aj

(cid:0) (cid:0) (cid:0) (cid:0) với (cid:0) (cid:0) (V (cid:0) • Nếu j

Bước 4: thay thế các Ai – luật sinh về đúng dạng (áp dụng bổ đề 3) Bước 5: thay thế các Bk – luật sinh về đúng dạng (bổ đề 3)

Dạng chuẩn Greibach (GNF)

(cid:0) thì j > i)

(cid:0) Ai

Giải thuật : (thay thế sao cho Ai

ạ

ỗ

Begin (1)   for k := 1 to m do begin (2)      for j := 1 to k1 do (3)

(cid:0)

A

ậ    for M i lu t sinh d ng A

do

k

j

begin

ấ ả ậ

(cid:0)

do

(cid:0)

ậ

(4)              for T t c lu t sinh A (5)                 Thêm lu t sinh A

(cid:0)

j (cid:0) (cid:0)

;

(cid:0)

ạ ỏ ậ

k (6)              Lo i b lu t sinh A

(cid:0)

A j

k

(cid:0)

end; ỗ

ạ

ậ

(cid:0)

A

(7)     for M i lu t sinh d ng A

do

k

k

begin

ậ

(cid:0)

và B

(cid:0)

(cid:0) B

;

k

k

k

(cid:0)

ạ ỏ ậ

(9)             Lo i b lu t sinh A

(8)             Thêm các lu t sinh B k (cid:0)

(cid:0) Ak

ậ

ằ

trong đó (cid:0)

do

k

ắ ầ không b t đ u b ng A k

ậ

end; ỗ (10)    for M i lu t sinh A (11)       Thêm lu t sinh A

(cid:0) (cid:0)

(cid:0) (cid:0) B

k

k

23

end; end;

(cid:0)

Dạng chuẩn Greibach (GNF)

Ví dụ: tìm văn phạm có dạng GNF cho văn phạm G sau:

(cid:0)

(cid:0) A2A3 (cid:0) a (cid:0) b

A2A1 A3A1 A2A2

(cid:0)

(cid:0) A2A2

(cid:0) • Áp dụng bổ đề 3: A3

(cid:0) b

(cid:0)

A1 (cid:0) A2 A3 Bước 1: G thỏa CNF Bước 2: ta có V = {A1, A2, A3} Bước 3: ta cần sửa đổi luật sinh A3 A3A1A2 A3

(cid:0) aA2

(cid:0) aA2 A3A1A2

(cid:0)

(cid:0) bB

(cid:0) aA2B

24

(cid:0)

(cid:0) A2A3 (cid:0) a (cid:0) b (cid:0) (cid:0) A1A2B

A1 (cid:0) A2 A3 B

(cid:0) • Áp dụng bổ đề 4, ta thu được tập luật sinh: A2A1 A3A1 aA2 A1A2

Dạng chuẩn Greibach (GNF)

Bước 4: A3 đã có dạng chuẩn. Thay thế A3 vào A2 :

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

(cid:0) aA2B

(cid:0)

(cid:0) bA1 (cid:0)

(cid:0) bB (cid:0) aA2BA1

(cid:0) bBA1 (cid:0) a

(cid:0)

(cid:0) B (cid:0) A3 A2 A1

(cid:0) A1A2B (cid:0) A1A2 (cid:0) aA2 (cid:0) b (cid:0) (cid:0) aA2A1 (cid:0) aA2A1A1 aA2A1A3

(cid:0) bA1A1 (cid:0) (cid:0) bA1A3 (cid:0)

(cid:0) aA2BA1A1 (cid:0) aA2BA1A3

(cid:0) (cid:0) bBA1A1 (cid:0) aA1 (cid:0) bBA1A3 (cid:0) aA3

(cid:0)

B (cid:0)

Bước 5: thay thế các Bk – luật sinh

(cid:0) bA1A1A2 (cid:0) (cid:0) bA1A3A2 (cid:0)

(cid:0) aA2BA1A1A2 (cid:0) aA2BA1A3A2

(cid:0) (cid:0) bBA1A1A2 (cid:0) aA1A2 (cid:0) bBA1A3A2 (cid:0) aA3A2

(cid:0)

(cid:0) aA2A1A1A2 aA2A1A3A2 (cid:0) aA2A1A1A2B(cid:0) bA1A1A2B (cid:0) (cid:0) bA1A3A2B (cid:0) aA2A1A3A2B

(cid:0) aA2BA1A1A2B (cid:0) aA2BA1A3A2B

(cid:0) bBA1A1A2B (cid:0) aA1A2B(cid:0) (cid:0) bBA1A3A2B (cid:0) aA3A2B

25

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

Bổ đề bơm cho CFL

Bổ đề bơm: cho L là một CFL bất kỳ, tồn tại một số n chỉ phụ thuộc

L và |z| ≥ n thì ta có thể viết z=uvwxy sao

vào L sao cho nếu z (cid:0) cho: |vx| ≥ 1, |vwx| ≤ n và (cid:0) i ≥ 0 ta có uviwxiy (cid:0) L

Ví dụ: chứng minh L = {aibici | i ≥ 1} không là CFL

• Giả sử L là CFL, khi đó tồn tại số n theo bổ đề bơm • Xét chuỗi z = anbncn, |z| ≥ n, ta có thể viết z=uvwxy thỏa bổ đề (cid:0) anbncn, |vwx| ≤ n nên vwx không thể đồng thời • Ta có: vwx (cid:0) chứa cả ký hiệu a và c (vì giữa a và c có n ký hiệu b) → vx cũng không thể chứa cả ký hiệu a và c. • Do |vx| ≥ 1 và trong uvwxy chứa số ký hiệu a, b, c bằng nhau:

26

 Nếu vx có chứa ký hiệu a (nên không thể chứa ký hiệu c) thì khi bơm chuỗi vx, số ký hiệu c sẽ không đổi (luôn là n), nhưng số ký hiệu a sẽ thay đổi. Ví dụ: chuỗi uv0wx0y (cid:0) hiệu a (ít hơn n) số ký hiệu c (luôn là n) không bằng nhau.  Nếu vx không chứa ký hiệu a thì khi bơm chuỗi vx, số ký hiệu a không đổi, nhưng số ký hiệu b (hoặc c) sẽ thay đổi.

L vì có số ký

Tính chất đóng của CFL

Định lý 5.7: CFL đóng với phép hợp, phép kết nối và phép bao đóng

Kleen.

Định lý 5.8: CFL không đóng với phép giao

27

Hệ quả: CFL không đóng với phép lấy phần bù