TAILIEUCHUNG - Tài liệu: Chương 5. Văn phạm phi ngữ cảnh

VĂN PHẠM PHI NGỮ CẢNH Nội dung chính : Trong chương này, ta sẽ nghiên cứu một loại văn phạm khá quan trọng, gọi là văn phạm phi ngữ cảnh (CFG) và lớp ngôn ngữ mà chúng mô tả - ngôn ngữ phi ngữ cảnh (CFL). CFL, cũng như tập hợp chính quy, có nhiều ứng dụng thực tế rất quan trọng, đặc biệt trong việc biểu diễn ngôn ngữ lập trình. Chẳng hạn, CFG dùng hữu ích để mô tả các biểu thức số học trong các dấu ngoặc lồng nhau hay những cấu trúc khối trong ngôn. | Chương V Văn phạm phi ngữ cảnh Chương V VĂN PHẠM PHI NGỮ CẢNH Nội dung chính Trong chương này ta sẽ nghiên cứu một loại văn phạm khá quan trọng gọi là văn phạm phi ngữ cảnh CFG và lớp ngôn ngữ mà chúng mô tả - ngôn ngữ phi ngữ cảnh CFL . CFL cũng như tập hợp chính quy có nhiều ứng dụng thực tế rất quan trọng đặc biệt trong việc biểu diễn ngôn ngữ lập trình. Chẳng hạn CFG dùng hữu ích để mô tả các biểu thức số học trong các dấu ngoặc lồng nhau hay những cấu trúc khối trong ngôn ngữ lập trình cấu trúc khối begin-end . Sau khi định nghĩa văn phạm phi ngữ cảnh một số cách biến đổi văn phạm phi ngữ cảnh nhằm giản lược nó và đưa nó về một trong những dạng chuẩn sẽ được trình bày. Cuối chương bổ đề bơm cho ngôn ngữ CFL và một số tính chất nhằm xác định tập ngôn ngữ này cũng sẽ được giới thiệu. Mục tiêu cần đạt Cuối chương sinh viên cần phải nắm vững Khái niệm CFG xác định các thành phần của một CFG. Nhận dạng được lớp ngôn ngữ mà một văn phạm CFG đặc tả. Xây dựng các luật sinh cho một CFG đặc tả một lớp ngôn ngữ. Các bước giản lược văn phạm CFG không chứa các giá trị vô ích. Chuẩn hóa CFG về các dạng chuẩn Chomsky hoặc Greibach. Ứng dụng bổ đề bơm cho CFL để chứng tỏ một ngôn ngữ không là ngôn ngữ phi ngữ cảnh. Xác định một ngôn ngữ có thuộc lớp ngôn ngữ phi ngữ cảnh hay không theo các tính chất của CFL. Kiểm tra tính rỗng hữu hạn hoặc vô hạn của một CFL. Kiến thức cơ bản Để tiếp thu tốt nội dung của chương này trước hết sinh viên cần hiểu rõ cấu trúc cú pháp của một số ngôn ngữ lập trình cấp cao như Pascal C nắm vững lý thuyết đồ thị và cây phương pháp chứng minh phản chứng và sự phân cấp các lớp văn phạm theo Noam Chomsky . Tài liệu tham khảo 1 John E. Hopcroft Jeffrey - Introduction to Automata Theory Languages and Computation - Addison - Wesley Publishing Company Inc -1979 Chapter 4 Context Free Grammars . 2 . Rayward-Smith - A First course in Formal Language Theory Second Editor - McGraw-Hill Book Company Europe - 1995 Chapter 5 Context-Free Languages 62

• Giáo dục học
• giáo trình tin học
• công nghệ thông tin
• Tin học lý thuyết
• kỹ thuật chuyên ngành
• ngôn ngữ máy tính
• tin học trong hoạt động thông tin thư viên
• bài giảng tin học trong hoạt động thông tin thư viên
• tài liệu tin học trong hoạt động thông tin thư viên
• giáo trình tin học trong hoạt động thông tin thư viên
• đề cương tin học trong hoạt động thông tin thư viên
• Giáo trình Tra cứu thông tin
• Thư viện Thông tin
• Hệ thống tìm tin
• Hệ thống tìm tin truyền thống
• Tìm tin tự động hóa
• Tìm tin trên mạng Internet
• Chiến lược tra cứu thông tin
• tin học cơ sở
• giáo trình tin học cơ sở
• bài giảng tin học cơ sở
• tin học căn bản
• kiến thức tin học
• Giáo án Tin học 8
• Tin học 8
• Giáo án điện tử Tin học 8
• Giáo án Tin
• Giáo án Tin 8
• Chương trình Tin học 8
• Giáo án Tin Học 10
• tài liệu giảng dạy Tin Học 10
• giáo trình Tin Học 10
• tài liệu Tin Học 10
• cẩm nang giảng dạy Tin Học 10
• Trình bày văn bản
• Kỹ năng soạn thảo
• Soạn thỏa văn bản
• Giáo trình Microsoft Word
• Tự học tin học
• Tài liệu tin học
• Lý thuyết tin học
• Tin học đại cương
• Giáo trình Tin học đại cương
• Đề thi trắc nghiệm tin học đại cương
• Bài giảng Tin học đại cương
• Tài liệu Tin học đại cương
• Bài tập Tin học đại cương
• Giáo án Tin học 10 bài 8
• Giáo án điện tử Tin học 10
• Giáo án lớp 10 Tin học
• Giáo án điện tử lớp 10
• Quy trình quản lý tin học
• Giải các bài toán khoa học kĩ thuật
• Những ứng dụng của tin học
• Giáo án Tin Học 11
• tài liệu giảng dạy Tin Học 11
• giáo trình Tin Học 11
• tài liệu Tin Học 11
• cẩm nang giảng dạy Tin Học 11
• tài liệu giảng dạy Tin Học 8
• giáo trình Tin Học 8
• tài liệu Tin Học 8
• cẩm nang giảng dạy Tin Học 8