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.
Nội dung trích xuất từ tài liệu:
Bài giảng Chương 3: Văn phạm phi ngữ cảnh Chương 3Vă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ý III.1 (đị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 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à A-cây Biên (kết quả) của một cây suy dẫn hay của một A-cây là xâu tạo thành bằng cách ghép tiếp các lá của cây theo trật tự từ trái qua phải ta được một câu gọi là kết quả. Ví dụ về cây suy dẫnVí dụ: xét văn phạm G({S, A}, {a, b}, P, S}, với P gồm: S  aAS | a A  SbA | SS | ba 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 b 10 11 9 Cây suy dẫn (tiếp) Định lý III.2: Cho G là văn phạm phi ngữ cảnh có một xâu w được sản sinh bởi G (S=>*Gw ) khi và chỉ khi có một cây suy dẫn của văn phạm đó mà biên của nó là w.Chứng minh:(1) Giả sử có cây suy dẫn biên là w thì có suy dẫn S=>*w.(2) Giả sử có suy dẫn S=>*w thì có cây suy dẫn biên là w. Suy dẫn trái và suy dẫn phải Suy dẫn trái: là suy dẫn mà trong đó, ở mỗi bước, kí hiệu được thay thế luôn luôn là kí hiệu không kết thúc nằm bên trái nhất trong dạng câu. Suy dẫn phải:là suy dẫn mà trong đó, ở mỗi bước, kí hiệu được thay thế luôn luôn là kí hiệu không kết thúc nằm bên phải nhất trong dạng câu. Suy dẫn trái và suy dẫn phải (tiếp)Ví dụ: Cho văn phạm G với các sản xuất: S AB A  aA|a B  bB|bCác dẫn xuất khác nhau cho từ aaabb: 1. S =>AB => aAB => aaAB => aaaB => aaabB => aaabb 2. S => AB => AbB => Abb => aAbb => aaAbb => aaabb 3. S => AB => aAB => aAbB => aAbb => aaAbb => aaabb 4. S => AB => aAB => aaAB => aaAbB => aaabB => aaabb Dẫn xuất (1) là dẫn xuất trái nhất, (2) 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 Văn phạm nhập nhằng Khái niệm: một văn phạm phi ngữ cảnh G được gọi là văn phạm nhập nhằng (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ăn phạm nhập nhằng (tiếp) Một ngôn ngữ có thể được sinh ra từ văn phạm nhập nhằng hoặc văn phạm không nhập nhằng Ngôn ngữ được gọi là nhập nhằng (nhập nhằng cố hữu – không nghiên cứu) nếu mọi văn phạm sinh ra nó đều nhập nhằng Văn phạm nhập nhằng (tiếp) Để giản trừ nhập nhằng: ta đưa vào một số kí hiệu kết thúc phụ và một vài sản xuất trung gian:  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) EE+T|E*T|T T  (E) | a  Quy định rằng khi không có dấ ...