Dạng FSM là gì? Phân biệt giữa Mealy FSM và Moore FSM.
Dạng FSM (Finite State Machine) là gì?
**FSM (Finite State Machine)**, hay còn gọi là **Máy Trạng Thái Hữu Hạn**, là một mô hình tính toán biểu diễn một hệ thống có thể ở một trong một số hữu hạn trạng thái (states) tại bất kỳ thời điểm nào. Hệ thống chuyển từ trạng thái này sang trạng thái khác để đáp ứng các đầu vào (inputs), và có thể tạo ra các đầu ra (outputs) tùy thuộc vào trạng thái hiện tại và/hoặc đầu vào.
Nói một cách đơn giản, FSM là một máy tính trừu tượng có:
* **Trạng thái (State):** Một điều kiện cụ thể mà máy có thể ở trong. Tập hợp tất cả các trạng thái là hữu hạn.
* **Chuyển tiếp (Transition):** Một sự thay đổi trạng thái xảy ra khi máy nhận được một đầu vào.
* **Đầu vào (Input):** Dữ liệu mà máy nhận được.
* **Đầu ra (Output):** Dữ liệu mà máy tạo ra.
* **Trạng thái ban đầu (Initial State):** Trạng thái mà máy bắt đầu.
FSM được sử dụng rộng rãi trong nhiều lĩnh vực, bao gồm:
* **Thiết kế mạch số:** Mô tả hành vi của các mạch tuần tự.
* **Phân tích cú pháp:** Phân tích cấu trúc của các ngôn ngữ lập trình.
* **Thiết kế giao thức:** Mô tả hành vi của các giao thức mạng.
* **Thiết kế trò chơi:** Điều khiển hành vi của các nhân vật.
* **Robot:** Điều khiển các hành động của robot.
## Phân biệt giữa Mealy FSM và Moore FSM
Mealy FSM và Moore FSM là hai loại FSM phổ biến, sự khác biệt chính giữa chúng nằm ở cách đầu ra được tạo ra:
| Tính năng | Mealy FSM | Moore FSM |
|-----------------|-------------------------------------------------------|-------------------------------------------------------|
| **Đầu ra** | Phụ thuộc vào **trạng thái hiện tại** và **đầu vào**. | Chỉ phụ thuộc vào **trạng thái hiện tại**. |
| **Độ phức tạp** | Thường phức tạp hơn Moore FSM. | Thường đơn giản hơn Mealy FSM. |
| **Số lượng trạng thái** | Có thể ít trạng thái hơn Moore FSM cho cùng một chức năng. | Có thể cần nhiều trạng thái hơn Mealy FSM cho cùng một chức năng. |
| **Thay đổi đầu ra** | Đầu ra có thể thay đổi ngay lập tức khi đầu vào thay đổi. | Đầu ra chỉ thay đổi khi trạng thái thay đổi. |
| **Ứng dụng** | Thích hợp cho các ứng dụng cần phản hồi nhanh với đầu vào. | Thích hợp cho các ứng dụng cần đầu ra ổn định và đồng bộ. |
**Giải thích chi tiết:**
* **Mealy FSM:** Đầu ra của Mealy FSM là một hàm của cả trạng thái hiện tại và đầu vào. Điều này có nghĩa là, với cùng một trạng thái, đầu ra có thể khác nhau tùy thuộc vào đầu vào hiện tại. Mealy FSM thường được biểu diễn bằng sơ đồ trạng thái, trong đó mỗi cạnh chuyển tiếp (transition) được gắn với cả đầu vào và đầu ra. Ví dụ, một máy bán hàng tự động sử dụng Mealy FSM có thể trả lại tiền thừa ngay khi nhận đủ tiền (đầu vào).
* **Moore FSM:** Đầu ra của Moore FSM chỉ là một hàm của trạng thái hiện tại. Điều này có nghĩa là, đầu ra không thay đổi khi đầu vào thay đổi, mà chỉ thay đổi khi trạng thái thay đổi. Moore FSM thường được biểu diễn bằng sơ đồ trạng thái, trong đó mỗi trạng thái được gắn với một đầu ra. Ví dụ, một đèn giao thông sử dụng Moore FSM, màu đèn (đầu ra) chỉ thay đổi khi thời gian của trạng thái hiện tại kết thúc.
**Ví dụ minh họa:**
Giả sử chúng ta muốn thiết kế một FSM phát hiện chuỗi "101".
* **Mealy FSM:** Mealy FSM sẽ có ít trạng thái hơn và sẽ đưa ra tín hiệu khi chuỗi "101" được phát hiện. Tín hiệu được phát ra ngay lập tức khi nhận được bit cuối cùng của chuỗi.
* **Moore FSM:** Moore FSM sẽ cần nhiều trạng thái hơn để theo dõi tiến trình tìm kiếm chuỗi "101". Một trạng thái sẽ đại diện cho việc đã nhận được "1", một trạng thái khác đại diện cho việc đã nhận được "10", và một trạng thái khác đại diện cho việc đã nhận được "101". Chỉ khi đạt đến trạng thái cuối cùng ("101") thì đầu ra mới được kích hoạt.
**Tóm lại:**
* **Mealy FSM:** Đầu ra phụ thuộc vào trạng thái hiện tại **và** đầu vào.
* **Moore FSM:** Đầu ra chỉ phụ thuộc vào trạng thái hiện tại.
Việc lựa chọn giữa Mealy FSM và Moore FSM phụ thuộc vào yêu cầu cụ thể của ứng dụng. Mealy FSM phù hợp cho các ứng dụng cần phản hồi nhanh, trong khi Moore FSM phù hợp cho các ứng dụng cần đầu ra ổn định và đồng bộ.
