Я использовал FSM в схемах цифровых последовательных цепей. Но я незнаком с конечными автоматами. Может ли кто-нибудь помочь мне понять «основную» разницу между ними?
16
Я использовал FSM в схемах цифровых последовательных цепей. Но я незнаком с конечными автоматами. Может ли кто-нибудь помочь мне понять «основную» разницу между ними?
Ответы:
Насколько я понимаю, оба имеют «состояния» и «действия», которые заставляют машину переходить из одного состояния в другое при входном сигнале. Таким образом, концептуальные идеи совпадают. Есть некоторая разница в деталях.
В FSM для схемотехники входной сигнал обычно считается двоичным (двоичным), тогда как в автоматах с конечным состоянием можно использовать общий «абстрактный» алфавит входных символов. Во-вторых, FSM также генерирует вывод, связанный с достигнутым состоянием, также двоичный. В терминах автоматов это «расширение» называется машиной Мура. Автоматы, однако, имеют конечные (или принимающие) состояния, которые сигнализируют о благоприятном прочтении ввода. Наконец, FSM являются в основном детерминированными, то есть для каждого входа в определенном состоянии существует одно следующее состояние. В теории автоматов также рассматривается недетерминированный вариант, когда можно выбирать, куда двигаться.
источник
Исходя из моего опыта, а также статьи в Википедии, существует несколько видов конечных автоматов , в том числе
Некоторые из понятий, летающих вокруг, отличаются в основном мотивацией; некоторые возникли из языка и / или теории вычислимости, другие из компьютерной архитектуры.
Обратите внимание, что вы также можете изменить несколько парадигм, чтобы получить автоматы, которые, возможно, все еще являются конечными автоматами, например
Как вы можете видеть, ванильные конечные автоматы, как описано в TCS 101, являются лишь одним из множества вариантов, каждый со своим (более или менее формальным) определением.
источник
Хотя основная идея, на которую они оба полагаются, одна и та же. Оба используют конечные состояния и переходят в другое состояние в качестве входного канала. Тем не менее, FSM, будучи машиной, такой как Full adder или SR flipflop, имеет биты как вход и выход. Да, FSA также имеет битовый вывод, 0 для не завершающего состояния и 1 для завершающего состояния, но это абстрактный механизм, который не виден. Есть разница в орграфах, которые нарисованы, чтобы представлять их. Кроме того, FSA является логическим и вычислительным устройством, а FSM - цифровым логическим устройством.
источник