tailieunhanh - 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