Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Đơn giản hóa VPPNC và các dạng chuẩn
Nội dung xem thử
Mô tả chi tiết
Trang 189
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Chương 6 Đơn giản hóa VPPNC
và các dạng chuẩn
6.1 Các phương pháp để biến đổi văn phạm
6.2 Hai dạng chuẩn quan trọng
6.3 Giải thuật thành viên cho văn phạm phi ngữ cảnh
Trang 190
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Các phương pháp để biến đổi văn phạm
Chuỗi trống đóng một vai trò khá đặc biệt trong nhiều định lý
và chứng minh, và thường cần có một sự chú ý đặc biệt cho nó.
Nếu L ∋ λ thì biểu diễn L = L1 ∪ λ với L1 = L - λ. Nếu
G1 = (V1, T, S1, P1)
là văn phạm biểu diễn cho L1 thì
G = (V1 ∪ {S}, T, S, P1 ∪ {S → S1 | λ})
là văn phạm biểu diễn cho L.
Trong chương này, chúng ta chỉ xem xét các NNPNC không
chứa λ.
Tuy nhiên những kết luận cho ngôn ngữ không chứa λ vẫn có
thể áp dụng cho ngôn ngữ có chứa λ.
Trang 191
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Một vài qui tắc thay thế hiệu quả
Đị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 nó
A → x1y1x2 | x1y2x2| ... | x1ynx2
Thì
L(G) = L(G1)