Bài giảng Tin học - Chương 5l Văn phạm phi ngữ cảnh

1• 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 2 là hệ thống gồm 4 thành phần • 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 ∩ T = Ø) • P : tập hữu hạn các luật sinh dạng A → α α∈ (V∪T • S : ký hiệu bắt ñầu của văn phạm S → AB A → aA A → a B → bB B → b S → AB A → aAa B → bBb hay Q u y ư  c : • V: chữ in hoa (A, B, C, ..); T: chữ in thường (a, b, c, .., w, x, y..) • α, β, γ, .. biểu diễn chuỗi ký hiệu kết thúc và biến V í d : G=({S, A, B}, {a, b}, P, S) với P gồm các luật sinh: 3 • Nếu A → β là luật sinh trong văn phạm G và α, γ là 2 chuỗi bất kỳ, thì khi áp dụng luật sinh A → β vào chuỗi α γ ta sẽ thu ñược chuỗi αβγ : α γ ⇒ G αβγ • Giả sử: α1 ⇒G α2, α2 ⇒G α3, ..., αm-1 ⇒G αm, ta có: α 1 ⇒ G α m • Ta có: α ⇒ G α với mọi chuỗi α • Thông thường, ta sẽ dùng ⇒ và ⇒ thay cho ⇒G và ⇒ G cho CFG G(V, T, P, S)  ∈ ⇒ G (chuỗi w gồm toàn ký hiệu kết thúc và ñược dẫn ra từ S) 4 cây dẫn xuất (hay cây phân tích cú pháp) của một văn 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 ∈ (V ∪ T ∪ {ε} ) (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 ∈ V (4) Nếu nút n có nhãn A và các ñỉnh n 1 , n 2 , ..., n k là con của n theo thứ tự từ trái sang phải có nhãn lần lượt là X 1 , X 2 , ..., X k thì A → X 1 X 2 ...X k 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ó Printed with FinePrint - purchase at www.fineprint.com 5xét văn phạm G({S, A}, {a, b}, P, S}, với P gồm: S → aASa A → SbASSba Một dẫn xuất của G: S ⇒ aAS ⇒ aSbAS ⇒ aabAS ⇒ aabbaS ⇒ aabbaa 1 3 6 10 2 5 9 4 7 8 11 S A b b a S a S A a a nếu G(V, T, P, S) là một CFG thì ⇒ α nếu và chỉ nếu có cây dẫn xuất trong văn phạm sinh ra α. 6 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) xét văn phạm G với luật sinh: → →  →  • Các dẫn xuất khác nhau cho từ : ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ • 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 7 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. xét văn phạm G với luật sinh: E → E + E  E * E  (E)  a Với chuỗi , ta có thể vẽ ñến 2 cây dẫn xuất khác nhau a E E E + EE a a E E + E E E a a a ð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: hoặc 8 • Hoặc 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 → E + T  E * T  T T → (E)  a • Hoặc 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 → E + T  T T → T * F  F F → (E)  a Printed with FinePrint - purchase at www.fineprint.com 9● 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 → B (làm kéo dài chuỗi dẫn xuất) ⇒ g i  n l ư c v ă n p h m n h m l o i b  n h  n g y  u t  v ô í c h , n h ưn g k h ô n g ñ ư c l à m t h a y ñ  i k h  n ă n g s  n s i n h n g ô n n g  c fi a v ă n p h 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 → B (với A, B ñều là biến) ● Nếu ngôn ngữ không chấp nhận chuỗi rỗng ε thì không cần luật sinh A → ε . 10 một ký hiệu X ñược gọi là có ích nếu có một dẫn xuất ⇒ α β ⇒ với α, β là các chuỗi bất kỳ và w ∈ T*. ⇒ c ó 2 ñ  c ñ i m c h o k ý h i " u c ó í c h • 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 11 ( l o & i b ) c á c b i , n k h ô n g d 3 n r a c h u 7 i k ý h i 9 u k , t t h ú 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 ∈ tồn tại ∈ ñể ⇒ Begin ( 1 ) O l d V ' : = ∅ ; ( 2 ) N e w V ' : = { A  A → w v O i w ∈ T * } ; ( 3 ) While O l d V ' ≠ N e w V ' do begin ( 4 ) O l d V ' : = N e w V ' ; ( 5 ) N e w V ' : = O l d V ' ∪ { A  A → α v O i α ∈ ( T ∪ O l d V ' ) * } end; ( 6 ) V ' : = N e w V ' ; End; 12 ( l o & i b ) c á c b i , n k h ô n g ñ ư Zc d 3 n r a t [ k ý h i 9 u b \ t ñ ] u ) 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 ∈ ∪ tồn tại α β ∈ ∪ ñể ⇒ α β • ðặt V' = {S} ; T' = Ø • Nếu A ∈ V' và A → α 1 α 2...α n là các luật sinh trong P thì ➢ Thêm các biến của α 1 α 2 ..., α n vào ➢ Thêm các ký hiệu kết thúc của α 1 α 2 ..., α n vào • Lặp lại cho ñến khi không còn biến hoặc ký hiệu kết thúc nào ñược thêm vào nữa Printed with FinePrint - purchase at www.fineprint.com 13 xét văn phạm S → A A → aBb | ε B → A | cB | cC C → AC | BCD D → ab • Áp dng b ñ 1: V' = {S, A, B, D} S → A A → aBb | ε B → A | cB D → ab • Áp dng b ñ 2: V' = {S, A, B} S → A A → aBb | ε B → A | cB 14 ( l o & i b ) l u t s i n h A → ε ) 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 ε. ➢ B ư  c 1 : xác ñịnh tập biến rỗng Nullable i. A → ε ⇒ A ∈ Nullable ii.B → X 1 X 2 ...X n , ∀X i ∈ Nullable⇒ B ∈ Nullable ➢ B ư  c 2 : xây dựng tập luật sinh P' Với mỗi luật sinh A → X 1 X 2 ...X n trong P, ta xây dựng luật sinh A → α 1 α 2 ...α n với ñiều kiện: i. Nếu X i ∉ Nullable thì α i = X i ii. Nếu X i ∈ Nullable thì α i = X i  ε iii. Không phải tất cả α i ñều bằng ε 15 loại bỏ luật sinh ε trong văn phạm sau: S → AB A → aA  ε B → bB  ε ➢ B ư  c 1 : xác ñịnh tập biến rỗng Nullable i. A → ε ⇒ A ∈ Nullable ii. B → ε ⇒ B ∈ Nullable iii.S → AB ⇒ S ∈ Nullable ➢ B ư  c 2 : xây dựng tập luật sinh P' S → AB  Aε  εB A → aA  aε B → bB  bε C h ú ý : văn phạm G' không chấp nhận chuỗi rỗng ε như văn phạm G. ðể G' tương ñương G, ta cần thêm luật sinh S → ε vào G'. 16 ( l o & i b ) l u t s i n h A → 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ị. ñặ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. ðể loại bỏ luật sinh ñơn vị, ta xây dựng tập P' mới theo giải thuật: F o r (mỗi biến A ∈ V) d o B e g i n Tính ∆ A = { B  B ∈ V và A ⇒ * B } ; F o r (mỗi biến B ∈ ∆ A ) d o F o r (mỗi luật sinh B → α thuộc P) d o I f (B → α không là luật sinh ñơn vị) t h e n Thêm luật sinh A → α vào P' E n d ; Printed with FinePrint - purchase at www.fineprint.com 17 loại bỏ luật sinh ñơn vị trong văn phạm E → E + T  T T → T * F  F F → (E)  a Ta có: ∆ E = {E, T, F} ⇒ thêm vào P' các luật sinh E → E + T T * F  (E)  a Tương tự: ∆ T = {T, F} ⇒ thêm vào P' : T → T * F  (E)  a ∆ F = {F} ⇒ thêm vào P' : F → (E)  a 18 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 → BC hoặc A → a, với A, B, C là biến và a là ký hiệu kết thúc. giả sử CFL L=L(G) với CFG G(V, T, P, S) ➢ 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 ➢ 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 A → X 1 X 2 ...X i ...X n a A → X 1 X 2 ...C a ...X n C a → a A → B 1 B 2 ...B m (m>2) A → B1 D1 D 1 → B 2 D 2 ... D m-2 → B m-1 B m 19 tìm văn phạm có dạng CNF tương ñương văn phạm sau: S → A  ABA A → aA  a  B B → bB  b B ư  c 1 : ∆ s = {S, A, B} , ∆ A = {A, B} , ∆ B = {B} S → aA  a  bB  b  ABA A → aA  a  bB  b B → bB  b B ư  c 2 : thay a bằng C a và b bằng C b trong các luật sinh có ñộ dài vế phải > 1: S → C a A  a  C b B  b  ABA A → C a A  a  C b B  b B → C b B  b C a → a C b → b 20 B ư  c 3 : thay thế các luật sinh có ñộ dài vế phải > 2: → C a A  a  C b B  b  A 1 A → C a A  a  C b B  b B → C b B  b C a → a C b → b 1 → Printed with FinePrint - purchase at www.fineprint.com 21 (t h a y t h , c á c l u t s i n h t r
c t i , p ) Cho G(V, T, P, S) là một CFG, ñặt A → α 1 Bα 2 là luật sinh trong P và B → β 1 β 2  β r là các B - luật sinh; văn phạm G 1 (V, T, P 1 , S) thu ñược từ G bằng cách loại bỏ luật sinh A → α 1 Bα 2 và thêm vào luật sinh A → α 1 β 1 α 2 α 1 β 2 α 2 ...α 1 β r α 2 tương ñương G ( d ù n g l o & i b ) v ă n p h & m ñ 9 q u y t r á i ) ðặt G(V, T, P, S) là CFG; A → Aα 1 Aα 2 ...Aα r là tập các A – luật sinh có A là ký hiệu trái nhất của vế phải (luật sinh ñệ quy trái). ðặt A → β 1 β 2  β s là các A - luật sinh còn lại; G 1 (V ∪ {B}, T, P 1 , S) là 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: A → β i A → βiB (1 ≤ i ≤ s) B → α i B → α i B (1 ≤ i ≤ r) Thì ta có G 1 tương ñương G, hay L(G) = L(G 1 ) 22 mỗi CFL bất kỳ không chứa ε ñược sinh ra bởi một CFG mà mỗi luật sinh có dạng A → aα với A là biến, a là ký hiệu kết thúc và α là một c h u  i c á c b i  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 A 1 , A 2 , ..., A m (m ≥1 ) với A 1 là ký hiệu bắt ñầu. ðặt V = {A 1 , A 2 , ..., A m } B ư  c 3 : thay thế luật sinh sao cho nếu A i → A j γ thì j > i • Nếu j<i : áp dụng bổ ñề 3. Nếu i=j : áp dụng bổ ñề 4 ( g i  i t h u  t ) • Trong P chỉ chứa các luật sinh dạng: Ai → Ajγ (j > i), Ai → aγ hoặc B k → γ với γ ∈ (V ∪ {B 1 ,B 2 , ...,B i-1 })* B ư  c 4 : thay thế các A i – luật sinh về ñúng dạng ( á p d n g b  ñ  3 ) B ư  c 5 : thay thế các B k – luật sinh về ñúng dạng ( b  ñ  3 ) 23 (t h a y t h , s a o c h o A i→ A i γ t h ì j > i ) Begin (1) for k := 1 to m do begin (2) for j := 1 to k-1 do (3) for Mỗi luật sinh dạng A k → A j α do begin (4) for Tất cả luật sinh A j → β do (5) Thêm luật sinh A k → βα; (6) Loại bỏ luật sinh A k → A j α end; (7) for Mỗi luật sinh dạng A k → A k α do begin (8) Thêm các luật sinh B k → α và B k → αB k ; (9) Loại bỏ luật sinh A k → A k α end; (10) for Mỗi luật sinh A k → β trong ñó β không bắt ñầu bằng A k do (11) Thêm luật sinh A k → βB k end; end; 24 tìm văn phạm có dạng GNF cho văn phạm G sau: A 1 → A 2 A 1  A 2 A 3 A 2 → A 3 A 1  a A 3 → A 2 A 2  b B ư  c 1 : G thỏa CNF B ư  c 2 : ta có V = {A 1 , A 2 , A 3 } B ư  c 3 : ta cần sửa ñổi luật sinh A 3 → A 2 A 2 • Áp dụng bổ ñề 3: A3 → A3A1A2 aA2 A 3 → A 3 A 1 A 2  a A 2  b • Áp dụng bổ ñề 4, ta thu ñược tập luật sinh: A 1 → A 2 A 1  A 2 A 3 A 2 → A 3 A 1  a A 3 → aA 2  b  aA 2 B  bB B → A 1 A 2  A 1 A 2 B Printed with FinePrint - purchase at www.fineprint.com 25 B ư  c 4 : A 3 ñã có dạng chuẩn. Thay thế A 3 vào A 2 : B → A 1 A 2  A 1 A 2 B A 3 → aA 2  b  aA 2 B  bB A 2 → aA 2 A 1  bA 1  aA 2 BA 1  bBA 1  a A 1 → aA 2 A 1 A 1  bA 1 A 1  aA 2 BA 1 A 1  bBA 1 A 1  aA 1  aA 2 A 1 A 3  bA 1 A 3  aA 2 BA 1 A 3  bBA 1 A 3  aA 3 B ư  c 5 : thay thế các B k – luật sinh B → aA 2 A 1 A 1 A 2  bA 1 A 1 A 2  aA 2 BA 1 A 1 A 2  bBA 1 A 1 A 2  aA 1 A 2  aA 2 A 1 A 3 A 2  bA 1 A 3 A 2  aA 2 BA 1 A 3 A 2  bBA 1 A 3 A 2  aA 3 A 2 





aA 2 A 1 A 1 A 2 B bA 1 A 1 A 2 B  aA 2 BA 1 A 1 A 2 B  bBA 1 A 1 A 2 B  aA 1 A 2 B aA 2 A 1 A 3 A 2 B  bA 1 A 3 A 2 B  aA 2 BA 1 A 3 A 2 B  bBA 1 A 3 A 2 B  aA 3 A 2 B 26 cho L là một CFL bất kỳ, tồn tại một số n chỉ phụ thuộc vào L sao cho nếu z ∈ L và |z| ≥ n thì ta có thể viết z=uvwxy sao cho: |vx| ≥ 1, |vwx| ≤ n và ∀i ≥ 0 ta có uviwxiy ∈ L chứng minh một ngôn ngữ không là CFL 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ổ ñề • Ta có: vx ∈ anbncn, |vx| ≤ |vwx| ≤ n nên vx không thể chứa cả ký hiệu a và c (vì giữa a và c có n ký hiệu b) • Do |vx| ≥ 1 và trong uvwxy chứa số ký hiệu a, b, c bằng nhau:  Nếu vx có chứa ký hiệu a (và không chứa ký hiệu c) thì chuỗi uv0wx0y ∉ L vì có số ký hiệu c lớn hơn số ký hiệu a  Nếu vx không chứa ký hiệu a thì chuỗi uv0wx0y ∉ L vì có số ký hiệu b (hoặc c) nhỏ hơn số ký hiệu a 27 CFL ñóng với phép hợp, phép kết nối và phép bao ñóng Kleen. CFL không ñóng với phép giao CFL không ñóng với phép lấy phần bù Printed with FinePrint - purchase at www.fineprint.com