tailieunhanh - Lý thuyết văn phạm, ngôn ngữ và ôtômát - Chương 2

Tài liệu tham khảo bài giảng Lý thuyết văn phạm, ngôn ngữ và ôtômát gồm 4 chương - Chương 2 Biến đổi văn phạm phi ngữ cảnh thành những văn phạm đặc biệt | 2 - thiệu cẲu i-ity Như ta đã biết trong văn phạm không phải ký hiệu hay phép thế nào cũng đóng vai trò sinh ra ngôn ngữ. Do vậy phần đầu của chương này sẽ đề cập đến vấn đề giản lược văn phạm phi ngữ cảnh tức là loại bỏ các ký hiệu phép thế không cần thiết nhưng vẫn giữ nguyên ngôn ngữ mà nó sinh ra. Cụ thể ta có 3 loại giản lược sau Giản lược các ký hiệu thừa Giản lược quy tắc rỗng Giản lược quy tắc đơn Phần hai của chương này sẽ trình bày thuật toán đưa văn phạm phi ngữ cảnh về những văn phạm đặc biệt sau Dạng chuẩn Chomsky Văn phạm không đệ quy trái - Dạng chuẩn Greiback Phần cuối chương trình bày điều kiện cần và đủ của ngôn ngữ phi ngữ cảnh và thuật toán tìm cây suy dẫn ra xâu sinh bởi văn phạm. Bài giảng Lý thuyết Văn phạm Ngôn ngữ và Ôtomat. Nguyễn Quốc Thắng-Nguyễn Lâm Tùng - ĐẠI HỌC THẢNG LONG - Ngày 15 tháng 1 năm 2006 - 201 Kẩ lùậu cá íclv ca lú hiộu tẲưa Định nghĩa. Cho văn phạm phi ngữ cảnh G E V cr p - X G E u V được gọi là kí hiệu có ích nếu tồn tại suy dẫn ơ I- aXf3 I- Cú trong đó CƯ 3 G E u V Cú G E . - Neu X không phải là ký hiệu có ích thì X được gọi là kí hiệu thừa. Định nghĩa. - Kí hiệu X e E u V được gọi là kí hiệu vô sinh nếu không tồn tại dẫn xuất X H jj E . - Kí hiệu X G E u V được gọi là kí hiệu không đến được nếu không tồn tại dẫn xuất ơ - cưX 3 CƯ 3 G Su y . Nhận xét. Neu X là kí hiệu vô sinh hoặc kí hiệu không đến được thì X là kí hiệu thừa. Điều ngược lại có đúng không Bài giảng Lý thuyết Văn phạm Ngôn ngữ và Ôtomat. Nguyễn Quốc Thắng-Nguyễn Lâm Tùng - ĐẠI HỌC THẢNG LONG - Ngày 15 tháng 1 năm 2006 - 201 aại kí kìệiỉ u-â sừiẦ Định lý 1. Cho văn phạm phi ngữ cảnh G E V cr p với L ơ 0. Ta có thể xây dựng văn phạm phi ngữ cảnh ƠI E1 Vi CT1 P1 tưong đưong với G sao cho VA e V1 không phải là kí hiệu vô sinh. Chứng minh. Văn phạm ƠI E1 Vi CT1 P1 được xây dựng từ G bằng cách loại bỏ các kí hiệu vô sinh như sau - Xây dựng Vi Nếu trong p có quy tắc A Jj mà Jj E thì đưa A vào Vi. 4 Nếu trong p có quy tắc A X X2 . xn mà Xi E hoặc Vi thì