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

Bài giảng "Tin học - 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, 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. . | 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

• Kỹ thuật lập trình
• Văn phạm phi ngữ cảnh
• Bài giảng Tin học
• 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 văn phạm phi ngữ cảnh
• Văn phạm máy tính
• Bài giảng Tin học lí thuyết
• Tin học lí thuyết
• Tính chất của văn phạm phi ngữ cảnh
• Toán giải tích
• Bài giảng Toán giải tích
• Context Free Grammar
• Tin học lý thuyết
• Bài giảng Tin học lý thuyết
• Bài giảng Chương 3
• Suy dẫn phi ngữ cảnh
• Cây suy dẫn
• Sự nhập nhằng
• Automata đẩy xuống
• Ngôn ngữ hình thức
• Văn phạm hình thức và các Automata
• Trình biên dịch
• Giáo trình điện tử
• Thiết kế cấu trúc dữ liệu
• Tập tin văn bản
• Bài giảng Ôtômát và ngôn ngữ hình thức
• Ôtômát đẩy xuống
• Ngôn ngữ phi ngữ cảnh
• Bài giảng Ngôn ngữ hình thức
• Ngôn ngữ lập trình
• Xây dựng chương trình dịch
• Bài giảng Xây dựng chương trình dịch
• Chương trình dịch
• Văn phạm LL
• Văn phạm G phi ngữ cảnh
• Lý thuyết Automat
• Giáo trình Lý thuyết Automat
• Automat đẩy xuống
• Phương tiện sát thương hàng không
• Phân tích cú pháp
• Quân chủng Phòng không – Không quân
• Tính toán ứng dụng chiến đấu
• Nghiên cứu tiếng Việt
• Cú pháp tiếng Việt
• Xác suất thống kê
• Câu tiếng Việt
• Bài giảng Lý thuyết tính toán
• Lý thuyết tính toán
• Lập trình gen
• Phát hiện xâm nhập
• Phân loại tấn công
• Văn phạm nối cây
• Lập trình gen định hướng bởi văn phạm nối cây
• Văn phạm nối cây và văn phạm phi ngữ cảnh
• Kỹ thuật văn phạm nối cây
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Xử lý ngôn ngữ tự nhiên
• Natural language processing
• Phân tích cú pháp xác suất
• Văn phạm phi ngữ cảnh xác suất
• Độc lập ngữ cảnh
• Thuật toán Beam search
• Lý thuyết văn phạm
• ôtômát hữu hạn
• otomat đẩy xuống
• Phép toán trên ngôn ngữ
• Ngôn ngữ chính quy
• Máy Turing
• Dạng chuẩn Chomsky
• Bài giảng Chương trình dịch
• Phân loại văn phạm của Chomsky
• Văn phạm nhập nhằng
• Luận án Tiến sĩ
• Luận án Tiến sĩ Khoa học máy tính
• Văn phạm liên kết cho tiếng Việt
• Lý thuyết cấu trúc diễn ngôn