Tập bài giảng “Ngôn ngữ hình thức” được biên soạn theo chương trình chi tiết môn học “Ngôn ngữ hình thức” của trường Đại học Sư phạm Kỹ thuật Nam Định. Mục tiêu của tập đề cương bài giảng nhằm cung cấp các kiến thức cơ bản, tổng quan về ngôn ngữ, văn phạm và automat; giúp sinh viên nắm vững các kiến thức cơ bản về văn phạm chính quy và automat hữu hạn, văn phạm phi ngữ cảnh và automat đẩy xuống là công cụ dùng để xây dựng và phân tích từ vựng, cú pháp của các ngôn ngữ lập trình. Mời các bạn cùng tham khảo. | Ngôn ngữ hình thức Mục lục LỜI NÓI ĐẦU . 4 Chƣơng 1. TỔNG QUAN VỀ NGÔN NGỮ VÀ AUTOMAT . 6 . Các khái niệm cơ bản . 6 . Khái niệm ngôn ngữ hình thức. 6 . Bảng chữ cái alphabet . 8 . Xâu trên bảng chữ cái . 8 . Các phép toán trên xâu . 9 . Ngôn ngữ language . 10 . Văn phạm và ngôn ngữ . 13 . Văn phạm . 13 . Ngôn ngữ sinh bởi Văn phạm . 15 . Văn phạm tƣơng đƣơng . 16 . Phân loại văn phạm và ngôn ngữ . 16 . Văn phạm và ngôn ngữ loại 0 . 16 . Văn phạm và ngôn ngữ loại 1 . 17 . Văn phạm và ngôn ngữ loại 2 . 17 . Văn phạm và ngôn ngữ loại 3 . 17 . Ví dụ . 18 . Một số tính chất của ngôn ngữ. 19 . Tính chất 1. 19 Tính chất 2. 20 . Tính chất 3. 20 . Tính chất 4. 21 . Tính chất 5 Tính đệ quy của ngôn ngữ . 21 . Automat . 23 . Mô tả automat . 23 . Phân loại automat . 24 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 1 . 25 Phạm Hùng Phú 1 Ngôn ngữ hình thức Chƣơng 2. VĂN PHẠM CHÍNH QUY VÀ AUTOMAT HỮU HẠN . 30 . Automat hữu hạn FINITE AUTOMAT - FA . 31 . Định nghĩa Automat hữu hạn . 31 . Automat hữu hạn đơn định . 36 . Automat hữu hạn không đơn định-NFA Nondeterministic Finite Automata . 42 . Sự tƣơng đƣơng giữa DFA và NFA . 49 . NFA với ε-dịch chuyển NFAε . 56 . Sự tƣơng đƣơng giữa NFA có và không có ε-dịch chuyển . 62 . Biểu thức chính quy RE Regular Expressions . 64 . Định nghĩa . 65 . Một số tính chất đại số của biểu thức chính quy . 66 . Sự tƣơng đƣơng giữa automat hữu hạn và biểu thức chính quy . 67 . Văn phạm chính quy . 79 . Văn phạm tuyến tính . 79 . Sự tƣơng đƣơng giữa văn phạm chính quy và automat hữu hạn . 80 . Tính chất của ngôn ngữ chính quy . 87 . Bổ đề bơm cho ngôn ngữ chính quy. 90 . Xác định ngôn ngữ chính quy . 92 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 2 . 94 Chƣơng 3. VĂN PHẠM PHI NGỮ CẢNH VÀ AUTOMAT ĐẨY XUỐNG. 107 . Văn phạm phi ngữ cảnh CFG Context Free Grammar . 107 . Định nghĩa . 109 .
