Переходная система
-
Определение переходной системы
- Используется в теоретической информатике для описания поведения дискретных систем
- Включает состояния и переходы с метками, которые могут быть уникальными или общими
- Может быть представлена в виде направленных графов или абстрактных систем перезаписи
-
Отличия от конечных автоматов
- Множество состояний и переходов не обязательно конечны
- Нет «начального» и «конечного» состояний
- Переходы могут быть помечены для дополнительной информации
-
Формальное определение
- Пара (S, T), где S — множество состояний, T — переходное отношение
- Переход от состояния p к состоянию q обозначается p → q
-
Маркированные переходные системы
- Включают набор меток Λ и переходное отношение T
- Метки могут представлять входные данные, условия или действия
-
Особые случаи
- Детерминированные переходы: существует только один кортеж (p, α, q) в T для каждого p и α
- Исполняемые переходы: существует хотя бы один кортеж (p, α, q) в T для каждого p и α
-
Формулировка коалгебры
- Помеченные системы перехода соответствуют взаимно однозначным функциям S → P(Λ × S)
- Коалгебра для функтора P(Λ × −)
-
Связь с системами перезаписи
- Немаркированная система перехода эквивалентна абстрактной системе перезаписи
- В системах перезаписи основное внимание уделяется преобразованию объектов, в то время как в системах перехода — интерпретации меток как действий
-
Расширения
- Системы перехода могут включать дополнительную функцию маркировки состояний
- Языки действий расширяют системы перехода, добавляя беглые выражения и значения
-
См. также
- Список связанных понятий, включая бинарные и троичные отношения, моноиды и структуры Крипке
Полный текст статьи: