TAILIEUCHUNG - 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. nội dung chi tiết. | Chu yn95 Văn phạm phi ngữ cảnh Context Free Grammar Dẩn xuất và ngôn ngữ Dần xuắt Nếu A P là luật sinh trong văn phạm G và a Y là 2 chuỗi bất kỳ Nôi dung thì khi áp dụng luật sinh A P vào chuỗi aAỵ ta sẽ thu được chuỗi aPY . . 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 aAy G aPy Giả sử a. a a a . a . a ta có í. a. 0. Ta có a G a với mọi chuỗi a 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 1 w G T và s G w 1 chuỗi w gồm toàn ký hiệu kết thúc và được dẫn ra từ S Văn phạm phi ngữ cảnh Cây dẫn xuất Đinh 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 n T 0 P tập hữu hạn các luật sinh dạng A a ae VưT S ký hiệu bắt đầu của văn phạm Quv ước Đinh 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 1 Mỗi nút có một nhãn là một ký hiệu G V u T u 2 Nút gốc có nhãn là S ký hiệu bắt đầu 3 Nếu nút trung gian có nhãn A thì A G V 4 Nếu nút n có nhãn A và các đỉnh n1 n2 . nk là con của n V chữ in hoa A B C . T chữ in thường a b c . w x y. a P 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 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 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 A aA S AB A a hay A aA a B bB B bB b 2 B b 2 nhất của nút cha của nó 4 Printed with FinePrint - purchase at Cây dẫn xuất Văn phạm mơ hồ Ví du xét văn phạm G S A a b P S với P gồm S aAS l a A SbA SSlba Một dẫn xuất của G S aAS aSbAS aabAS aabbaS aabbaa Đinh ly nếu G V T P S là một CFG thì s a nếu và chỉ nếu có cây dẫn xuất trong văn phạm sinh ra a. Khái niêm một văn phạm phi ngữ cảnh G được gọi là văn phạm mơ hồ 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í du xét văn phạm G với luật sinh _ E E E l E E l E l a

• Tin học văn phòng
• Bài giảng Tin học lí thuyết
• Tin học lí thuyết
• Văn phạm phi ngữ cảnh
• Giản lược văn phạm phi ngữ cảnh
• Chuẩn hóa văn phạm phi ngữ cảnh
• Tính chất của văn phạm phi ngữ cảnh
• Bổ túc toán
• Phép chứng minh quy nạp
• Đồ thị và cây
• Phép toán tập hợp
• Sự phân cấp Chomsky
• Biểu diễn ngôn ngữ
• Sự phân lớp văn phạm
• Automata đẩy xuống
• PDA đơn định
• PDA không đơn định
• PDA chấp nhận chuỗi
• Mô hình TM
• TM nhận dạng ngôn ngữ
• TM tính toán hàm số nguyên
• Kỹ thuật xây dựng TM