- BÀI 6: VĂN PHẠM PHI NGỮ CẢNH. - Văn phạm nhập nhằng. - Dạng chuẩn tắc Chomsky. - Văn phạm phi ngữ cảnh = Context-free Grammar (CFG). - CFG: Là một phương pháp mạnh hơn để mô tả ngôn ngữ. - Bộ biên dịch trong các ngôn ngữ lập trình. - Một văn phạm gồm có:. - Tập các quy tắc thay thế ≡ các sản xuất. - Mỗi quy tắc là một dòng bao gồm 1 ký hiệu và 1 xâu được ngăn cách bởi dấu mũi tên. - Biến ban đầu thường xuất hiện bên trái của quy tắc trên cùng. - Dẫn xuất. - Dẫn xuất trái nhất: Luôn lựa chọn dẫn xuất ở bên trái. - Dẫn xuất phải nhất: Luôn lựa chọn dẫn xuất ở bên phải. - Cây dẫn xuất. - R tập các quy tắc. - S biến bắt đầu. - Ngôn ngữ của văn phạm là {w|w ∈ Σ* và S. - Một ngôn ngữ phi ngữ cảnh (CFL) là ngôn ngữ được tạo ra bởi một văn phạm phi ngữ cảnh (CFG). - Ngôn ngữ B = {0 n 1 n | n ≥ 0}. - Mỗi cây dẫn xuất đều có duy nhất một cây dẫn xuất trái nhất và duy nhất một cây dẫn xuất phải nhất. - Ngôn ngữ nhập nhằng. - Có nhiều hơn 2 cây dẫn xuất ⇔ Có nhiều cách để tạo ra chuỗi đó. - Văn phạm nhập nhằng:. - Một văn phạm là nhập nhằng nếu một vài chuỗi có thể được sinh ra bởi nhiều cách. - Văn phạm không nhập nhằng:. - Ngôn ngữ chính quy và CFG. - Mọi ngôn ngữ chính quy đều là phi ngữ cảnh Chứng minh. - Ý TƯỞNG: Cho một DFA, xây dựng một văn phạm có thể tạo ra cùng 1 ngôn ngữ với DFA. - Chuyển trạng thái bắt đầu thành biến bắt đầu. - Chuyển các cạnh thành các quy tắc. - Thêm 1 quy tắc ε cho mỗi trạng thái kết thúc. - Tập hợp ngôn ngữ. - Dạng chuẩn tắc Chomsky Định nghĩa. - Một văn phạm phi ngữ cảnh ở dạng chuẩn tắc Chomsky nếu tất cả các quy tắc của nó có dạng:. - A, B, C là các biến bất kỳ, B,C không thể là biến bắt đầu Ngoài ra ta có thểm quy tắc: S → εvới S là biến bắt đầu Định lý 2. - Mọi ngôn ngữ phi ngữ cảnh nào cũng được sinh ra bởi một văn phạm phi ngữ cảnh ở dạng chuẩn tắc Chomsky. - Bước 1: Đảm bảo rằng biến bắt đầu không xuất hiện bên phía bên phải của quy tắc ⇔ Thêm một biến bắt đầu mới. - Bước 2: Loại bỏ các quy tắc có dạng A → ε. - Bước 3: Khử tất các các quy tắc đơn vị A → B. - Bước 4: Loại bỏ các quy tắc có nhiều hơn 2 biến ở phần bên phải. - Bước 5: Đảm bảo rằng chỉ còn tồn tại các quy tắc có dạng sau:. - Cho văn phạm sau:. - S → ASA | aB A → B|S B → b|ε. - Bước 1: Thêm biến bắt đầu mới S 0 → S. - Bước 2: Loại bỏ các quy tắc A → ε S 0 → S. - S → ASA | aB | a A → B|S | ε B → b S 0 → S. - S → ASA | aB | a A → B|S | ε B → b. - S → ASA | aB | a | SA | AS | S A → B|S. - Bước 3: Khử tất các các quy tắc đơn vị A → B S 0 → S. - Loại bỏ S → S S 0 → S. - S → ASA | aB | a | SA | AS A → B|S. - B → b Loại bỏ S 0 → S. - S 0 → ASA | aB | a | SA | AS S → ASA | aB | a | SA | AS A → B|S. - Loại bỏ A → B S 0 → S. - S → ASA | aB | a | SA | AS A → b|S. - B → b Loại bỏ A → S. - S 0 → ASA | aB | a | SA | AS S → ASA | aB | a | SA | AS A → b|ASA | aB | a | SA | AS B → b. - S 0 → AA 1 | aB | a | SA | AS S → AA 1 | aB | a | SA | AS A → b|AA 1 | aB | a | SA | AS A 1 → SA. - Bước 5: Thay thế A → bC bằng A → A 1 C và A 1 → b S 0 → AA 1 | aB | a | SA | AS. - S → AA 1 | aB | a | SA | AS A → b|AA 1 | aB | a | SA | AS A 1 → SA. - Thêm quy tắc A 2 → a. - S 0 → AA 1 | A 2 B | a | SA | AS S → AA 1 | A 2 B | a | SA | AS A → b|AA 1 | A 2 B | a | SA | AS A 1 → SA
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt