TAILIEUCHUNG - 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ì

• Ngôn ngữ học
• Lý thuyết văn phạm
• ngôn ngữ hình thức
• ôtômát hữu hạn
• otomat đẩy xuống
• văn phạm phi ngữ cảnh
• Tin học lý thuyết
• Bài giảng Tin học lý thuyết
• Context Free Grammar
• Giản lược văn phạm phi ngữ cảnh
• Chuẩn hóa văn phạm phi ngữ cảnh
• Luận văn Thạc sĩ
• Tóm tắt Luận văn Thạc sĩ
• Luận văn Thạc sĩ Sư phạm Lịch sử
• Sư phạm Lịch sử
• Phương pháp dạy học môn Lịch sử
• Vận dụng lý thuyết đa thông minh
• Lý thuyết đa thông minh trong dạy môn Sử 10
• Lý thuyết Structuration của A
• Giddens
• Lý thuyết Structuration
• Bối cảnh ra đời lý thuyết Structuration
• Nội dung lý thuyết Structuration
• Đánh giá lý thuyết Structuration
• Lý thuyết xã hội học
• Bài giảng Lý thuyết tính toán
• Lý thuyết tính toán
• Văn phạm nhập nhằng
• Dạng chuẩn tắc Chomsky
• Quy tắc thay thế
• Cơ sở toán học
• Cơ sở thuật toán
• Lý thuyết khoa học máy tính
• Ôtômat hữu hạn
• Bài giảng Lý thuyết thông tin
• Lý thuyết thông tin
• Xử lý tín hiệu
• Lý thuyết thông tin thống kê
• Đô lượng thông tin
• Entropy có điều kiện
• Văn phạm chính quy
• Sự tương đương giữa RG và FA
• Tập hợp chính quy
• Regular Grammar
• Ngôn ngữ chính quy
• Lý thuyết automat
• Bài giảng Lý thuyết automat
• Biểu diễn ngôn ngữ
• Automat hữu hạn
• Văn phạm chính qui
• Luận văn Thạc sĩ ngành Mĩ thuật
• Lý luận và phương pháp dạy học bộ môn Mĩ thuật
• Mĩ thuật học
• Dạy học phân môn lý thuyết âm nhạc
• Vai trò phân môn lý thuyết âm nhạc
• Biện pháp dạy học phân môn lý thuyết âm nhạc
• Luận văn thạc sĩ Âm nhạc
• Lý luận và Phương pháp dạy học Âm nhạc
• Lý thuyết Âm nhạc cơ bản
• Phương pháp thuyết trình nhóm
• Sử dụng phương pháp thuyết trình nhóm
• Lý luận dạy học Hóa học đại cương
• Dạy học Hóa học đại cương
• Phương pháp dạy học tích cực
• Sư phạm Hóa học
• Tổng quan lý thuyết tính toán
• Khái niệm ngôn ngữ
• Khái niệm văn phạm
• Các phép toán trên ngôn ngữ
• Cơ sở lý thuyết tập hợp và lôgic toán
• Cơ sở lý thuyết tập hợp
• Bài giảng Cơ sở lý thuyết tập hợp
• Cơ sở lôgic toán
• Quy tắc suy luận
• Giáo trình Lý thuyết ngôn ngữ hình thức
• Lý thuyết ngôn ngữ hình thức
• Lý thuyết ngôn ngữ
• Ngôn ngữ lập trình
• Văn phạm hình thức
• Luận văn Thạc sĩ Khoa học xã hội
• Văn học Việt Nam
• Tiểu thuyết lịch sử
• Phạm Minh Kiên
• Tiền Lê vận mạt
• Trần Hưng Đạo
• Nghiên cứu tôn giáo
• Xã hội học trong nghiên cứu tôn giáo
• Thuyết cấu trúc chức năng
• Thuyết mâu thuẫn
• Thuyết trao đổi
• Lý thuyết phân tích văn hóa
• luận văn
• lý thuyết ánh sáng
• lượng tử ánh sáng
• ứng dụng dạy học 12
• thực nghiệm sư phạm
• tâm lý sư phạm
• Nguyên lý thống kê kinh tế
• Giáo trình Nguyên lý thống kê kinh tế
• Bài giảng Nguyên lý thống kê kinh tế
• Lý thuyết Nguyên lý thống kê kinh tế
• Tài liệu Nguyên lý thống kê kinh tế
• Học Nguyên lý thống kê kinh tế