Tham khảo sách 'ngôn ngữ hình thức và ôtômat - chương 2', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Ngôn ngữ hình thức và Ôtômat Formal Language Automata . Phan Huy Khánh khanhph@ Chương 2 Ôtômat hữu hạn Trầu thuốc. đầu câu chuyện Hình thức hình thức hoá o Đối lập tự nhiên o Mô tả quy ước chặt chẽ không thể bác BỎ o Nhu cầu GQ vấn đề tin học CNTT ICT Ngôn ngữ NN o CCụ trao đổi liên lạc o MTĐT nỏ hiểu chi về con người o Hình thức hoá ngôn ngữ o Xử lý học về NN Phát nói viết. sinh câu - VĂN PHẠM sản sinh Nhận nghe cảm thụ. - ÔTÔMAT đoán nhận 2 56 3 Chương 2 Ôtômat hữu hạn Ôtômat hữu hạn đơn định o Mô tả o Mô hình hóa o Biểu diễn ôtômat hữu hạn Ôtômat hữu hạn không đơn định o Mô tả o Khử bỏ tính không đơn định Ôtômat hữu hạn và các biểu thức chính qui o Xây dựng các ôtômat từ các biểu thức chính qui o Xây dựng các ngôn ngữ chính quy từ các ôtômat Mô tả phi hình thức ôtômat hữu hạn đơn định 3 56 Một ôtômat hữu hạn đơn định ký hiệu M viết tắt ôhhđđ DFA Deterministic Finite State Automaton gôm các phần tử o Băng vào Input Tape Chứa câu cần xử lý gôm nhiều ô Mỗi ô chứa một ký tự thuộc một bảng chữ 2 nào đó o Một đầu đọc Read Head đọc lần lượt từng ký tự trong ô o Một tập hợp hữu hạn các trạng thái gôm Một trạng thái đầu Initial State Một số trạng thái trung gian Một trạng thái cuối hay đạt được Accepting States o Một hàm chuyển tiếp Transition Function Chuyển M sang trạng thái tiếp theo từ trạng thái đang xễt và từ ký tự vừa đọc được trên băng vào 4 56 Mô hình cơ cấu các băng từ Minh hoạ ôhhđđ 5 56 Hoạt động đoán nhận của ôhh như sau e e e e e Câu vào weS được đặt ở mút trái trên băng vào Lúc đầu đầu đọc ở vị trí w 1 mút trái nhất của băng Ôhh đang ở trạng thái đầu q0 Đầu đọc đọc lần lượt từng ký tự của w trên băng di chuyển đầu đọc qua phải và thay đổi trạng thái Ôhh dừng khi mọi ký tự của w đã được đọc hết và thừa nhận câu hoặc hóc giữa chừng không thừa nhận câu vào Câu vào w e 2 Băng vào Đầu đọc di chuyển qua phải theo chiều mũi tên 6 56 1 Ví dụ một số ôtômat Mô tả hình thức ôtômat hữu hạn đơn định Máy bán báo 5xu tờ 2 xu 1 xu Chà 1 xu ------K q1 2 xu 1 .
