Детерминированный конечный автомат – это автомат, который при получении данных может находиться в одном состоянии. Если для представления функции переходов ДКА используется таблица, то каждая запись в ней представляет собой единственное состояние.18 Dec 2018
Различают детерминированные КА — автоматы, в которых следующее состояние однозначно определяется текущим состоянием и выход зависит только от текущего состояния и текущего входа, и недетерминированные КА, следующее состояние у которых в общем случае неопределённо и, соответственно, не определён выходной сигнал.
Таким образом, единственное отличие НКА от ДКА — существование нескольких переходов по одному символу из одного состояния.
Конечный автомат (или попросту FSM — Finite-state machine) это модель вычислений, основанная на гипотетической машине состояний. В один момент времени только одно состояние может быть активным. Следовательно, для выполнения каких-либо действий машина должна менять свое состояние.
Добавить комментарий