В теории автоматов и последовательной логики , таблица перехода состояний таблица , показывающая , что состояние (или состояния в случае недетерминированного конечного автомата ) а конечный автомат переместится, на основе текущего состояния и других входов. По сути, это таблица истинности, в которой входы включают текущее состояние вместе с другими входами, а выходы включают следующее состояние вместе с другими выходами.
Таблица переходов состояний - это один из многих способов указать конечный автомат. Другие способы включают диаграмму состояний .
Общие формы [ править ]
Одномерный [ править ]
Таблицы переходов между состояниями иногда представляют собой одномерные таблицы, также называемые таблицами характеристик . Они больше похожи на таблицы истинности, чем на их двумерную форму. Единственное измерение указывает входы, текущие состояния, следующие состояния и (необязательно) выходы, связанные с переходами между состояниями.
| Вход | Текущее состояние | Следующее состояние | Выход |
|---|---|---|---|
| Я 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-мерной таблицей переходов состояний, в которой пары строк отображают (наборы) текущие состояния на следующие состояния. [1] Это альтернатива представлению связи между отдельными, взаимозависимыми конечными автоматами.
С другой стороны, отдельные таблицы использовались для каждого из переходов в пределах одного конечного автомата: «таблицы И / ИЛИ» [2] аналогичны неполным таблицам решений, в которых решение для существующих правил неявно активация связанного перехода.
Пример [ править ]
Пример таблицы переходов состояний вместе с соответствующей диаграммой состояний для конечного автомата приведен ниже:
Вход Текущее состояние | 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 .
Преобразования из / в диаграмму состояний [ править ]
Можно нарисовать диаграмму состояний из таблицы состояния перехода. Ниже приводится последовательность простых шагов:
- Нарисуйте круги, чтобы обозначить данные состояния.
- Для каждого состояния просканируйте соответствующую строку и нарисуйте стрелку к целевому состоянию (ям). Для входного символа может быть несколько стрелок, если конечный автомат недетерминирован.
- Обозначьте состояние как начальное состояние . Начальное состояние дается в формальном определении конечного автомата.
- Обозначьте одно или несколько состояний как принимающее состояние . Это также дается в формальном определении конечного автомата.
См. Также [ править ]
Ссылки [ править ]
- ^ Брин, Майкл (2005), «Опыт использования упрощенного метода формальной спецификации для линейки коммерческих встроенных систем» (PDF) , Requirements Engineering Journal , 10 (2): 161–172, CiteSeerX 10.1.1.60.5228 , doi : 10.1007 / s00766-004-0209-1 , S2CID 16928695
- ^ Левесон, Нэнси; Хеймдал, Матс Пер Эрик; Хилдрет, Холли; Риз, Джон Дэймон (1994), "Технические требования , установленные для управления процессами Системы" (PDF) , IEEE Transactions по разработке программного обеспечения , 20 (9): 684-707, CiteSeerX 10.1.1.72.8657 , DOI : 10,1109 / 32,317428
Дальнейшее чтение [ править ]
- Майкл Сипсер: Введение в теорию вычислений . PWS Publishing Co., Бостон 1997 ISBN 0-534-94728-X
