TAILIEUCHUNG - Bài giảng Ngôn ngữ hình thức: Phần 1 - ĐH Sư phạm kỹ thuật Nam Định

Bài giảng Ngôn ngữ hình thức: Phần 1 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. | TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT NAM ĐỊNH KHOA CÔNG NGHỆ THÔNG TIN PHẠM HÙNG PHÚ - VŨ THỊ PHƯƠNG TẬP BÀI GIẢNG NGÔN NGỮ HÌNH THỨC NAM ĐỊNH - 2012 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 . .

• Kỹ thuật lập trình
• Bài giảng Ngôn ngữ hình thức
• Ngôn ngữ hình thức
• Automat hữu hạn
• Phép toán trên ngôn ngữ
• Ngôn ngữ chính quy
• Lí thuyết Ngôn ngữ hình thức
• Bài giảng Lí thuyết Ngôn ngữ hình thức
• Lí thuyết Ngôn ngữ hình thức và ôtômat
• Ngôn ngữ phi ngữ cảnh
• Bài giảng Ngôn ngữ hình Đại cương về ngôn ngữ
• Biểu diễn ngôn ngữ
• Hệ viết lại
• Phép toán trên tập hợp
• Bài giảng Trị liệu ngôn ngữ
• Trị liệu ngôn ngữ
• Đánh giá ngôn ngữ
• Các dạng ngôn ngữ
• Các hình thức ngôn ngữ
• Trẻ bị rối loạn ngôn ngữ
• Âm vị học ngữ pháp
• Ngôn ngữ hình thức và ôtômát
• Văn phạm hình thức
• Phép toán trên từ
• Máy Turing
• Dạng chuẩn Chomsky
• Văn phạm phi ngữ cảnh
• Otomat đẩy xuống
• Chương trình dịch
• Ôtômát hữu hạn
• Văn phạm chính quy
• Bài toán bao hàm ngôn ngữ
• Lí thuyết ngôn ngữ hình thức và ôtômát
• Lí thuyết ngôn ngữ
• Lớp ngôn ngữ chính quy
• Bài giảng Ôtômát và ngôn ngữ hình thức
• Phân cấp văn phạm
• Cấu tạo Ôtômát
• Xây dựng văn phạm cho ngôn ngữ
• Phép toán trên xâu
• Ngôn ngữ lập trình Pascal
• Ôtômát đẩy xuống
• Suy dẫn phi ngữ cảnh
• Cây suy dẫn
• Ngôn ngữ lập trình
• Ôtômat đẩy xuống
• Bài toán xâu rỗng
• Thuật toán Thampson
• Ngôn ngữ đoán nhận
• Bản chất của thuật toán
• Otomat hữu hạn
• Bài giảng công nghệ thông tin
• Tập bài giảng Ngôn ngữ hình thức
• Automat hữu hạn đơn định
• Automat đẩy xuống
• Lý thuyết Automat
• Lý thuyết tính toán Otomat
• Lý thuyết ngôn ngữ hình thức
• Kỹ thuật mô phỏng
• Kỹ thuật chứng minh
• Otomat và ngôn ngữ hình thức
• Văn phạm và ngôn ngữ hình thức
• Bài giảng Đặc tả hình thức
• Đặc tả hình thức
• Mô hình Thế giới thực
• Ngôn ngữ đặc tả hình thức
• Quy trình công nghệ phần mềm
• Các tính chất của quan hệ
• Phép toán trên các tập hợp
• Các quan hệ tương đương
• Chương trình con
• Thiết kế thuật toán
• Ôtômát tuyến tính giới nội
• Máy turing tiền định
• Cấu tạo máy Turing
• Ngôn ngữ hình thức và Ôtômat
• Ôtomat hữu hạn