Lý thuyết Automat
Lý thuyết Automata là nghiên cứu về máy trừu tượng và automata, cũng như các vấn đề tính toán có thể được giải quyết bằng cách sử dụng chúng. Đó là một lý thuyết trong khoa học máy tính lý thuyết và toán học rời rạc (một môn học trong cả toán học và khoa học máy tính). Từ automata (số nhiều của automaton) xuất phát từ tiếng Hy Lạp αὐτόματα, có nghĩa là "tự hành động".
Hình bên phải minh họa một máy trạng thái hữu hạn, thuộc về một loại máy tự động nổi tiếng. Máy tự động này bao gồm các trạng thái (được biểu thị trong hình bằng các vòng tròn) và chuyển tiếp (được biểu thị bằng mũi tên). Khi automaton nhìn thấy một biểu tượng của đầu vào, nó thực hiện chuyển đổi (hoặc nhảy) sang trạng thái khác, theo chức năng chuyển đổi của nó, lấy trạng thái hiện tại và biểu tượng tiếp theo làm đầu vào.
Lý thuyết tự động liên quan chặt chẽ với lý thuyết ngôn ngữ hình thức. Máy tự động là một đại diện hữu hạn của một ngôn ngữ hình thức có thể là một tập hợp vô hạn. Automata thường được phân loại theo lớp ngôn ngữ hình thức mà họ có thể nhận ra, thường được minh họa bằng hệ thống phân cấp Chomsky, mô tả mối quan hệ giữa các ngôn ngữ khác nhau và các loại logic chính thức.
Automata đóng vai trò chính trong lý thuyết tính toán, xây dựng trình biên dịch, trí tuệ nhân tạo, phân tích cú pháp và xác minh hình thức.
Tham khảo
 | Bài viết liên quan đến điện toán này vẫn còn sơ khai. Bạn có thể giúp Wikipedia mở rộng nội dung để bài được hoàn chỉnh hơn.
|
