tailieunhanh - Bài giảng Chương 3: Văn phạm phi ngữ cảnh
Đến với "Bài giảng Chương 3: Văn phạm phi ngữ cảnh" các bạn sẽ được tìm hiểu về việc suy dẫn phi ngữ cảnh; cây suy dẫn và sự nhập nhằng; giản lược văn phạm phi ngữ cảnh; dạng chuẩn Chomsky. | Chương 3 Văn phạm phi ngữ cảnh Nội dung Suy dẫn phi ngữ cảnh Cây suy dẫn và sự nhập nhằng Giản lược văn phạm phi ngữ cảnh Dạng chuẩn Chomsky Suy dẫn phi ngữ cảnh Văn phạm phi ngữ cảnh: là văn phạm trong đó các sản xuất có dạng: A với A ; ( )* Suy dẫn phi ngữ cảnh: tại mỗi bước chỉ áp dụng sản xuất phi ngữ cảnh Một số ví dụ về suy dẫn phi ngữ cảnh Ví dụ 1: Trong ngôn ngữ lập trình || A|B|C| |Z 0|1|2|3|4|5|6|7|8|9 Kí hiệu không kết thúc: , , Kí hiệu kết thúc: A, B, C, , Z, 0, 1, 2, , 9 Một số ví dụ về suy dẫn phi ngữ cảnh Ví dụ 2: Trong văn phạm tiếng Việt có các quy tắc: | bò|mèo| tôi|nó| ăn|nằm| Kí hiệu không kết thúc: , , , , , Kí hiệu kết thúc: “bò”, “mèo”, “tôi”, “nó”, “ăn”, “nằm” là các từ tiếng Việt Suy dẫn phi ngữ cảnh Định lý (định lý phân dã suy dẫn) Cho G=( , , P, S) là văn phạm phi ngữ cảnh, đặt V= . Nếu trong G có suy dẫn u1u2 un=>kG v trong đó ui, v V* thì tồn tại vi V*và ki N (i=1, 2, , n) sao cho: ui=>ki vi Với mọi i=1, 2, , n v=v1v2 vn k1+k2+ +kn=k (Chứng minh: lý thuyết ngôn ngữ và tính toán – Nguyễn Văn Ba) Cây suy dẫn và sự nhập nhằng Định nghĩa cây suy dẫn: Trong văn phạm phi ngữ cảnh G=( , ,P,S), Cây suy dẫn là cây mà mỗi đỉnh được gắn một nhãn là một phần tử thuộc tập { } và thỏa các điều kiện: i. Nhãn của gốc là kí hiệu đầu S. ii. Nhãn của mỗi đỉnh trong là kí hiệu không kết thúc. Nhãn của mỗi lá là kí hiệu kết thúc hoặc . iii. Với mỗi đỉnh trong có nhãn A và các con có nhãn là X1, X2 Xk thì A X1X2Xk là một sản xuất trong G. iv. Nếu một lá có nhãn là thì lá đó là con duy nhất của cha nó Cây suy dẫn (tiếp) Cây con là một cây tạo thành bởi một đỉnh và mọi hậu duệ của nó cùng với các nhãn và cung liên kết chúng. Gốc cây con có nhãn là A ta gọi cây con đó là . | Chương 3 Văn phạm phi ngữ cảnh Nội dung Suy dẫn phi ngữ cảnh Cây suy dẫn và sự nhập nhằng Giản lược văn phạm phi ngữ cảnh Dạng chuẩn Chomsky Suy dẫn phi ngữ cảnh Văn phạm phi ngữ cảnh: là văn phạm trong đó các sản xuất có dạng: A với A ; ( )* Suy dẫn phi ngữ cảnh: tại mỗi bước chỉ áp dụng sản xuất phi ngữ cảnh Một số ví dụ về suy dẫn phi ngữ cảnh Ví dụ 1: Trong ngôn ngữ lập trình || A|B|C| |Z 0|1|2|3|4|5|6|7|8|9 Kí hiệu không kết thúc: , , Kí hiệu kết thúc: A, B, C, , Z, 0, 1, 2, , 9 Một số ví dụ về suy dẫn phi ngữ cảnh Ví dụ 2: Trong văn phạm tiếng Việt có các quy tắc: | bò|mèo| tôi|nó| ăn|nằm| Kí hiệu không kết thúc: , , , , , Kí hiệu kết thúc: “bò”, “mèo”, “tôi”, “nó”, “ăn”, “nằm” là các từ tiếng Việt Suy dẫn phi .
đang nạp các trang xem trước
