TAILIEUCHUNG - Bài giảng Lí thuyết ngôn ngữ hình thức và ôtômát: Chương 2 - Nguyễn Thị Minh Huyền

Bài giảng "Lí thuyết ngôn ngữ hình thức và ôtômát: Chương 2 - Ngôn ngữ chính quy và ôtômát hữu hạn" cung cấp cho người học các kiến thức: Ôtômát hữu hạn, tính đóng của lớp ngôn ngữ chính quy, biểu thức chính quy, điều kiện cần của ngôn ngữ chính quy, . Mời các bạn cùng tham khảo. | Lí thuyết ngôn ngữ hình thức và ôtômát Chương 2. Ngôn ngữ chính quy và ôtômát hữu hạn Nguyễn Thị Minh Huyền Khoa Toán - Cơ - Tin học Trường Đại học Khoa học Tự nhiên Hà Nội Ngôn ngữ chính quy Văn phạm chính quy Ôtômat hữu hạn Nguồn đồ thị chuyển Ch2. NN chính quy amp ôtômát hữu hạn 1 37 Ôtômát hữu hạn Nội dung 1. Ôtômát hữu hạn Ôtômát hữu hạn đơn định và ngôn ngữ chính quy Ôtômát hữu hạn không đơn định Đơn định hoá ôtômát Bài tập 2. Tính đóng của lớp ngôn ngữ chính quy 3. Biểu thức chính quy 4. Điều kiện cần của ngôn ngữ chính quy 5. Điều kiện cần và đủ của ngôn ngữ chính quy Ch2. NN chính quy amp ôtômát hữu hạn 2 37 Ôtômát hữu hạn Ôtômát hữu hạn đơn định và ngôn ngữ chính quy Ví dụ Dàn máy phát thanh P nút Power 2 chế độ ON OFF S nút chọn nguồn phát chuyển đổi giữa 3 chế độ CD Tape Radio. Chỉ thay đổi được trạng thái của S khi máy bật P ON . Khi tắt máy P OFF S không thay đổi giá trị Ban đầu máy tắt và ở chế độ CD. Bài toán Cho 1 dãy thao tác bấm nút P hoặc S. Dãy thao tác này có cho phép đưa máy về trạng thái bật và ở chế độ Radio không Ch2. NN chính quy amp ôtômát hữu hạn 3 37 Ôtômát hữu hạn Ôtômát hữu hạn đơn định và ngôn ngữ chính quy Định nghĩa hình thức Ôtômat hữu hạn đơn định Bộ năm A S Σ s0 δ F S tập hữu hạn các trạng thái S 6 Σ 6 bảng chữ cái vào s0 S trạng thái khởi đầu F S tập trạng thái kết δ S Σ S hàm chuyển trạng thái δ p a q máy đang ở trạng thái p nếu đọc được chữ cái vào a thì chuyển sang trạng thái q biểu diễn dạng bảng Ch2. NN chính quy amp ôtômát hữu hạn 4 37 Ôtômát hữu hạn Ôtômát hữu hạn đơn định và ngôn ngữ chính quy Biểu diễn ôtômat Biểu diễn bằng đồ thị chuyển nguồn Đỉnh vào đỉnh ra kết cung 1 1 0 s1 s2 0 Ch2. NN chính quy amp ôtômát hữu hạn 5 37 Ôtômát hữu hạn Ôtômát hữu hạn đơn định và ngôn ngữ chính quy Ngôn ngữ đoán nhận bởi ôtômat hữu hạn đơn định Hàm chuyển mở rộng δˆ S Σ S ˆ p δ p ˆ ay δ δ p p S a Σ y Σ δ p ˆ a y Ngôn ngữ đoán nhận bởi ôtômat A ˆ 0 x F L A x Σ δ s Ch2. NN chính quy amp ôtômát hữu hạn 6 37 Ôtômát hữu hạn Ôtômát hữu .

• Toán học
• Lí thuyết ngôn ngữ hình thức
• Lí thuyết ngôn ngữ hình thức và ôtômát
• Lí thuyết ngôn ngữ
• Ngôn ngữ chính quy
• Ôtômát hữu hạn
• Lớp ngôn ngữ chính quy
• Bài giảng Lí thuyết Ngôn ngữ hình thức
• 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
• kiến thức vật lý căn bản
• vật lí hạt nhân
• công suất điện
• cơ ứng dụng
• lý thuyết ôtômát
• kỹ thuật điện tử
• lý thuyết tính toán
• Phân tích diễn ngôn đa thức
• Nghĩa kinh nghiệm
• Quan hệ hình ảnh – văn bản
• Lý thuyết Ngôn ngữ học
• Ngôn ngữ học chức năng hệ thống
• công nghệ điện tử
• vi mạch điện tử
• mạch điện ứng dụng
• đề cương vi xử lí
• tài liệu học đại học
• tài liệu ôn thi vật lý
• Âm tiết và loại hình ngôn ngữ
• Tư cách ngôn ngữ học
• Lí thuyết âm tiết
• Âm vận học cổ điển Trung Hoa
• Âm tiết cảm thức
• Âm tiết ngữ âm học
• Phân tích âm vị học
• Hiện tượng đa thanh
• Lập luận nghịch hướng
• Lí thuyết đa thanh
• Hình thức đa thanh
• Quan hệ nghịch hướng
• Ngôn ngữ học