Tiếp nội dung phần 1, Bài giảng Ngôn ngữ hình thức: Phần 2 cung cấp cho người học những kiến thức như: Trình bày các kiến thức cơ bản về: Văn phạm phi ngữ cảnh (CFG); rút gọn văn phạm phi ngữ cảnh; chuẩn hoá văn phạm phi ngữ cảnh; tính chất của văn phạm phi ngữ cảnh; automat đẩy xuống (PDA); sự tương đương của PDA và CFG. | Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Chƣơng 3. VĂN PHẠM PHI NGỮ CẢNH VÀ AUTOMAT ĐẨY XUỐNG Contexet free Grammar - CFG and push down Automata - PDA Mục tiêu Giúp sinh viên có khả năng - Hiểu đƣợc khái niệm và xác định đƣợc các thành phần của một CFG. - Nhận dạng đƣợc lớp ngôn ngữ phi ngữ cảnh CFL do văn phạm CFG sinh ra và tính chất của CFL. - Xây dựng đƣợc các thành phần của CFG đặc tả một lớp CFL. - Hiểu và xây dựng đƣợc dẫn xuất và cây dẫn xuất. - Rút gọn và chuẩn hoá đƣợc CFG. - Hiểu đƣợc khái niệm và xác định đƣợc các thành phần của một PDA - Xây dựng đƣợc các thành phần của PDA đoán nhận ngôn ngữ sinh bởi CFG và xây dựng đƣợc CFG sinh ra ngôn ngữ đƣợc đoán nhận bởi PDA. Nội dung chính - Văn phạm phi ngữ cảnh định nghĩa dẫn xuất và ngôn ngữ và cây dẫn xuất. - Rút gọn văn phạm phi ngữ cảnh. - Chuẩn hoá văn phạm phi ngữ cảnh. - Tính chất của CFL. - Automat đẩy xuống định nghĩa ngôn ngữ đoán nhận bởi PDA. - Quan hệ của PDA và CFG. . Văn phạm phi ngữ cảnh CFG Context Free Grammar Xuất xứ của văn phạm phi ngữ cảnh là sự mô tả thông qua các ngôn ngữ tự nhiên. Ta có thể viết các quy tắc cú pháp để diễn tả câu An là sinh viên giỏi nhƣ sau lt câu đơn gt lt chủ ngữ gt lt vị ngữ gt lt chủ ngữ gt lt danh từ gt lt vị ngữ gt lt động từ gt lt bổ ngữ gt lt bổ ngữ gt lt danh từ gt lt tính từ gt 107 Phạm Hùng Phú Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống lt danh từ gt An lt danh từ gt sinh viên lt động từ gt là lt tính từ gt giỏi Các từ trong cặp dấu lt gt nhƣ . là các phạm trù cú pháp cho ta vai trò của các bộ phận hợp thành câu. Ta thấy một câu đƣợ sinh ra qua các bƣớc triển khai dần dần theo các quy tắc cú pháp. Đây cũng chính là dạng của các luật sinh trong văn phạm phi ngữ cảnh. Nhƣ vậy văn phạm phi ngữ cảnh cũng có thể chọn làm mô hình cho các văn phạm của các ngôn ngữ tự nhiên. Tuy nhiên trong khoa học máy tính với nhu cầu biểu diễn các ngôn ngữ lập trình văn phạm phi ngữ cảnh CFG còn đƣợc thiết kế thành một dạng tƣơng đƣơng gọi là văn phạm
