В теории автоматов и последовательной логике таблица переходов состояний — это таблица, показывающая, в какое состояние (или состояния в случае недетерминированного конечного автомата ) перейдет конечный автомат на основе текущего состояния и других входов. По сути, это таблица истинности , в которой входы включают текущее состояние вместе с другими входами, а выходы включают следующее состояние вместе с другими выходами.
Таблица переходов состояний — один из многих способов задания конечного автомата . Другие способы включают диаграмму состояний .
Таблицы переходов состояний иногда являются одномерными таблицами, также называемыми таблицами характеристик . Они гораздо больше похожи на таблицы истинности, чем на их двумерную форму. Одно измерение указывает входы, текущие состояния, следующие состояния и (необязательно) выходы, связанные с переходами состояний.
Таблицы переходов состояний обычно являются двумерными таблицами. Существует два распространенных способа их организации.
В первом случае одно из измерений указывает текущие состояния, а другое указывает входы. Пересечения строк/столбцов указывают следующие состояния и (опционально) выходы, связанные с переходами состояний.
Во втором случае одно из измерений указывает текущие состояния, а другое указывает следующие состояния. Пересечения строк/столбцов указывают входы и (опционально) выходы, связанные с переходами состояний.
Одновременные переходы в нескольких конечных автоматах можно отобразить в том, что фактически является n -мерной таблицей переходов состояний, в которой пары строк отображают (наборы) текущих состояний в следующие состояния. [1] Это альтернатива представлению связи между отдельными взаимозависимыми конечными автоматами.
С другой стороны, для каждого перехода в пределах одного конечного автомата использовались отдельные таблицы: «таблицы И/ИЛИ» [2] похожи на неполные таблицы решений , в которых решение для присутствующих правил неявно представляет собой активацию соответствующего перехода.
Ниже приведен пример таблицы переходов состояний вместе с соответствующей диаграммой состояний для конечного автомата, принимающего строку с четным числом нулей:
В таблице переходов состояний все возможные входы в конечный автомат перечислены по столбцам таблицы, в то время как все возможные состояния перечислены по строкам. Если автомат находится в состоянии S 1 (первая строка) и получает вход 1 (второй столбец), автомат останется в состоянии S 1 . Теперь, если автомат находится в состоянии S 1 и получает вход 0 (первый столбец), автомат перейдет в состояние S 2 .
На диаграмме состояний первое обозначено стрелкой, идущей от S 1 к S 1 , помеченной 1, а второе обозначено стрелкой от S 1 к S 2 , помеченной 0. Этот процесс можно статистически описать с помощью цепей Маркова .
Для недетерминированного конечного автомата вход может привести к тому, что автомат окажется в более чем одном состоянии, отсюда его недетерминированность . Это обозначается в таблице переходов состояний набором всех целевых состояний, заключенных в пару фигурных скобок {}. Пример таблицы переходов состояний вместе с соответствующей диаграммой состояний для недетерминированного конечного автомата приведен ниже:
Если машина находится в состоянии S 2 и получает входной сигнал 0, машина будет находиться в двух состояниях одновременно: состояниях S 1 и S 2 .
Можно нарисовать диаграмму состояний из таблицы переходов состояний. Последовательность простых шагов приведена ниже: