Bài giảng Tin học lí thuyết: Chương 5 - Võ Huỳnh Trâm

Chia sẻ: Thanh Hoa | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

63
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Tin học lí thuyết - Chương 5: Văn phạm phi ngữ cảnh" cung cấp cho người học các kiến thức: 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. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Tin học lí thuyết: Chương 5 - Võ Huỳnh Trâm

• 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 αβγ : • Văn phạm phi ngữ cảnh (CFG) α γ ⇒G αβ βγ • Giả sử: α1 ⇒G α2, α2 ⇒G α3, ..., αm-1 ⇒G αm, ta có: • Giản lược văn phạm phi ngữ cảnh α1 ⇒ G αm • Chuẩn hóa văn phạm phi ngữ cảnh • Ta có: α ⇒ G α với mọi chuỗi α • Các tính chất của văn phạm phi ngữ cảnh • 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) 1 3 là hệ thống gồm 4 thành phần cây dẫn xuất (hay cây phân tích cú pháp) của một văn • V : tập hữu hạn các biến (ký tự chưa kết thúc) phạm G(V, T, P, S) có ñặc ñiểm • T : tập hữu hạn các ký tự kết thúc (V ∩ T = Ø) (1) Mỗi nút có một nhãn, là một ký hiệu ∈ (V ∪ T ∪ {ε} ) • P : tập hữu hạn các luật sinh dạng A → α α∈ (V∪T (2) Nút gốc có nhãn là S (ký hiệu bắt ñầu) • S : ký hiệu bắt ñầu của văn phạm (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 n1, n2, ..., nk là con của n Q : u y ư c • V: chữ in hoa (A, B, C, ..); T: chữ in thường (a, b, c, .., w, x, y..) theo thứ tự từ trái sang phải có nhãn lần lượt là X1, X2, ..., Xk thì • α, β, γ, .. biểu diễn chuỗi ký hiệu kết thúc và biến A → X1X2...Xk là một luật sinh trong P V í d : G=({S, A, B}, {a, b}, P, S) với P gồm các luật sinh: (5) Nếu nút n có nhãn là ε thì n phải là nút lá và là nút con duy S → AB nhất của nút cha của nó A → aA S → AB A→a hay A → aAa B → bB B → bBb 2 4 B→b Printed with FinePrint - purchase at www.fineprint.com
xét văn phạm G({S, A}, {a, b}, P, S}, với P gồm: S → aASa một văn phạm phi ngữ cảnh G ñược gọi là văn phạm A → SbASSba mơ hồ (ambiguity) nếu nó có nhiều hơn một cây dẫn xuất cho Một dẫn xuất của G: cùng một chuỗi w. S ⇒ aAS ⇒ aSbAS ⇒ aabAS ⇒ aabbaS ⇒ aabbaa xét văn phạm G với luật sinh: S 1 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 S E a E A 2 3 4 E E E E + S A a 5 b 6 7 8 a a + E E E E a a b 11 9 10 a 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 nếu G(V, T, P, S) là một CFG thì ⇒ α nếu và chỉ 5 nhau: hoặc 7 nếu có cây dẫn xuất trong văn phạm sinh ra α. 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) • Hoặc quy ñịnh rằng các phép cộng và nhân luôn ñược thực xét văn phạm G với luật sinh: → 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 • Các dẫn xuất khác nhau cho từ : • 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 • 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 6 8 Printed with FinePrint - purchase at www.fineprint.com
, 3 7 , ) ( l i b á b i k h ô d h i k ý h i 9 k t t h ú ) o & c c n n g n r a c u u c ● Các ký hiệu không tham gia vào quá trình dẫn xuất ra chuỗi ký Cho CFG G(V, T, P, S) với L(G) ≠ Ø, có một CFG G'(V', T', P', S) hiệu kết thúc tương ñương sao cho mỗi ∈ tồn tại ∈ ñể ⇒ ● Luật sinh dạng A → B (làm kéo dài chuỗi dẫn xuất) ⇒
Begin i l ă h h l i b h t ô í h h g n ư c v n p m n m o n n g y u v c n n ư g , ∅ ( 1 ) O l d V ' k h ô ñ l à t h ñ i k h ă i h ô ă : = ; n g ư c m a y n n g s n s n n g n n g c a v n  → ∈ ( 2 ) N V ' { A A O i T * } e w : = w v w ; h p m ≠ ( 3 ) O l d V ' N V ' While do e w • Mỗi biến và mỗi ký hiệu kết thúc của văn phạm ñều xuất begin ( 4 ) O l d V ' N V ' hiện trong dẫn xuất của một số chuỗi trong ngôn ngữ : = e w ; ∪  →α α∈ ∪ ( 5 ) N V ' O l d V ' { A A O i ( T O l d V ' ) * } • Không có luật sinh A → B (với A, B ñều là biến) e w : = v end; ● Nếu ngôn ngữ không chấp nhận chuỗi rỗng ε thì không cần luật ( 6 ) V ' N V ' : = e w ; sinh A → ε . 9 11 End; , 3 \ ] ) một ký hiệu X ñược gọi là có ích nếu có một dẫn xuất ( l i b á b i k h ô ñ d t [ k ý h i 9 b t ñ ) o & c c n n g ư c Z n r a u u ⇒ α β⇒ Cho CFG G(V, T, P, S), ta có thể tìm ñược CFG G'(V', T', P', S) với α, β là các chuỗi bất kỳ và w ∈ T*. tương ñương sao cho mỗi ∈ ∪ tồn tại α β ∈ ∪ ñể ⇒ α β ⇒ ó 2 ñ ñ i h k ý h i " ó í h c c m c o u c c • X phải dẫn ra chuỗi ký hiệu kết thúc • ðặt V' = {S} ; T' = Ø • X phải nằm trong dẫn xuất từ S • Nếu A ∈ V' và A → α  α ...α là các luật sinh trong P thì 1 2 n ➢ Thêm các biến của α α ..., α vào 1 2 n ➢ Thêm các ký hiệu kết thúc của α α ..., α vào 1 2 n • 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 10 12 Printed with FinePrint - purchase at www.fineprint.com
loại bỏ luật sinh ε trong văn phạm sau: S → AB A → aA  ε B → bB  ε xét văn phạm S→A B 1 ➢ : xác ñịnh tập biến rỗng Nullable ư c A → aBb | ε i. A → ε ⇒ A ∈ Nullable B → A | cB | cC ii. B → ε ⇒ B ∈ Nullable C → AC | BCD iii.S → AB ⇒ S ∈ Nullable D → ab B 2 ➢ xây dựng tập luật sinh P' ư c : • Áp dng b ñ 1: • Áp dng b ñ 2: S → AB  Aε  εB V' = {S, A, B, D} V' = {S, A, B} A → aA  aε S→A S→A B → bB  bε A → aBb | ε A → aBb | ε C h ú ý B → A | cB : văn phạm G' không chấp nhận chuỗi rỗng ε như văn phạm G. B → A | cB 13 ðể G' tương ñương G, ta cần thêm luật sinh S → ε vào G'. 15 D → ab → ) → ( l i b l t i h A B ) ) o & u s n ( l i b l t i h A ) o & u s n ε Cho CFG G(V, T, P, S) và L là ngôn ngữ sinh ra bởi G. Khi ñó L – {ε} là Mỗi CFL không chứa ε ñược sinh ra bởi CFG không có ký hiệu vô ngôn ngữ sinh ra bởi CFG G'(V, T, P', S) không có ký hiệu vô ích và ích, không có luật sinh ε hoặc luật sinh ñơn vị. không có luật sinh ε. ñặ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. B 1 ➢ : xác ñịnh tập biến rỗng Nullable ư c i. A → ε ⇒ A ∈ Nullable ðể loại bỏ luật sinh ñơn vị, ta xây dựng tập P' mới theo giải thuật: ii.B → X1X2...Xn, ∀Xi ∈ Nullable ⇒ B ∈ Nullable F (mỗi biến A ∈ V) d o r o B 2 ➢ xây dựng tập luật sinh P' ư c : B i e g n Với mỗi luật sinh A → X1X2...Xn trong P, ta xây dựng luật sinh Tính ∆A = { B  B ∈ V và A ⇒ B } ; * A → α1α2...αn với ñiều kiện: (mỗi biến B ∈ ∆A) F d o r o i. Nếu Xi ∉ Nullable thì αi = Xi (mỗi luật sinh B → α thuộc P) F d o r o (B → α không là luật sinh ñơn vị) I f t h ii. Nếu Xi ∈ Nullable thì αi = Xi  ε e n 14 Thêm luật sinh A → α vào P' 16 iii. Không phải tất cả αi ñều bằng ε ; E d n Printed with FinePrint - purchase at www.fineprint.com
loại bỏ luật sinh ñơn vị trong văn phạm tìm văn phạm có dạng CNF tương ñương văn phạm sau: E→E+TT S → A  ABA A → aA  a  B T→T*FF B → bB  b F → (E)  a B 1 : ∆s = {S, A, B} , ∆A = {A, B} , ∆B = {B} ư c Ta có: ∆E = {E, T, F} ⇒ thêm vào P' các luật sinh S → aA  a  bB  b  ABA A → aA  a  bB  b E → E + T T * F  (E)  a B → bB  b Tương tự: B 2 : thay a bằng Ca và b bằng Cb trong các luật sinh có ñộ dài vế ư c ∆T = {T, F} ⇒ thêm vào P' : T → T * F  (E)  a phải > 1: S → CaA  a  CbB  b  ABA ∆F = {F} ⇒ thêm vào P' : F → (E)  a A → CaA  a  CbB  b B → CbB  b Ca → a 17 Cb → b 19 một ngôn ngữ phi ngữ cảnh bất kỳ không chứa ε ñều B 3 : thay thế các luật sinh có ñộ dài vế phải > 2: ư c ñược sinh ra bằng một văn phạm nào ñó mà các luật sinh có dạng → CaA  a  CbB  b  A A → BC hoặc A → a, với A, B, C là biến và a là ký hiệu kết thúc. 1 A → CaA  a  CbB  b giả sử CFL L=L(G) với CFG G(V, T, P, S) B → CbB  b B 1 ➢ : thay thế tất cả các luật sinh có ñộ dài vế phải là 1 ư c • Áp dụng ñịnh lý 4.4 ñể loại bỏ luật sinh ñơn vị và ε Ca → a Cb → b B 2 ➢ : thay thế tất cả luật sinh có ñộ dài vế phải lớn hơn 1 và ư c có chứa ký hiệu kết thúc → 1 A → X1X2...Xi...Xn A → X1X2...Ca...Xn Ca → a a B 3 ➢ : thay thế các luật sinh mà vế phải có nhiều hơn 2 ký ư c hiệu chưa kết thúc A → B1 D1 D1 → B2 D2 A → B1B2...Bm (m>2) ... 18 20 Dm-2 → Bm-1 Bm Printed with FinePrint - purchase at www.fineprint.com
→ γ , , , t ( h t h á l t i h t t i ) t ( h t h h A A t h ì j i ) > a y c c u s n r c p a y s a o c o i i Cho G(V, T, P, S) là một CFG, ñặt A → α1Bα2 là luật sinh trong P Begin (1) for k := 1 to m do begin và B → β1β2 βr là các B - luật sinh; văn phạm G1(V, T, P1, S) (2) for j := 1 to k-1 do for Mỗi luật sinh dạng Ak → Ajα do thu ñược từ G bằng cách loại bỏ luật sinh A → α1Bα2 và thêm vào (3) begin luật sinh A → α1β1α2α1β2α2...α ... 1βrα2 tương ñương G (4) for Tất cả luật sinh Aj → β do ) (5) Thêm luật sinh Ak → βα; ( d ù l i b ă h ñ 9 t á i ) n g o & v n p & m q u y r (6) Loại bỏ luật sinh Ak → Ajα ðặt G(V, T, P, S) là CFG; A → Aα1Aα2...Aα ... r là tập các A – luật end; sinh có A là ký hiệu trái nhất của vế phải (luật sinh ñệ quy trái). ðặt (7) for Mỗi luật sinh dạng Ak → Akα do A → β1β2 βs là các A - luật sinh còn lại; G1(V ∪ {B}, T, P1, S) là begin (8) Thêm các luật sinh Bk → α và Bk → αBk; CFG ñược tạo thành bằng cách thêm biến mới B vào V và thay (9) Loại bỏ luật sinh Ak → Akα các A - luật sinh bằng các luật sinh dạng: end; A → βi B → αi (10) for Mỗi luật sinh Ak → β trong ñó β không bắt ñầu bằng Ak do (1 ≤ i ≤ s) Thêm luật sinh Ak → βBk A → βi B B → αiB (1 ≤ i ≤ r) 21 (11) 23 end; Thì ta có G1 tương ñương G, hay L(G) = L(G1) end; mỗi CFL bất kỳ không chứa ε ñược sinh ra bởi một CFG tìm văn phạm có dạng GNF cho văn phạm G sau: mà mỗi luật sinh có dạng A → aα với A là biến, a là ký hiệu kết A1 → A2A1 A2A3 thúc và α là một A2 → A3A1 a h i á b i (có thể rỗng) c u c c n ðặt G là CFG sinh ra CFL không chứa ε A3 → A2A2 b B 1 : G thỏa CNF ư c B 1 : xây dựng G' có dạng CNF tương ñương G ư c B 2 : ta có V = {A1, A2, A3} ư c B 2 : ñổi tên các biến trong G' thành A1, A2, ..., Am (m ≥1 ) với A1 ư c : ta cần sửa ñổi luật sinh A3 → A2A2 B 3 ư c là ký hiệu bắt ñầu. ðặt V = {A1, A2, ..., Am} • Áp dụng bổ ñề 3: A3 → A3A1A2 aA2 : thay thế luật sinh sao cho nếu Ai → Ajγ thì j > i B 3 ư c →   A A A A A b a 3 3 1 2 2 • Nếu j i), Ai → aγ A1 → A2A1 A2A3 hoặc Bk → γ với γ ∈ (V ∪ {B1,B2, ...,Bi-1})* A2 → A3A1 a B 4 ( á d b ñ 3 ) : thay thế các Ai – luật sinh về ñúng dạng ư c p n g A3 → aA2  b  aA2B  bB B 5 ( b ñ 3 ) : thay thế các Bk – luật sinh về ñúng dạng B → A1A2 A1A2B ư c 22 24 Printed with FinePrint - purchase at www.fineprint.com
B 4 : A3 ñã có dạng chuẩn. Thay thế A3 vào A2 : ư c CFL ñóng với phép hợp, phép kết nối và phép bao ñóng B → A1A2 A1A2B Kleen. A3→ aA2  b  aA2B  bB A2→ aA2A1  bA1  aA2BA1  bBA1  a CFL không ñóng với phép giao A1→ aA2A1A1  bA1A1  aA2BA1A1  bBA1A1  aA1 aA2A1A3  bA1A3  aA2BA1A3  bBA1A3  aA3 CFL không ñóng với phép lấy phần bù B 5 : thay thế các Bk – luật sinh ư c B → aA2A1A1A2  bA1A1A2  aA2BA1A1A2  bBA1A1A2  aA1A2 aA2A1A3A2  bA1A3A2  aA2BA1A3A2  bBA1A3A2  aA3A2   bA1A1A2B  aA2BA1A1A2B  bBA1A1A2B  aA1A2B  aA2A1A1A2B aA2A1A3A2B  bA1A3A2B  aA2BA1A3A2B  bBA1A3A2B  aA3A2B 25 27 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 26 Printed with FinePrint - purchase at www.fineprint.com