Таблица перехода состояний
В теории автоматов и последовательной логике таблица переходов состояний — это таблица, показывающая, в какое состояние (или состояния в случае недетерминированного конечного автомата ) конечный автомат перейдет , на основе текущего состояния и других входных данных. По сути, это таблица истинности, в которой входные данные включают текущее состояние вместе с другими входными данными, а выходные данные включают следующее состояние вместе с другими выходными данными.
Таблица перехода состояний — это один из многих способов описания конечного автомата . Другие способы включают диаграмму состояний .
Общие формы [ править ]
Одномерный [ править ]
Таблицы переходов состояний иногда представляют собой одномерные таблицы, называемые также таблицами характеристик . Они больше похожи на таблицы истинности, чем на их двумерную форму. Одно измерение указывает входы, текущие состояния, следующие состояния и (необязательно) выходные данные, связанные с переходами между состояниями.
Таблица перехода состояний
(S: состояние, I: вход, O: выход)Вход Текущее состояние Следующее состояние Выход я 1 SS1 SИ О х я 2 SS1 С Дж О да … … … … В SS1 С к О з я 1 SS2 И ' О х' я 2 SS2 С j' О да … … … … В SS2 S k' О з' … … … … я 1 см И " О х″ я 2 см С Дж ″ О да″ … … … … В см С к″ О з″
Двумерное [ править ]
Таблицы перехода состояний обычно представляют собой двумерные таблицы. Есть два распространенных способа их организации.
В первом случае одно из измерений указывает текущие состояния, а другое — входные данные. Пересечения строк и столбцов указывают следующие состояния и (необязательно) выходные данные, связанные с переходами состояний.
Таблица перехода состояний
(S: состояние, I: вход, O: выход)ВходТекущее состояниея 1 я 2 … В SS1 S i /O x С дж / О й … С к /О з SS2 S i' /O x' S j' /O y' … S k' /O z' … … … … … см S i″ /O x″ S j″ /O z″ … С к″ /О з″
Во втором случае одно из измерений указывает текущие состояния, а другое — следующие состояния. Пересечения строк и столбцов указывают входные и (необязательные) выходные данные, связанные с переходами состояний.
Таблица перехода состояний
(S: состояние, I: вход, O: выход, —: незаконно)Следующее состояниеТекущее состояниеSS1 SS2 … см SS1 Я я /О х — … — SS2 — — … Я дж /О й … … … … … см — Я к /О з … —
Другие формы [ править ]
Одновременные переходы в нескольких конечных автоматах можно показать в виде n -мерной таблицы переходов состояний, в которой пары строк отображают (наборы) текущих состояний в следующие состояния. [1] Это альтернатива представлению связи между отдельными взаимозависимыми конечными автоматами.
С другой стороны, для каждого перехода внутри одного конечного автомата использовались отдельные таблицы: «таблицы И/ИЛИ». [2] подобны неполным таблицам решений , в которых решение для присутствующих правил неявно представляет собой активацию соответствующего перехода.
Пример [ править ]
Пример таблицы переходов состояний вместе с соответствующей диаграммой состояний для конечного автомата приведен ниже:
Таблица перехода состояний ВходТекущее состояние0 1 SS1 SS2 SS1 SS2 SS1 SS2
|
В таблице переходов состояний все возможные входные данные конечного автомата перечисляются по столбцам таблицы, а все возможные состояния перечисляются по строкам. Если машина находится в состоянии S1 ( первая строка) и получает на входе 1 (второй столбец), машина останется в состоянии S1 . Теперь, если машина находится в состоянии S1 и получает на входе 0 (первый столбец), машина перейдет в состояние S2 .
На диаграмме состояний первое обозначено стрелкой, идущей от S 1 к S 1 , помеченной цифрой 1, а второе обозначено стрелкой от S 1 до S 2 , помеченной цифрой 0. Этот процесс можно описать статистически, используя Марковские цепи .
Для недетерминированного конечного автомата входные данные могут привести к тому, что машина окажется в более чем одном состоянии, отсюда и его недетерминизм . В таблице переходов состояний это обозначается набором всех целевых состояний, заключенных в пару фигурных скобок {}. Пример таблицы переходов состояний вместе с соответствующей диаграммой состояний для недетерминированного конечного автомата приведен ниже:
Таблица перехода состояний ВходТекущее состояние0 1 SS1 SS2 SS1 SS2 {С 1 , С 2 } SS2
|
Если машина находится в состоянии S2 и получает на входе 0, машина будет одновременно находиться в двух состояниях: состояниях S1 и S2 .
Преобразования из/в диаграмму состояний [ править ]
можно нарисовать диаграмму состояний Из таблицы переходов состояний . Ниже представлена последовательность простых шагов:
- Нарисуйте кружки, обозначающие данные состояния.
- Для каждого из состояний просмотрите соответствующую строку и нарисуйте стрелку к состоянию(ям) назначения. Для входного символа может быть несколько стрелок, если конечный автомат недетерминирован.
- Назначьте состояние в качестве начального состояния . Начальное состояние задается формальным определением конечного автомата.
- Назначьте одно или несколько штатов как принимающие . Это также дано в формальном определении конечного автомата.
См. также [ править ]
- Список смежности
- Матрица смежности
- Поток данных
- Стол возбуждения
- Конечный автомат
- Обозначение индекса
- Машина Мура
- Мучнистая машина
- Методика Уорда-Меллора
Ссылки [ править ]
- ^ Брин, Майкл (2005), «Опыт использования облегченного метода формальной спецификации для линейки продуктов коммерческой встраиваемой системы» (PDF) , журнал «Требования к разработке» , 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