TAILIEUCHUNG - Ngôn ngữ hình thức và Ôtômat - Chương 2

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 .

• Kỹ thuật lập trình
• ôtômat hữu hạn
• văn phạm chính qui
• ôtômat đẩy xuống
• máy turing
• ngôn ngữ lập trình
• Ngôn ngữ hình thức
• Chomsky
• Tin học lý thuyết
• Bổ túc toán
• Ôtômat tuyến tính
• Văn phạm phi ngữ cảnh
• Xác định độ trễ giải mã
• Độ trễ giải mã
• Ngôn ngữ chính quy
• ôtômat hữu hạn A
• Giải thuật mở rộng ôtômat
• Ôtômat lưỡng cực
• Bài giảng Lý thuyết tính toán
• Lý thuyết tính toán
• Thiết kế ôtômat hữu hạn
• Toán tử chính quy
• biểu thực chính quy
• tài liệu công nghệ
• công nghệ thông tin
• hữu hạn trạng thái
• ôtô mát hữu hạn
• Ngôn ngữ hình thức và Ôtômat
• Ngôn ngữ phi ngữ cảnh
• Ôtomat hữu hạn
• Chương trình dịch
• Lý thuyết ngôn ngữ hình thức
• Kiến thức toán học cơ sở
• Các văn phạm chính quy
• trình bày báo cáo
• báo cáo kỹ thuật
• cách trình bày báo cáo
• báo cáo ngành nông nghiệp
• báo cáo ngành tin học
• Lý thuyết ôtômát
• trình biên dịch
• ô tô mát hữu hạn
• kỹ thuật điện tử
• toán học
• Toán rời rạc
• Phương pháp quy nạp
• Đại số boole
• Cơ sở toán học
• Cơ sở thuật toán
• Lý thuyết khoa học máy tính
• Ôtômat hữu hạn không đơn định
• Toán tử chính quy với NFA
• Nondeterministic Finite State Automaton (NFA)
• Biểu thức chính quy
• Ngôn ngữ của biểu thức chính quy