Войти
В теории автоматов и последовательная логика, таблица переходов между состояниями - это таблица, показывающая, в каком состоянии (или состояниях в случае недетерминированного конечного автомата ) конечный автомат переместится в, в зависимости от текущего состояния и других входных данных. По сути, это таблица истинности , в которой входы включают текущее состояние вместе с другими входами, а выходы включают следующее состояние вместе с другими выходами.
Таблица переходов состояний - один из многих способов указать конечный автомат. Другие способы включают диаграмму состояний.
Таблицы переходов между состояниями иногда бывают одномерными таблицы, также называемые таблицами характеристик. Они больше похожи на таблицы истинности, чем на их двумерную форму. Единственное измерение указывает входы, текущие состояния, следующие состояния и (необязательно) выходы, связанные с переходами между состояниями.
| Вход | Текущее состояние | Следующее состояние | Выход |
|---|---|---|---|
| I1 | S1 | Si | Ox |
| I2 | S1 | Sj | Oy |
| … | … | … | … |
| In | S1 | Sk | Oz |
| I1 | S2 | Si′ | Ox′ |
| I2 | S2 | Sj′ | Oy′ |
| … | … | … | … |
| In | S2 | Sk′ | Oz′ |
| … | … | … | … |
| I1 | Sm | Si″ | Ox″ |
| I2 | Sm | Sj″ | Oy″ |
| … | … | … | … |
| In | Sm | Sk″ | Oz″ |
Таблицы переходов между состояниями обычно представляют собой двумерные таблицы. Есть два распространенных способа их размещения.
В первом случае одно из измерений указывает текущее состояние, а другое - входные данные. Пересечения строк / столбцов указывают следующие состояния и (необязательно) выходы, связанные с переходами состояний.
| Вход Текущее состояние | I1 | I2 | … | In |
|---|---|---|---|---|
| S1 | Si/Ox | Sj/Oy | … | Sk/Oz |
| S2 | Si′/Ox′ | Sj′/Oy′ | … | Sk′/Oz′ |
| … | … | … | … | … |
| Sm | Si″/Ox″ | Sj″/Oz″ | … | Sk″/Oz″ |
Во втором случае одно из измерений указывает текущее состояние, а другое указывает следующие состояния. Пересечения строк / столбцов обозначают входы и (необязательно) выходы, связанные с переходами состояний.
| Следующее состояние Текущее состояние | S1 | S2 | … | Sm |
|---|---|---|---|---|
| S1 | Ii/Ox | — | … | — |
| S2 | — | — | … | Ij/Oy |
| … | … | … | … | … |
| Sm | — | Ik/Oz | … | — |
Одновременные переходы в нескольких конечных автоматах можно показать в том, что по сути является n-мерной таблицей переходов между состояниями, в которой пары строк отображают текущие состояния (наборы) на следующие состояния. Это альтернатива представлению связи между отдельными, взаимозависимыми конечными автоматами.
С другой стороны, отдельные таблицы использовались для каждого из переходов в пределах одного конечного автомата: «таблицы И / ИЛИ» аналогичны неполным таблицам решений, в которых решение для имеющихся правил неявно является активацией соответствующего перехода.
Пример таблицы переходов состояний вместе с соответствующей диаграммой состояний для конечного автомата приведен ниже:
| Вход Текущее состояние | 0 | 1 |
|---|---|---|
| S1 | S2 | S1 |
| S2 | S1 | S2 |
 |
В таблице переходов состояний все возможные входы конечного автомата перечислены по столбцам таблицы, а все возможные состояния перечислены по ряды. Если автомат находится в состоянии S 1 (первая строка) и получает ввод 1 (второй столбец), автомат останется в состоянии S 1. Теперь, если автомат находится в состоянии S 1 и получает ввод 0 (первый столбец), автомат переходит в состояние S 2... На диаграмме состояний первое обозначено стрелкой. цикл от S 1 к S 1, помеченный цифрой 1, а последний обозначен стрелкой от S 1 к S 2 помечен нулем. Этот процесс можно описать статистически с помощью цепей Маркова.
. Для недетерминированного конечного автомата вход может привести к тому, что автомат будет находиться в более чем одном состоянии, поэтому недетерминизм. Это обозначается в таблице переходов состояний набором всех целевых состояний, заключенных в пару фигурных скобок {}. Пример таблицы переходов состояний вместе с соответствующей диаграммой состояний для недетерминированного конечного автомата приведен ниже:
| Вход Текущее состояние | 0 | 1 |
|---|---|---|
| S1 | S2 | S1 |
| S2 | {S1, S 2} | S2 |
 |
Если автомат находится в состоянии S 2 и получает на входе 0, автомат будет одновременно находиться в двух состояниях: состояния S 1 и S 2.
Можно построить диаграмму состояний из таблицы переходов состояний. Последовательность простых шагов приведена ниже:
