Lý thuyết Automata là bộ môn nghiên cứu về các thiết bị tính toán trừu tượng (machines). Trước khi máy tính ra đời, vào thập niên 1930, A. Turing đã nghiên cứu một cỗ máy trừu tượng có đầy đủ khả năng tính toán như máy tính ngày nay. Mục tiêu của Turing là chỉ ra chính xác biên giới giữa những gì máy tính có thể và không thể làm. Kết luận của ông không chỉ áp dụng cho cỗ máy Turing trừu tượng mà còn cho tất cả các máy tính ngày nay.
Trong các thập niên 1940 và 1950, các cỗ máy đơn giản hơn, mà ngày này chúng ta gọi là automata hữu hạn (finite automata) được nghiên cứu bởi một số nhà khoa học. Những automata này, ban đầu được đề xuất để mô hình hóa các chức năng của bộ não, trở nên rất hữu ích cho nhiều mục đích khác. Vào cuối thập niên 1950, nhà ngôn ngữ học N. Chomsky bắt đầu nghiên cứu các văn phạm (grammars) chính quy. Mặc dù không phải là các cỗ máy, những văn phạm này có quan hệ gần gũi với các automata trừu tượng. Ngày nay, các văn phạm đóng vai trò nền tảng trong một số bộ phần của phần mềm máy tính, bao gồm trình biên dịch.
Vào năm 1969, S. Cook mở rộng lý thuyết của Turing về vấn đề có thể và không thể tính toán được. Cook đã chia ra những bài toán có thể giải quyết hiệu quả bằng máy tính và những bài toán có thể giải được trên lý thuyết, nhưng trên thực tế cần nhiều thời gian đến nỗi máy tính cũng trở nên không hữu dụng, trừ cho một số trường hợp nhỏ. Lớp các bài toán này được gọi là khó xử lý (intractable) hay “NP-hard”. Ngay cả nếu trong tương lai, tốc độ của máy tính tăng theo hàm mũ (định luật Moore), cũng không mở rộng được đáng kể khả năng giải quyết các bài toán này.

(Trích Introduction to Automata Theory, Languages and Computation – 2nd edition)