Bài giảng Lý thuyết tính toán: Bài 06 - Nguyễn Ngọc Tú
lượt xem 3
download
Mời các bạn cùng tìm hiểu biến đổi văn phạm; hai dạng chuẩn quan trọng; giải thuật thành viên cho văn phạm phi ngữ cảnh được trình bày cụ thể trong "Bài giảng Lý thuyết tính toán: Bài 06 - Ngôn ngữ phi ngữ cảnh và dạng chuẩn".
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Lý thuyết tính toán: Bài 06 - Nguyễn Ngọc Tú
- LÝ THUYẾT TÍNH TOÁN INTRODUCTION TO COMPUTATION THEORY (FORMAL LANGUAGES & AUTOMATA) Bài 06. Ngôn ngữ phi ngữ cảnh và Dạng chuẩn Sử dụng slides của các tác giả: Hồ Văn Quân + Nick Hopper GV: Nguyễn Ngọc Tú TIN331 Tu.NguyenNgoc@hoasen.edu.vn
- Nội dung Biến đổi văn phạm Hai dạng chuẩn quan trọng Giải thuật thành viên cho văn phạm phi ngữ cảnh
- Biến đổi văn phạm Nếu L ∋ λ thì biểu diễn L = L1 ∪ λ với L1 = L - λ. Nếu G1 = (V1, T, S1, P1) thì G = (V1 ∪ {S}, T, S, P1 ∪ {S → S1 | λ})
- Biến đổi văn phạm – quy tắc Định lý 6.1 Cho G = (V, T, S, P) là một VPPNC. Giả sử P có chứa luật sinh A → x1Bx2 trong đó A, B là các biến khác nhau và B → y1 | y2 | ... | yn là tập tất cả các luật sinh trong P mà có B ở vế trái. Cho G1= (V, T, S, P1) là VP được xây dựng bằng cách xóa đi A → x1Bx2 từ P, và thêm vào A → x1y1x2 | x1y2x2| ... | x1ynx2 Thì L(G) = L(G1)
- E.x. Xét văn phạm G = ({A, B}, {a, b}, A, P) với các luật sinh A → a | aA | bBc, B → abA | b. Sau khi thay thế biến B ta nhận được VP tương đương như sau A → a | aA | babAc | bbc, B → abA | b Chuỗi abbc có các dẫn xuất trong G và G1 lần lượt như sau: A ⇒ aA ⇒ abBc ⇒ abbc A ⇒ aA ⇒ abbc
- Biến đổi văn phạm – quy tắc Định lý 6.2 (Loại bỏ đệ qui trái) Cho G = (V, T, S, P) là một VPPNC. Chia tập các luật sinh mà vế trái của chúng là một biến đã cho nào đó (chẳng hạn là A), thành hai tập con riêng biệt A → Ax1 | Ax2 | ... | Axn (6.2) A → y1 | y2 | ... | ym (6.3) với xi, yi ∈ (V ∪ T)*, và A không là prefix của bất kỳ yi nào. Xét G1 = (V ∪ {Z}, T, S, P1), trong đó Z ∉ V và P1 nhận được bằng cách thay mọi luật sinh của P có dạng (6.2) và (6.3) bởi A → yi | yiZ, i = 1, 2, . . . , m, Z → xi | xiZ, i = 1, 2, . . . , n, Thì L(G) = L(G1).
- Chứng minh Các dạng câu mà A sinh ra trong văn phạm G có dạng: A A(x1 + x2 + ... + xn)* ⇒ yi(x1 + x2 + ... + xn)* Cácdạng câu này cũng có thể được sinh ra trong G1 bằng cách chú ý Z có thể sinh ra các dạng câu có dạng Z (x1 + x2 + ... + xn)(x1 + x2 + ... + xn)* ⇒ mà A → yi | yiZ nên A yi(x1 + x2 + ... + xn)* ⇒ Vì vậy L(G) = L(G1).
- E.x. Sử dụng Định lý 6.2 để loại bỏ các luật sinh đệ qui-trái khỏi VP A → Aa | aBc | λ B → Bb | ba Áp dụng định lý cho biến A ta được tập luật sinh mới như sau: A → aBc | λ | aBcZ | Z B → Bb | ba Z → a | aZ Áp dụng định lý một lần nữa lần này cho biến B ta được tập luật sinh kết quả cuối cùng như sau: A → aBc | aBcZ | Z | λ B → ba | baY Z → a | aZ Y → b | bY
- Biến đổi văn phạm – Luật sinh vô dụng Định nghĩa 6.1: Cho G = (V, T, S, P) là một VPPNC. Một biến A ∈ V được gọi là khả dụng nếu và chỉ nếu có ít nhất một chuỗi w ∈ L(G) sao cho S ⇒ xAy⇒ w, với x, y ∈ (V ∪ T)*. một biến là khả dụng nếu và chỉ nếu nó xuất hiện trong ít nhất một dẫn xuất. Một biến mà không khả dụng thì gọi là vô dụng. Một luật sinh được gọi là vô dụng nếu nó có chứa bất kỳ biến vô dụng nào.
- Biến đổi văn phạm – Luật sinh vô dụng Định lý 6.3 Cho G = (V, T, S, P) là một VPPNC, ∃ một VP tương đương G0 = (V0, T, S, P0) mà không chứa bất kỳ biến vô dụng nào. Chứng minh Loại bỏ các biến và luật sinh vô dụng loại 1 Tạo văn phạm G1 = (V1, T, S, P1) với V1 là tập biến không vô dụng loại 1. Ta tìm V1 như sau: 1. Khởi tạo V1 = ∅. 2. Lặp lại bước sau cho đến khi không còn biến nào được thêm vào V1. Đối với mỗi A ∈ V mà có luật sinh A → x, x ∈ (V1∪T)*, thì thêm A vào V1. 3. Loại khỏi P các luật sinh có chứa các biến ∉ V1, ta được P1.
- Biến đổi văn phạm – Luật sinh vô dụng Để loại tiếp các biến và các luật sinh vô dụng loại 2 ta dựa vào G1 vừa có ở trên và vẽ đồ thị phụ thuộc cho nó, sau đó tìm tập các biến không đạt tới được từ S. Loại các biến này và các luật sinh liên quan đến nó ra khỏi G1 ta được văn phạm kết quả G0. Đồ thị phụ thuộc (dependency graph) Là một đồ thị có các đỉnh biểu diễn các biến, còn một cạnh nối hai đỉnh A và B khi và chỉ khi có luật sinh dạng A → xBy A B
- E.x. Loại bỏ các biến và các luật sinh vô dụng ra khỏi văn phạm G = ({S, A, B, C}, {a, b}, S, P), với tập luật sinh P là: S → aS | A | C B → aa A→ a C → aCb V1 = {S, A, B} và tập luật sinh P1 S A B S → aS | A A→a S → aS | A B → aa A→a
- Biến đổi văn phạm – Loại bỏ luật sinh Định nghĩa 6.2 Bấtkỳ luật sinh nào của VPPNC có dạng A→ λ được gọi là luật sinh-λ. Bất kỳ biến A nào mà là có thể thì được gọi là khả trống (nullable). Định lý 6.4 Cho G là một VPPNC bất kỳ mà L(G) không chứa λ, thì tồn tại một văn phạm G0 tương đương mà không có chứa luật sinh-λ.
- Biến đổi văn phạm – Loại bỏ luật sinh Chứng minh: Bước 1 Tìm tập VN tất cả các biến khả trống của G bằng các bước sau. 1. Đối với mọi luật sinh A → λ, đưa A vào VN. 2. Lặp lại bước sau cho đến khi không còn biến nào được thêm vào VN. Đối với mọi luật sinh B → A1A2 … An, mà A1, A2, An ∈ VN thì đặt B vào V N. Bước 2 Sau khi có tập VN ta xây dựng tập luật sinh như sau. Ứng với mỗi luật sinh có dạng A → x1x2 … xm, m ≥ 1, trong đó mỗi xi ∈ V ∪ T, đặt luật sinh này vào cùng với các luật sinh được sinh ra bằng cách thay thế các biến khả trống bằng λ trong mọi tổ hợp có thể, ngoại trừ nếu tất cả các xi đều khả trống thì không đặt luật sinh A → λ vào P0 của G0
- E.x. Loại bỏ các luật sinh-λ của văn phạm sau: S → ABaC C→D|λ A → BC D→d B→b|λ Vì B → λ và C → λ B và C là các biến khả trống. Vì A → BC A cũng là biến khả trống. Theo Bước 2 ta xây dựng được tập luật sinh mới tương đương như sau: S → ABaC | BaC | AaC | Aba | aC | Aa | Ba | a A → BC | B | C B→b C→D D→d
- Biến đổi văn phạm – Loại bỏ luật sinh Định nghĩa 6.3 Bất kỳ luật sinh nào của VPPNC có dạng A→B trong đó A, B ∈ V được gọi là luật sinh-đơn vị. Định lý 6.5 Cho G = (V, T, S, P) là một VPPNC bất kỳ không có luật sinh-λ, thì tồn tại một VPPNC G1 = (V1, T, S, P1) mà không có bất kỳ luật sinh đơn vị nào và tương đương với G1.
- Chứng minh 1. Đặt vào trong P1 tất cả các luật sinh không đơn vị của P. 2. Đối với mỗi biến A tìm tất cả các biến B mà A B (*) ⇒ Điều này thực hiện bằng cách vẽ đồ thị phụ thuộc cho G nhưng một cạnh nối 2 đỉnh A và B khi và chỉ khi có luật sinh-đơn vị A → B. Hai biến A và B thỏa (*) khi và chỉ khi có một con đường trong đồ thị đi từ A đến B. 3. Đối với mỗi A, B thõa (*) thêm vào trong P1 các luật sinh A → y1 | y2 | ... | yn với B → y1 | y2 | ... | yn là các luật sinh không đơn vị của B.
- E.x. Loại bỏ các luật sinh đơn vị cho VP sau S → Aa | B Đặt các luật sinh không đơn vị B → A | bb vào trong P1 A → a | bc | B S → Aa S A A → a | bc B B → bb Từ ĐTPT S → Aa | a | bc | bb S → a | bc | bb A → a | bc | bb A → bb B → bb | a | bc B → a | bc
- Biến đổi văn phạm – Loại bỏ luật sinh Định lý 6.6 Cho L là một NNPNC không chứa λ, tồn tại một VPPNC sinh ra L mà không chứa bất kỳ luật sinh vô dụng, luật sinh- λ, hay luật sinh-đơn vị nào. Chứng minh: B1. Loại bỏ luật sinh-λ B2. Loại bỏ luật sinh đơn vị B3. Loại bỏ luật sinh vô dụng loại 1, rồi vô dụng loại 2
- Hai dạng chuẩn quan trọng Một VPPNC là thuộc dạng chuẩn Chomsky nếu mọi luật sinh có dạng A → BC, hoặc A→a trong đó A, B, C ∈ V, còn a ∈ T. Định lý 6.7 Bất kỳ VPPNC G = (V, T, S, P) nào với λ ∉ L(G) đều có một văn phạm tương đương G1 = (V1, T, S, P1) có dạng chuẩn Chomsky
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Lý thuyết tính toán Otomat và ngôn ngữ hình thức - GV. Hồ Văn Quân
316 p | 226 | 56
-
Bài giảng Lý thuyết độ phức tạp: Lý thuyết NP - Đầy đủ - PGS. TSKH Vũ Đình Hòa (tt)
41 p | 219 | 51
-
Bài giảng Lý thuyết mật mã và an toàn thông tin: Mật mã cổ điển - Vũ Đình Hòa
48 p | 163 | 22
-
Bài giảng Lý thuyết tính toán: Chương 3 - PGS.TS. Phan Huy Khánh
13 p | 100 | 11
-
Bài giảng Lý thuyết tính toán: Chương 4 - PGS.TS. Phan Huy Khánh
10 p | 116 | 11
-
Bài giảng Lý thuyết tính toán: Chương 1 - PGS.TS. Phan Huy Khánh
10 p | 152 | 8
-
Bài giảng Lý thuyết đồ thị: Chương 10 - PGS.TS. Hoàng Chí Thành
25 p | 10 | 6
-
Bài giảng Lý thuyết ngôn ngữ lập trình: Chương 6 - CĐ CNTT Hữu nghị Việt Hàn
13 p | 91 | 6
-
Bài giảng Lý thuyết tính toán: Bài 03 - Nguyễn Ngọc Tú
53 p | 87 | 5
-
Bài giảng Lý thuyết tính toán: Bài 04 - Nguyễn Ngọc Tú
32 p | 90 | 5
-
Bài giảng Lý thuyết mật mã: Chương 1 - PGS.TS Đỗ Trọng Tuấn
57 p | 36 | 5
-
Bài giảng Lý thuyết tính toán: Bài 02 - Nguyễn Ngọc Tú
43 p | 79 | 4
-
Bài giảng Lý thuyết mạng máy tính: Chương 7 - ThS. Nguyễn Đức Thiện
13 p | 11 | 4
-
Bài giảng Lý thuyết tính toán: Bài 00 - Nguyễn Ngọc Tú
7 p | 81 | 3
-
Bài giảng Lý thuyết nhận dạng – Chương 4: Phân lớp dựa trên tối ưu hóa hàm lượng giá
47 p | 53 | 3
-
Bài giảng Lý thuyết tính toán: Bài 05 - Nguyễn Ngọc Tú
28 p | 90 | 3
-
Bài giảng Lý thuyết tính toán: Bài 01 - Nguyễn Ngọc Tú
29 p | 91 | 3
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