Máy trạng thái hữu hạn (Finite State Machine- FSM) là một mô hình tính toán trừu tượng biểu diễn một hệ thống có một số lượng hữu hạn các trạng thái. Hệ thống chuyển đổi giữa các trạng thái dựa trên các sự kiện hoặc đầu vào và mỗi trạng thái thực hiện một số hành động và tác vụ cụ thể.
FSM thường được sử dụng trong thiết kế mạch số để điều khiển và phối hợp hoạt động của hệ thống và điều khiển luồng dữ liệu. FSM được sử dụng trong các thiết kế mạch tuần tự như bộ đếm, thanh ghi dịch, điều khiển bộ nhớ đến sử dụng cho mạch điều khiển như mạch điều khiển thang máy, điều khiển đèn giao thông, máy bán hàng tự động, điều khiển các giao thức truyền thông,…
FSM thường được biểu diễn bằng sơ đồ trạng thái (state diagram) bao gồm một số hữu hạn các trạng thái (state). Tại một thời điểm, hệ thống chỉ ở một trạng thái, gọi là trạng thái hiện tại (current state). Hệ thống có thể thay đổi từ trạng thái hiện tại sang trạng thái tiếp theo (next state) khi có một sự kiện hay sự thay đổi đầu vào gọi là sự chuyển trạng thái (transition). Tại mỗi trạng thái hoặc khi chuyển đổi trạng thái, hệ thống sẽ thực hiện một công việc hay hành động nào đó.
Có 2 loại máy trạng thái là Moore và Mealy. Đầu ra của máy Moore chỉ phụ thuộc vào trạng thái hiện tại còn đầu ra của máy Mealy phụ thuộc vào cả trạng thái hiện tại và đầu vào hiện tại.
Một số điểm khác biệt chính giữa máy Moore và Mealy:
- Mealy: đầu ra phụ thuộc vào cả trạng thái hiện tại và đầu vào hiện tại nên đầu ra có thể thay đổi ngay khi đầu vào thay đổi, ngay cả khi máy chưa chuyển trạng thái. Do đó máy mealy thường có độ trễ đầu ra nhỏ hơn, có thể phản ứng nhanh hơn khi đầu vào thay đổi. Trong sơ đồ trạng thái, máy Mealy thường cần ít trạng thái hơn và đầu ra được đặt trên đường chuyển trạng thái.
- Moore: đầu ra chỉ phụ thuộc vào trạng thái hiện tại nên máy Moore thường có độ trễ lớn hơn vì đầu ra phải chờ đến khi trạng thái thay đổi và được xác định mới thay đổi. Trong sơ đồ trạng thái, máy Moore thường cần nhiều trạng thái hơn để thực hiện cùng chức năng và đầu ra được đặt trong tại trạng thái.
