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 .
