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 ảnh là một hình ảnh trực quan của một máy tự động nhận ra các chuỗi chứa số 0 chẵn. Máy tự động bắt đầu ở trạng thái S1 và chuyển sang trạng thái không chấp nhận S2 khi đọc ký hiệu 0. Đọc 0 khác làm cho máy tự động chuyển trở lại trạng thái chấp nhận S1. Ở cả hai trạng thái, ký hiệu 1 bị bỏ qua bằng cách chuyển sang trạng thái hiện tại.

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.