Таблица переходов состояний
В теории автоматов и последовательной логике таблица переходов состояний — это таблица, показывающая, в какое состояние (или состояния в случае недетерминированного конечного автомата ) перейдет конечный автомат на основе текущего состояния и других входов. По сути, это таблица истинности , в которой входы включают текущее состояние вместе с другими входами, а выходы включают следующее состояние вместе с другими выходами.
Таблица переходов состояний — один из многих способов задания конечного автомата . Другие способы включают диаграмму состояний .
Распространенные формы
Одномерный
Таблицы переходов состояний иногда являются одномерными таблицами, также называемыми таблицами характеристик . Они гораздо больше похожи на таблицы истинности, чем на их двумерную форму. Одно измерение указывает входы, текущие состояния, следующие состояния и (необязательно) выходы, связанные с переходами состояний.
Таблица состояний-переходов
(S: состояние, I: вход, O: выход)Вход Текущее состояние Следующий штат Выход Я 1 С 1 С я О х Я 2 С 1 С дж О у … … … … В С 1 С к О з Я 1 С 2 S i′ О х′ Я 2 С 2 С j′ О у′ … … … … В С 2 С к′ О з′ … … … … Я 1 С м S i″ О х″ Я 2 С м С дж″ О у″ … … … … В С м С к″ О з″
Двумерный
Таблицы переходов состояний обычно являются двумерными таблицами. Существует два распространенных способа их организации.
В первом случае одно из измерений указывает текущие состояния, а другое указывает входы. Пересечения строк/столбцов указывают следующие состояния и (опционально) выходы, связанные с переходами состояний.
Таблица состояний-переходов
(S: состояние, I: вход, O: выход)ВходТекущее состояниеЯ 1 Я 2 … В С 1 С и /О х С дж /О у … С к /О з С 2 S i′ /O x′ S j′ /O y′ … С к′ /О з′ … … … … … С м S i″ /O x″ С j″ /О z″ … С к″ /О з″
Во втором случае одно из измерений указывает текущие состояния, а другое указывает следующие состояния. Пересечения строк/столбцов указывают входы и (опционально) выходы, связанные с переходами состояний.
Таблица состояний-переходов
(S: состояние, I: вход, O: выход, —: недопустимо)Следующий штатТекущее состояниеС 1 С 2 … С м С 1 Я и /О х — … — С 2 — — … Я дж /О й … … … … … С м — И к /О з … —
Другие формы
Одновременные переходы в нескольких конечных автоматах можно отобразить в том, что фактически является n -мерной таблицей переходов состояний, в которой пары строк отображают (наборы) текущих состояний в следующие состояния. [1] Это альтернатива представлению связи между отдельными взаимозависимыми конечными автоматами.
С другой стороны, для каждого перехода в пределах одного конечного автомата использовались отдельные таблицы: «таблицы И/ИЛИ» [2] похожи на неполные таблицы решений , в которых решение для присутствующих правил неявно представляет собой активацию соответствующего перехода.
Пример
Ниже приведен пример таблицы переходов состояний вместе с соответствующей диаграммой состояний для конечного автомата, принимающего строку с четным числом нулей:
Таблица переходов состояний ВходТекущее состояние0 1 С 1 С 2 С 1 С 2 С 1 С 2
 |
В таблице переходов состояний все возможные входы в конечный автомат перечислены по столбцам таблицы, в то время как все возможные состояния перечислены по строкам. Если автомат находится в состоянии S 1 (первая строка) и получает вход 1 (второй столбец), автомат останется в состоянии S 1 . Теперь, если автомат находится в состоянии S 1 и получает вход 0 (первый столбец), автомат перейдет в состояние S 2 .
На диаграмме состояний первое обозначено стрелкой, идущей от S 1 к S 1 , помеченной 1, а второе обозначено стрелкой от S 1 к S 2 , помеченной 0. Этот процесс можно статистически описать с помощью цепей Маркова .
Для недетерминированного конечного автомата вход может привести к тому, что автомат окажется в более чем одном состоянии, отсюда его недетерминированность . Это обозначается в таблице переходов состояний набором всех целевых состояний, заключенных в пару фигурных скобок {}. Пример таблицы переходов состояний вместе с соответствующей диаграммой состояний для недетерминированного конечного автомата приведен ниже:
Таблица переходов состояний ВходТекущее состояние0 1 С 1 С 2 С 1 С 2 {С 1 , С 2 } С 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 on Software Engineering , 20 (9): 684–707 , CiteSeerX 10.1.1.72.8657 , doi :10.1109/32.317428
Дальнейшее чтение
- Майкл Сипсер: Введение в теорию вычислений . PWS Publishing Co., Бостон, 1997 ISBN 0-534-94728-X
