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