Недавно я использовал XState, чтобы упростить мои сложные компоненты React. Диаграммы состояний приятно использовать для интерфейсных приложений. Я начал думать о том, чем механическая природа конечного автомата напоминает мне переключатели, и чем транзисторы похожи на переключатели, и как логические вентили строятся из этих переключателей - можно ли моделировать логические вентили с помощью конечных автоматов? Потратив некоторое время на рисование диаграмм конечных автоматов и пошаговое выполнение переходов, я обнаружил, что их действительно можно смоделировать.
Переключатель
Возможно, самый простой тип конечного автомата - это переключатель. Переключатель имеет два состояния - «включен» или «выключен». Когда вы щелкаете выключателем, вы вызываете переход между двумя состояниями. Если светильник горит, а затем вы щелкаете выключателем, свет переходит в состояние «выключено» и наоборот. Переключение переключателя называется «событием», которое вызывает переход.
Мы могли бы думать о транзисторе как о переключателе аналогичного типа. Вместо события «переворота» мы могли бы рассматривать событие напряжения в форме «высокого» и «низкого». Событие «высокий» представляет уровень напряжения выше порога затвора, а «низкий» - как напряжение ниже порога затвора. Если транзистор находится в состоянии «выключено», а затем происходит событие «высокого» напряжения, то транзистор переходит в состояние «включено». Если произойдет еще одно «высокое» событие, то состояние «включено» снова перейдет в само себя. Применяется полярная логика.
НЕ ворота
Затвор НЕ аналогичен модели транзистора выше, за исключением того, что состояния меняются местами. Если напряжение «высокое» (которое я теперь назову «1»), то затвор будет в состоянии «выключено». Если напряжение «низкое» (с этого момента «0»), то затвор включен.
И ворота
Следующие логические элементы имеют два входа и один выход. Входы будут последовательностью событий («0» или «1»), а выход - состоянием ворот («включен» или «выключен» - или в цифровом выражении «1» или «0»). Входные события являются последовательными - они влияют на конечный автомат по одному событию за раз. В отличие от реальных логических вентилей, которые получают входы параллельно, мы должны подавать входы последовательно. Из-за этого конечный автомат должен иметь два дополнительных промежуточных состояния, которые я назову просто «x» и «y».
Самый простой входной ряд - «1,1». Если мы начинаем с состояния «выключено», затем получаем событие «1» и переходим в состояние «x». Если состояние «x» получает событие «1», мы переходим в состояние «включено», которое является конечным состоянием серии. Если мы снова запустим серию «1,1», то состояние «включено» снова перейдет в состояние «x» из события «1». Затем, как и раньше, когда «x» получит событие «1», мы вернемся в состояние «включено».
Другой интересный входной ряд - «0,0». Состояние «выключено» перейдет в состояние «y» при событии «0». Независимо от того, какое событие произойдет дальше, «y» всегда будет переключаться обратно на «off». Таким образом, другой «0» неизбежно перейдет в «выключено». Если состояние «включено» получает «0», мы переходим к «y», что неизбежно завершается в состоянии «выключено».
Поскольку события и переходы биномиальны, мы могли бы смоделировать ряд как биномиальное дерево. Обратите внимание, что единственная серия, которая заканчивается «on», - «1,1».
ИЛИ Ворота
NAND ворота
XOR ворота
Анализ машин
Из состояния «выключено» событие «1» всегда переходит в состояние «x», а событие «0» всегда переходит в состояние «y». Это ветвление просто помещает второе событие в серии в контекст первого события. То же самое верно и в обратном направлении - из состояния «включено» событие «1» всегда будет переходить в состояние «x», а событие «0» всегда будет переходить в состояние «y». Опять же, это должно поместить второе событие в контекст первого события. Учитывая, что эта симметричная топология инвариантна - каковы варианты переходов между ними?
Шлюзы NAND и XOR имеют зеркальную топологию. Логически они противоположны друг другу. В то время как NAND включен для идентичных входов, XOR включен для разных входов.
Разница между AND и NAND минимальна. Событие «0» переносится от перехода «И» («y» ›‘ off ’) к переходу NAND (« y ’› ‘on’). Это потому, что есть только 1 из 4 условий, где AND находится в состоянии «on» - «1,1». Таким образом, есть только один переход, который завершается состоянием «включено». У NAND есть два условия: «включено», что требует второго события «0» после первого события «0».
Аналогичная история верна для OR и XOR. Разница между AND / NAND и OR / XOR заключается в том, что перенос является обратной цифрой, а направление переноса отражается как по горизонтали, так и по вертикали на диаграмме. Радует симметрия в логике :)
Спасибо
Я хотел бы написать больше статей о государственных машинах. Я мог бы развить эту идею и построить электрические логические схемы, такие как полусумматор, триггеры и т. Д.
Я действительно рекомендую попробовать XState. Я использовал его для всех вышеперечисленных симуляций.
Всем привет :)
