Разница между Mealy и Moore

Question

Имеет ли разница между машинами состояния Mealy и Moore какое-либо реальное значение, когда дело доходит до реализации C? Какая разница?

Давным-давно, мне было намного легче понять преимущества/недостатки Mealy/Moore, когда дело доходит до RTL. Весь вывод, зависящий от текущего состояния/выхода в зависимости от текущего состояния + текущего разности входных сигналов, имеет смысл, так же как и тот факт, что в некоторых случаях Мили может быть сделано с 1 меньшим состоянием, также имеет смысл. Сопоставление временных диаграмм с каждой реализацией FSM также сделало разницу между ними более ясными.

Скажем, я делаю машину состояний в C. В одном случае LUT зависит от входов состояния/тока (Mealy), а в Moore LUT просто просматривает текущее состояние и возвращает следующее. В любом случае выход происходит после возвращения из LUT (я думаю, хотя я мог ошибаться). Я не думал о том, что Mealy имеет преимущество при кодировании на C. Темы, такие как читаемость кода, скорость, плотность кода, легкость дизайна, могут быть релевантными темами - с моей точки зрения, две модели кажутся почти одинаковыми.

Возможно, это различие является лишь темой для ученых, и на практике в реализациях C разница незначительна. Если вы знаете ключевые способы реализации C-автомата C, которые будут отличаться от Mealy и Moore, и если есть реальные преимущества (которые также значительны), мне было бы интересно узнать. Я хотел бы подчеркнуть - я не спрашиваю о реализации RTL.

Я видел еще один пост Мили/Moore здесь: Mealy v/s. Moore

Но это на самом деле не уровень объяснения я ищу.

Answer 1

У вас есть механическая процедура преобразования одного формализма в другой, поэтому между ними нет структурной разницы.

Говоря о различиях в реализации, два формализма отличаются только функцией вывода , которая сообщает вам, какой символ должен выводиться. В частности:

1. В машине Мура, выход зависит только от текущего состояния
2. В Мили машины, выход зависит от текущего состояния и тока входного сигнала.

Машина Moore может быть немного проще реализовать, поскольку у вас меньше информации для отслеживания, когда дело доходит до генерации вывода, но разница будет очень маленькой.

Вот как простая машина Мур будет выглядеть в C:

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

и вот Мили машина:

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

, как вы видите, единственное различие заключается в определении nextOutputSymbol(). Является ли реализация указанной функции более простой для одного или другого формализма, это действительно зависит от конкретного приложения.

nextInputSymbol просто рутина, чтобы получить новый символ (может быть scanf или тому подобное) и nextState будет зависеть от конкретной машины, но ее сложность не изменится между Милей и эквивалентной Мур.

В частности, как nextOutputSymbol и nextState сводится к табличному или switch или if/else цепи, без реальной сложности реализации. На самом деле это просто скучно писать.

ПРИМЕЧАНИЕ: Я пропустил проверку ошибок в фрагментах кода, чтобы мы сосредоточились на главном обсуждении. Код реального мира выполнил бы некоторые дополнительные проверки, такие как обработка EOF по nextInputSymbol или break IN при ошибках.

Answer 2

Moore Machine: Выход зависит только от текущего состояния. Mealy Machine: Выход зависит от обоих состояний & настоящий вход.