Таблица переходов состояний - State-transition table
В теории автоматов и последовательной логики , таблица перехода состояний таблица , показывающая , что состояние (или состояния в случае недетерминированного конечного автомата ) а конечный автомат переместится, на основе текущего состояния и других входов. По сути, это таблица истинности, в которой входы включают текущее состояние вместе с другими входами, а выходы включают следующее состояние вместе с другими выходами.
Таблица переходов между состояниями - это один из многих способов указать конечный автомат. Другие способы включают диаграмму состояний .
Общие формы
Одномерный
Таблицы переходов между состояниями иногда представляют собой одномерные таблицы, также называемые таблицами характеристик . Они больше похожи на таблицы истинности, чем на их двумерную форму. Единственное измерение указывает входы, текущие состояния, следующие состояния и (необязательно) выходы, связанные с переходами между состояниями.
| Вход | Текущее состояние | Следующее состояние | Выход |
|---|---|---|---|
| Я 1 | S 1 | S i | О х |
| Я 2 | S 1 | S j | О у |
| … | … | … | … |
| Я н | S 1 | S k | O z |
| Я 1 | S 2 | S i ′ | O x ′ |
| Я 2 | S 2 | S j ′ | O y ′ |
| … | … | … | … |
| Я н | S 2 | S k ′ | O z ′ |
| … | … | … | … |
| Я 1 | См м | S i ″ | O x ″ |
| Я 2 | См м | S j ″ | Ой ″ |
| … | … | … | … |
| Я н | См м | S k ″ | O z ″ |
Двухмерный
Таблицы переходов между состояниями обычно представляют собой двумерные таблицы. Есть два распространенных способа их размещения.
В первом случае одно из измерений указывает текущее состояние, а другое - входные данные. Пересечения строк / столбцов указывают следующие состояния и (необязательно) выходы, связанные с переходами между состояниями.
|
Вход
Текущее состояние
|
Я 1 | Я 2 | … | Я н |
|---|---|---|---|---|
| S 1 | S ввод / вывод x | S j / O y | … | S k / O z |
| S 2 | S i ′ / O x ′ | S j ′ / O y ′ | … | S k ′ / O z ′ |
| … | … | … | … | … |
| См м | S i ″ / O x ″ | S j ″ / O z ″ | … | S k ″ / O z ″ |
Во втором случае одно из измерений указывает текущие состояния, а другое - следующие состояния. Пересечения строк / столбцов обозначают входы и (необязательно) выходы, связанные с переходами между состояниями.
|
Следующее состояние
Текущее состояние
|
S 1 | S 2 | … | См м |
|---|---|---|---|---|
| S 1 | Я я / вывода х | - | … | - |
| S 2 | - | - | … | Я J / вывода у |
| … | … | … | … | … |
| См м | - | I k / O z | … | - |
Другие формы
Одновременные переходы в нескольких конечных автоматах могут быть показаны в том, что по сути является n-мерной таблицей переходов состояний, в которой пары строк отображают (наборы) текущие состояния на следующие состояния. Это альтернатива представлению связи между отдельными, взаимозависимыми конечными автоматами.
С другой стороны, отдельные таблицы использовались для каждого из переходов в пределах одного конечного автомата: «таблицы И / ИЛИ» аналогичны таблицам неполных решений, в которых решение для присутствующих правил является неявной активацией связанный переход.
Пример
Пример таблицы переходов состояний вместе с соответствующей диаграммой состояний для конечного автомата приведен ниже:
|
Вход
Текущее состояние
|
0 | 1 |
|---|---|---|
| S 1 | S 2 | S 1 |
| S 2 | S 1 | S 2 |
|
В таблице переходов состояний все возможные входные данные для конечного автомата перечислены по столбцам таблицы, а все возможные состояния перечислены по строкам. Если автомат находится в состоянии S 1 (первая строка) и получает ввод 1 (второй столбец), автомат останется в состоянии S 1 . Теперь, если автомат находится в состоянии S 1 и получает на входе 0 (первый столбец), автомат перейдет в состояние S 2 .
На диаграмме состояний первый обозначен стрелкой, идущей от S 1 к S 1, обозначенной цифрой 1, а последний обозначен стрелкой от S 1 к S 2, обозначенной цифрой 0. Этот процесс можно описать статистически, используя Цепи Маркова .
Для недетерминированного конечного автомата вход может привести к тому, что автомат будет находиться в более чем одном состоянии, отсюда его недетерминизм . Это обозначается в таблице переходов состояний набором всех целевых состояний, заключенных в пару фигурных скобок {}. Пример таблицы переходов состояний вместе с соответствующей диаграммой состояний для недетерминированного конечного автомата приведен ниже:
|
Вход
Текущее состояние
|
0 | 1 |
|---|---|---|
| S 1 | S 2 | S 1 |
| S 2 | {S 1 , S 2 } | S 2 |
|
Если автомат находится в состоянии S 2 и получает на входе 0, автомат будет одновременно находиться в двух состояниях, состояниях S 1 и S 2 .
Преобразования из / в диаграмму состояний
Можно нарисовать диаграмму состояний из таблицы состояния перехода. Ниже приводится последовательность простых шагов:
- Нарисуйте круги, чтобы обозначить данные состояния.
- Для каждого из состояний просканируйте соответствующую строку и нарисуйте стрелку к целевому состоянию (ям). Для входного символа может быть несколько стрелок, если конечный автомат недетерминирован.
- Обозначьте состояние как начальное состояние . Начальное состояние дается в формальном определении конечного автомата.
- Обозначьте одно или несколько состояний как принимающее состояние . Это также дается в формальном определении конечного автомата.
Смотрите также
Рекомендации
дальнейшее чтение
- Майкл Сипсер: Введение в теорию вычислений . PWS Publishing Co., Бостон 1997 ISBN 0-534-94728-X