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 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 1 Văn phạm phi ngữ cảnh Đ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 VoT S ký hiệu bắt đầu của văn phạm Quy ước V chữ in hoa A B C . T chữ in thường a b c . w x y. a p Ỵ . biểu diễn chuỗi ký hiệu kết thúc và biến Ví du G S A B a b P S với P gồm các luật sinh S AB A aA S AB A a hay A aA a B bB B bB b B b 2 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ỳ thì khi áp dụng luật sinh A p vào chuỗi aAy ta sẽ thu được chuỗi aPy aAy G apy Giả sử a1 G a2 a2 G a3 . am-1 G am ta có a1 _ G am 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 I w e 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
