Máy Moore và Mealy
Dữ liệu tự động hữu hạn có thể có đầu ra tương ứng với mỗi lần chuyển đổi. Có hai loại máy trạng thái hữu hạn tạo ra đầu ra -
- Máy Mealy
- Máy Moore
Máy Mealy
Máy Mealy là một FSM có đầu ra phụ thuộc vào trạng thái hiện tại cũng như đầu vào hiện tại.
Nó có thể được mô tả bằng 6 bộ (Q, ∑, O, δ, X, q 0 ) trong đó -
Q là một tập hợp hữu hạn các trạng thái.
∑ là một tập hợp hữu hạn các ký hiệu được gọi là bảng chữ cái đầu vào.
O là một tập hợp hữu hạn các ký hiệu được gọi là bảng chữ cái đầu ra.
δ là hàm chuyển đổi đầu vào trong đó δ: Q × ∑ → Q
X là hàm chuyển đổi đầu ra trong đó X: Q × ∑ → O
q0là trạng thái ban đầu mà từ đó bất kỳ đầu vào nào được xử lý (q 0 ∈ Q).
Bảng trạng thái của Máy Mealy được hiển thị bên dưới:
Trạng thái hiện tại | Trạng thái tiếp theo | |||
---|---|---|---|---|
đầu vào = 0 | đầu vào = 1 | |||
Tiểu bang | Đầu ra | Tiểu bang | Đầu ra | |
→ a | b | x 1 | c | x 1 |
b | b | x 2 | d | x 3 |
c | d | x 3 | c | x 1 |
d | d | x 3 | d | x 2 |
Biểu đồ trạng thái của Máy Mealy ở trên là -
Máy Moore
Máy Moore là một FSM có đầu ra chỉ phụ thuộc vào trạng thái hiện tại.
Máy Moore có thể được mô tả bằng 6 bộ (Q, ∑, O, δ, X, q 0 ) trong đó -
Q là một tập hợp hữu hạn các trạng thái.
∑ là một tập hợp hữu hạn các ký hiệu được gọi là bảng chữ cái đầu vào.
O là một tập hợp hữu hạn các ký hiệu được gọi là bảng chữ cái đầu ra.
δ là hàm chuyển đổi đầu vào trong đó δ: Q × ∑ → Q
X là hàm chuyển đổi đầu ra trong đó X: Q → O
q0là trạng thái ban đầu mà từ đó bất kỳ đầu vào nào được xử lý (q 0 ∈ Q).
Bảng trạng thái của Máy Moore được hiển thị bên dưới:
Trạng thái hiện tại | Trạng thái tiếp theo | Đầu ra | |
---|---|---|---|
Đầu vào = 0 | Đầu vào = 1 | ||
→ a | b | c | x 2 |
b | b | d | x 1 |
c | c | d | x 2 |
d | d | d | x 3 |
Biểu đồ trạng thái của Máy Moore ở trên là -
Máy Mealy so với Máy Moore
Bảng sau đây nêu bật những điểm giúp phân biệt Máy Mealy với Máy Moore.
Máy Mealy | Máy Moore |
---|---|
Đầu ra phụ thuộc cả vào trạng thái hiện tại và đầu vào hiện tại | Sản lượng chỉ phụ thuộc vào trạng thái hiện tại. |
Nói chung, nó có ít trạng thái hơn Máy Moore. | Nói chung, nó có nhiều trạng thái hơn Mealy Machine. |
Giá trị của hàm đầu ra là một hàm của các quá trình chuyển đổi và thay đổi, khi logic đầu vào ở trạng thái hiện tại được thực hiện. | Giá trị của hàm đầu ra là một hàm của trạng thái hiện tại và những thay đổi ở các cạnh đồng hồ, bất cứ khi nào xảy ra thay đổi trạng thái. |
Máy Mealy phản ứng nhanh hơn với đầu vào. Chúng thường phản ứng trong cùng một chu kỳ đồng hồ. | Trong máy Moore, cần nhiều logic hơn để giải mã các đầu ra dẫn đến nhiều độ trễ mạch hơn. Chúng thường phản ứng sau một chu kỳ đồng hồ. |
Máy Moore đến Máy Mealy
Thuật toán 4
Input - Máy Moore
Output - Máy Mealy
Step 1 - Lấy định dạng bảng chuyển tiếp Mealy Machine trống.
Step 2 - Sao chép tất cả các trạng thái chuyển tiếp của Máy Moore sang dạng bảng này.
Step 3- Kiểm tra các trạng thái hiện tại và đầu ra tương ứng của chúng trong bảng trạng thái Máy Moore; nếu đầu ra Q i ở trạng thái là m, hãy sao chép nó vào các cột đầu ra của bảng trạng thái Máy Mealy ở bất kỳ nơi nào Q i xuất hiện ở trạng thái tiếp theo.
Thí dụ
Chúng ta hãy xem xét máy Moore sau:
Trạng thái hiện tại | Trạng thái tiếp theo | Đầu ra | |
---|---|---|---|
a = 0 | a = 1 | ||
→ a | d | b | 1 |
b | a | d | 0 |
c | c | c | 0 |
d | b | a | 1 |
Bây giờ chúng tôi áp dụng Thuật toán 4 để chuyển đổi nó thành Máy Mealy.
Step 1 & 2 -
Trạng thái hiện tại | Trạng thái tiếp theo | |||
---|---|---|---|---|
a = 0 | a = 1 | |||
Tiểu bang | Đầu ra | Tiểu bang | Đầu ra | |
→ a | d | b | ||
b | a | d | ||
c | c | c | ||
d | b | a |
Step 3 -
Trạng thái hiện tại | Trạng thái tiếp theo | |||
---|---|---|---|---|
a = 0 | a = 1 | |||
Tiểu bang | Đầu ra | Tiểu bang | Đầu ra | |
=> a | d | 1 | b | 0 |
b | a | 1 | d | 1 |
c | c | 0 | c | 0 |
d | b | 0 | a | 1 |
Máy Mealy đến Máy Moore
Thuật toán 5
Input - Máy Mealy
Output - Máy Moore
Step 1- Tính toán số lượng đầu ra khác nhau cho mỗi trạng thái (Q i ) có sẵn trong bảng trạng thái của máy Mealy.
Step 2- Nếu tất cả các đầu ra của Qi giống nhau, hãy sao chép trạng thái Q i . Nếu nó có n đầu ra riêng biệt, hãy ngắt Q i thành n trạng thái là Q trong đón = 0, 1, 2 .......
Step 3 - Nếu đầu ra của trạng thái ban đầu là 1, hãy chèn một trạng thái ban đầu mới vào đầu cho đầu ra 0.
Thí dụ
Chúng ta hãy xem xét Máy Mealy sau đây -
Trạng thái hiện tại | Trạng thái tiếp theo | |||
---|---|---|---|---|
a = 0 | a = 1 | |||
Trạng thái tiếp theo | Đầu ra | Trạng thái tiếp theo | Đầu ra | |
→ a | d | 0 | b | 1 |
b | a | 1 | d | 0 |
c | c | 1 | c | 0 |
d | b | 0 | a | 1 |
Ở đây, trạng thái 'a' và 'd' chỉ đưa ra đầu ra 1 và 0 tương ứng, vì vậy chúng tôi giữ lại trạng thái 'a' và 'd'. Nhưng trạng thái 'b' và 'c' tạo ra các đầu ra khác nhau (1 và 0). Vì vậy, chúng tôi chiab thành b0, b1 và c thành c0, c1.
Trạng thái hiện tại | Trạng thái tiếp theo | Đầu ra | |
---|---|---|---|
a = 0 | a = 1 | ||
→ a | d | b 1 | 1 |
b 0 | a | d | 0 |
b 1 | a | d | 1 |
c 0 | c 1 | C 0 | 0 |
c 1 | c 1 | C 0 | 1 |
d | b 0 | a | 0 |