Tập bài giảng Ngôn ngữ hình thức

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.
Nội dung trích xuất từ tài liệu:
Tập bài giảng Ngôn ngữ hình thức Ngôn ngữ hình thức Mục lụcLỜI NÓI ĐẦU ............................................................................................................ 4Chương 1. TỔNG QUAN VỀ NGÔN NGỮ VÀ AUTOMAT ................................. 6 1.1. Các khái niệm cơ bản ....................................................................................... 6 1.1.1. Khái niệm ngôn ngữ hình thức.................................................................. 6 1.1.2. Bảng chữ cái (alphabet) ............................................................................ 8 1.1.3. Xâu trên bảng chữ cái ............................................................................... 8 1.1.4. Các phép toán trên xâu .............................................................................. 9 1.1.5. Ngôn ngữ (language)............................................................................... 10 1.2. Văn phạm và ngôn ngữ .................................................................................. 13 1.2.1. Văn phạm ................................................................................................ 13 1.2.2. Ngôn ngữ sinh bởi Văn phạm ................................................................. 15 1.2.3. Văn phạm tương đương .......................................................................... 16 1.3. Phân loại văn phạm và ngôn ngữ ................................................................... 16 1.3.1. Văn phạm và ngôn ngữ loại 0 ................................................................. 16 1.3.2. Văn phạm và ngôn ngữ loại 1 ................................................................. 17 1.3.3. Văn phạm và ngôn ngữ loại 2 ................................................................. 17 1.3.4. Văn phạm và ngôn ngữ loại 3 ................................................................. 17 1.3.5. Ví dụ ........................................................................................................ 18 1.4. Một số tính chất của ngôn ngữ....................................................................... 19 1.4.1. Tính chất 1............................................................................................... 19 1.4.2 Tính chất 2................................................................................................ 20 1.4.3. Tính chất 3............................................................................................... 20 1.4.4. Tính chất 4............................................................................................... 21 1.4.5. Tính chất 5 (Tính đệ quy của ngôn ngữ) ................................................. 21 1.5. Automat ......................................................................................................... 23 1.5.1. Mô tả automat ......................................................................................... 23 1.5.2. Phân loại automat .................................................................................... 24CÂU HỎI VÀ BÀI TẬP CHƢƠNG 1 ..................................................................... 25Phạm Hùng Phú 1Ngôn ngữ hình thứcChương 2. VĂN PHẠM CHÍNH QUY VÀ AUTOMAT HỮU HẠN .................... 30 2.1. Automat hữu hạn (FINITE AUTOMAT - FA) ................................................ 31 2.1.1. Định nghĩa Automat hữu hạn .................................................................. 31 2.1.2. Automat hữu hạn đơn định ...................................................................... 36 2.1.3. Automat hữu hạn không đơn định-NFA (Nondeterministic Finite Automata) .......................................................................................................... 42 2.1.4. Sự tương đương giữa DFA và NFA ........................................................ 49 2.1.5. NFA với ε-dịch chuyển (NFAε) .............................................................. 56 2.1.6. Sự tương đương giữa NFA có và không có ε-dịch chuyển ..................... 62 2.2. Biểu thức chính quy (RE: Regular Expressions) ........................................... 64 2.2.1. Định nghĩa ............................................................................................... 65 2.2.2. Một số tính chất đại số của biểu thức chính quy ..................................... 66 2.2.3. Sự tương đương giữa automat hữu hạn và biểu thức chính quy ............. 67 2.3. Văn phạm chính quy ...................................... ...