Sự khác biệt giữa Mealy và Moore

Question

Sự khác biệt giữa các máy trạng thái Mealy và Moore có ý nghĩa thực sự nào khi nói đến việc thực hiện C không? Sự khác biệt đó thường là gì?

Một thời gian dài trước đây, tôi dễ hiểu hơn về những lợi thế/bất lợi của Mealy/Moore khi nói đến RTL. Toàn bộ đầu ra tùy thuộc vào trạng thái hiện tại/đầu ra tùy thuộc vào trạng thái hiện tại + chênh lệch đầu vào hiện tại có ý nghĩa, cũng như thực tế là Mealy có thể được tạo với 1 trạng thái ít hơn trong một số trường hợp cũng có ý nghĩa. Việc kết hợp các biểu đồ thời gian với mỗi lần thực hiện FSM cũng làm cho sự khác biệt giữa chúng rõ ràng hơn.

Giả sử tôi đang tạo một máy trạng thái trong C. Trong một trường hợp LUT phụ thuộc vào trạng thái/đầu vào hiện tại (Mealy) và trong Moore LUT chỉ tra cứu trạng thái hiện tại và trả về giá trị tiếp theo. Trong cả hai đầu ra xảy ra sau khi trở về từ LUT (tôi nghĩ, mặc dù tôi có thể sai). Tôi đã không nghĩ ra một cách rõ ràng rằng một Mealy có một lợi thế khi được mã hóa trong C. Chủ đề như khả năng đọc mã, tốc độ, mật độ mã, thiết kế dễ dàng, tất cả có thể là chủ đề liên quan - từ quan điểm của tôi hai mô hình dường như gần như giống nhau.

Có lẽ sự khác biệt này chỉ là một chủ đề cho các học giả - và trong thực tế trong việc triển khai C sự khác biệt là không đáng kể. Nếu bạn biết các cách chính, việc thực thi máy trạng thái C sẽ khác nhau giữa Mealy và Moore, và nếu có những lợi thế thực sự (điều đó cũng quan trọng), tôi sẽ tò mò muốn biết. Tôi muốn nhấn mạnh - Tôi không hỏi về triển khai RTL.

tôi đã nhìn thấy một Mealy/Moore khác bài ở đây: Mealy v/s. Moore

Nhưng điều này là không thực sự mức độ giải thích Tôi đang tìm kiếm.

Answer 1

Bạn có quy trình cơ học để chuyển đổi một hình thức thành một hình thức khác, do đó không có sự khác biệt về cấu trúc giữa hai loại.

Nói về những khác biệt trong triển khai, hai hình thức chỉ khác nhau ở hàm đầu ra , cho bạn biết biểu tượng nào sẽ được xuất. Cụ thể là:

1. Trong một máy Moore, đầu ra chỉ phụ thuộc vào trạng thái hiện tại
2. Trong một máy Mealy, sản lượng phụ thuộc vào trạng thái hiện tại và đầu vào hiện tại.

Máy Moore có thể đơn giản hơn một chút vì bạn có ít thông tin để theo dõi khi tạo đầu ra, nhưng sự khác biệt sẽ rất nhỏ.

Dưới đây là làm thế nào một máy Moore đơn giản sẽ trông giống như trong C:

int state = INITIAL; 
while (!isTerminal(state)) { 
    char input = nextInputSymbol(); 
    fprintf(output, "%c", nextOutputSymbol(state)); 
    state = nextState(state, input); 
} 

và đây là máy Mealy:

int state = INITIAL; 
while (!isTerminal(state)) { 
    char input = nextInputSymbol(); 
    fprintf(output, "%c", nextOutputSymbol(input, state)); 
    state = nextState(state, input); 
} 

như bạn thấy, sự khác biệt duy nhất là trong định nghĩa của nextOutputSymbol(). Cho dù việc thực hiện các chức năng nói là dễ dàng hơn cho một hoặc các hình thức khác, nó thực sự phụ thuộc vào ứng dụng cụ thể.

nextInputSymbol chỉ là thói quen để có biểu tượng mới (có thể là scanf hoặc tương tự) và nextState sẽ phụ thuộc vào máy cụ thể, nhưng độ phức tạp của nó sẽ không thay đổi nhiều giữa Moore và Moore tương đương.

Cụ thể, cả hai nextOutputSymbol và nextState đun sôi xuống bảng tra cứu hoặc switch hoặc chuỗi if/else, không gặp khó khăn khi triển khai thực. Họ chỉ là nhàm chán để viết, thực sự.

LƯU Ý: Tôi bỏ qua kiểm tra lỗi trong đoạn mã để giữ cho chúng tôi tập trung vào điểm chính của cuộc thảo luận. Mã thế giới thực sẽ thực hiện một số kiểm tra bổ sung, như xử lý EOF trên nextInputSymbol hoặc break nhập vào trạng thái lỗi.

Answer 2

Máy Moore: Đầu ra chỉ phụ thuộc vào trạng thái hiện tại. Máy thực sự: Đầu ra phụ thuộc vào cả trạng thái hiện tại & đầu vào hiện tại.