TAILIEUCHUNG - Bài giảng Tin học lý thuyết - Chương 5: Văn phạm phi ngữ cảnh (Context Free Grammar)
Chương 5 trình bày những nội dung chính sau: Văn phạm phi ngữ cảnh (CFG), giản lược văn phạm phi ngữ cảnh, chuẩn hóa văn phạm phi ngữ cảnh, các tính chất của văn phạm phi ngữ cảnh. để nắm bắt các nội dung chi tiết. | Văn phạm phi ngữ cảnh (Context Free Grammar) Nội dung: Văn phạm phi ngữ cảnh (CFG) Giản lược văn phạm phi ngữ cảnh Chuẩn hóa văn phạm phi ngữ cảnh Các tính chất của văn phạm phi ngữ cảnh Chương 5: Văn phạm phi ngữ cảnh Định nghĩa: là hệ thống gồm 4 thành phần G(V, T, P, S) V : tập hữu hạn các biến (ký tự chưa kết thúc) T : tập hữu hạn các ký tự kết thúc (V T = Ø) P : tập hữu hạn các luật sinh dạng A ( (V T)*) S : ký hiệu bắt đầu của văn phạm S AB A aA A a B bB B b S AB A aA a B bB b hay Quy ước: V: chữ in hoa (A, B, C, ); T: chữ in thường (a, b, c, , w, x, y) , , , biểu diễn chuỗi ký hiệu kết thúc và biến Ví dụ: G=({S, A, B}, {a, b}, P, S) với P gồm các luật sinh: Dẫn xuất và ngôn ngữ Dẫn xuất: Nếu A là luật sinh trong văn phạm G và , là 2 chuỗi bất kỳ, thì khi áp dụng luật sinh A vào chuỗi A ta sẽ thu được chuỗi : A G Giả sử: 1 G 2, 2 G 3, ., m-1 G m, ta có: 1 *G m Ta có: *G với mọi chuỗi Thông thường, ta sẽ dùng và * thay cho G và *G Ngôn ngữ sinh bởi CFG: cho CFG G(V, T, P, S) L(G) = { w w T* và S *G w } (chuỗi w gồm toàn ký hiệu kết thúc và được dẫn ra từ S) Cây dẫn xuất Định nghĩa: cây dẫn xuất (hay cây phân tích cú pháp) của một văn phạm G(V, T, P, S) có đặc điểm Mỗi nút có một nhãn, là một ký hiệu (V T {ε} ) Nút gốc có nhãn là S (ký hiệu bắt đầu) Nếu nút trung gian có nhãn A thì A V Nếu nút n có nhãn A và các đỉnh n1, n2, ., nk là con của n theo thứ tự từ trái sang phải có nhãn lần lượt là X1, X2, ., Xk thì A là một luật sinh trong P Nếu nút n có nhãn là ε thì n phải là nút lá và là nút con duy nhất của nút cha của nó Cây dẫn xuất Ví 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 1 3 6 10 2 5 9 4 7 8 11 S A b b a S a S A a a Định lý : nếu G(V, T, P, S) là một CFG thì S * nếu và chỉ nếu có cây dẫn xuất trong văn phạm sinh ra . Dẫn xuất trái nhất - Dẫn
đang nạp các trang xem trước
