Bài giảng Tin học lí thuyết: Chương 5 - Võ Huỳnh Trâm

Bài giảng "Tin học lí thuyết - Chương 5: Văn phạm phi ngữ cảnh" cung cấp cho người học các kiến thức: 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. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Tin học lí thuyết: Chương 5 - Võ Huỳnh Trâm • 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 α γ ta sẽ thu ñược chuỗi αβγ : • Văn phạm phi ngữ cảnh (CFG) α γ ⇒G αβ βγ • Giả sử: α1 ⇒G α2, α2 ⇒G α3, ..., αm-1 ⇒G αm, ta có: • Giản lược văn phạm phi ngữ cảnh α1 ⇒ G αm • Chuẩn hóa văn phạm phi ngữ cảnh • Ta có: α ⇒ G α với mọi chuỗi α • Các tính chất của văn phạm phi ngữ cảnh • Thông thường, ta sẽ dùng ⇒ và ⇒ thay cho ⇒G và ⇒ G cho CFG G(V, T, P, S)  ∈ ⇒ G (chuỗi w gồm toàn ký hiệu kết thúc và ñược dẫn ra từ S) 1 3 là hệ thống gồm 4 thành phần cây dẫn xuất (hay cây phân tích cú pháp) của một văn • V : tập hữu hạn các biến (ký tự chưa kết thúc) phạm G(V, T, P, S) có ñặc ñiểm • T : tập hữu hạn các ký tự kết thúc (V ∩ T = Ø) (1) Mỗi nút có một nhãn, là một ký hiệu ∈ (V ∪ T ∪ {ε} ) • P : tập hữu hạn các luật sinh dạng A → α α∈ (V∪T (2) Nút gốc có nhãn là S (ký hiệu bắt ñầu) • S : ký hiệu bắt ñầu của văn phạm (3) Nếu nút trung gian có nhãn A thì A ∈ V (4) Nếu nút n có nhãn A và các ñỉnh n1, n2, ..., nk là con của n Q : u y ư c • V: chữ in hoa (A, B, C, ..); T: chữ in thường (a, b, c, .., w, x, y..) theo thứ tự từ trái sang phải có nhãn lần lượt là X1, X2, ..., Xk thì • α, β, γ, .. biểu diễn chuỗi ký hiệu kết thúc và biến A → X1X2...Xk là một luật sinh trong P V í d : G=({S, A, B}, {a, b}, P, S) với P gồm các luật sinh: (5) Nếu nút n có nhãn là ε thì n phải là nút lá và là nút con duy S → AB nhất của nút cha của nó A → aA S → AB A→a hay A → aAa B → bB B → bBb 2 4 B→bPrinted with FinePrint - purchase at www.fineprint.com xét văn phạm G({S, A}, {a, b}, P, S}, với P gồm: S → aASa một văn phạm phi ngữ cảnh G ñược gọi là văn phạm A → SbASSba mơ hồ (ambiguity) nếu nó có nhiều hơn một cây dẫn xuất cho Một dẫn xuất của G: cùng một chuỗi w. S ⇒ aAS ⇒ aSbAS ⇒ aabAS ⇒ aabbaS ⇒ aabbaa xét văn phạm G với luật sinh: S ...