Bài giảng Toán giải tích - Chương 5: Văn phạm phi ngữ cảnh
lượt xem 9
download
Bài giảng "Toán giải tích - Chương 5: Văn phạm phi ngữ cảnh" cung cấp cho người đọc các kiến thức: Văn phạm phi ngữ cảnh, 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.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Toán giải tích - Chương 5: Văn phạm phi ngữ cảnh
- 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 1
- Văn phạm phi ngữ cảnh Đị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 T = Ø) • P : tập hữu hạn các luật sinh dạng A ( (VT)*) • 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..) • , , , .. 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: S AB A aA S AB Aa hay A aAa B bB B bBb 2 Bb
- Dẫn xuất và ngôn ngữ Dẫn xuất: • 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 A ta sẽ thu được chuỗi : A 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 Ngôn ngữ sinh bởi CFG: cho CFG G(V, T, P, S) L(G) = { ww T* và S *G w } (chuỗi w gồm toàn ký hiệu kết thúc và được dẫn ra từ S) 3
- 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 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 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 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ó 4
- 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: S aASa A SbASSba Một dẫn xuất của G: S aAS aSbAS aabAS aabbaS aabbaa S 1 a A S 2 3 4 S A a 5 b 6 7 8 a a 9 b 10 11 Định lý 5.1: nếu G(V, T, P, S) là một CFG thì S * nếu và chỉ nếu 5 có cây dẫn xuất trong văn phạm sinh ra .
- 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 AB A aAa B bBb • Các dẫn xuất khác nhau cho từ aaabb: (a) S AB aAB aaAB aaaB aaabB aaabb (b) S AB AbB Abb aAbb aaAbb aaabb (c) S AB aAB aAbB aAbb aaAbb aaabb (d) S AB aAB aaAB aaAbB aaabB 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 6
- 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 E + E E * E (E) a Với chuỗi a + a * a, ta có thể vẽ đến 2 cây dẫn xuất khác nhau E E E * E E + E E + E a a E * E 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 nhau: (a + a) * a hoặc a + (a * a) 7
- 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) EE+TE*TT T (E) 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 EE+TT TT*FF F (E) a 8
- Giản lược văn phạm phi ngữ cảnh Trong CFG có thể chứa các yếu tố thừa: ● 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) 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 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 ε . 9
- Các ký hiệu vô ích 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 S * X * w với , là các chuỗi bất kỳ và w T*. có 2 đặc điểm cho ký hiệu có ích • 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 10
- 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 V' tồn tại w T* để A * w Giải thuật tìm V': Begin (1) OldV' := ; (2) NewV' := { A A w với w T* }; (3) While OldV' NewV' do begin (4) OldV' := NewV'; (5) NewV' := OldV' {A A với (T OldV')* } end; (6) V' := NewV'; 11 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) 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 (V' T') tồn tại , (V' T')* để S * X Cách tìm: • Đặt V' = {S} • Nếu A V' và A 1 2n là các luật sinh trong P thì ➢ Thêm các biến của , , vào V' 1 2 n • Lặp lại cho đến khi không còn biến nào được thêm vào nữa 12
- 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: • Áp dụng bổ đề 2: V' = {S, A, B, D} V' = {S, A, B} S→A S→A A → aBb | ε A → aBb | ε B → A | cB B → A | cB 13 D → ab
- Luật sinh ε Định lý 5.3: (loại bỏ luật sinh 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 ε. Cách tìm: ➢ Bước 1: xác định tập biến rỗng Nullable i. A ε A Nullable ii.B X1X2...Xn, Xi Nullable B Nullable ➢ Bước 2: xây dựng tập luật sinh P' Với mỗi luật sinh A X1X2...Xn trong P, ta xây dựng luật sinh A 12n với điều kiện: i. Nếu Xi Nullable thì i = Xi ii. Nếu Xi Nullable thì i = Xi ε iii. Không phải tất cả i đều bằng ε 14
- Luật sinh ε Ví dụ: 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ε Chú ý: 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'. 15
- Luật sinh đơn vị Định lý 5.4: (loại bỏ luật sinh 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ị. 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. Để 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 V) do Begin Tính ΔA = { B B V và A * B } ; For (mỗi biến B ΔA) do For (mỗi luật sinh B thuộc P) do If (B không là luật sinh đơn vị) then Thêm luật sinh A vào P' 16 End ;
- Luật sinh đơn vị Ví dụ: loại bỏ luật sinh đơn vị trong văn phạm EE+TT TT*FF 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 17
- 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 BC hoặc A a, với A, B, C là biến và a là 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) ➢ 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 A X1X2...Xi...Xn A X1X2...Ca...Xn Ca a a ➢ 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 B1 D1 D1 B2 D2 A B1B2...Bm (m>2) ... Dm-2 Bm-1 Bm 18
- 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 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 Ca và b bằng Cb trong các luật sinh có độ dài vế phải > 1: S CaA a CbB b ABA A CaA a CbB b B CbB b Ca a Cb b 19
- Dạng chuẩn Chomsky (CNF) Bước 3: thay thế các luật sinh có độ dài vế phải > 2: S CaA a CbB b AD1 A CaA a CbB b B CbB b Ca a Cb b D1 BA 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Toán kỹ thuật: Hàm phức và ứng dụng - Hàm giải tích
21 p | 396 | 44
-
Bài giảng Toán giải tích 1: Chương 1 - Dương Minh Đức
61 p | 191 | 23
-
Bài giảng Toán 1E1 và Toán 1: Chương giới thiệu - ThS. Huỳnh Văn Kha
8 p | 178 | 13
-
Bài giảng Toán giải tích 1: Chương 3 - Dương Minh Đức
30 p | 97 | 10
-
Bài giảng Toán giải tích 1: Chương 6 - Dương Minh Đức
64 p | 116 | 10
-
Bài giảng Toán giải tích 1: Chương 7 - Dương Minh Đức
88 p | 107 | 10
-
Bài giảng Toán giải tích 1: Chương 8 - Dương Minh Đức
57 p | 91 | 10
-
Bài giảng Toán giải tích 1: Chương 4 - Dương Minh Đức
29 p | 99 | 9
-
Bài giảng Toán giải tích 1: Chương 5 - Dương Minh Đức
90 p | 94 | 9
-
Bài giảng Toán giải tích 1: Chương 2 - Dương Minh Đức
49 p | 97 | 9
-
Bài giảng Toán giải tích - Chương 7: Máy Turing
12 p | 191 | 8
-
Bài giảng Toán giải tích - Chương 3: Automata hữu hạn và biểu thức chính quy
34 p | 130 | 6
-
Bài giảng Toán cao cấp - Chương 0: Giải tích tổ hợp
18 p | 198 | 6
-
Bài giảng Toán giải tích - Chương 2: Ngôn ngữ và sự phân cấp Chomsky
18 p | 76 | 3
-
Bài giảng Toán giải tích - Chương 4: Văn phạm chính quy và các tính chất
9 p | 97 | 2
-
Bài giảng Toán giải tích - Chương 6: Automata đẩy xuống
16 p | 62 | 2
-
Bài giảng Toán giải tích - Chương 1: Bổ túc toán
20 p | 76 | 2
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn