Переходная система

• Определение переходной системы

  • Используется в теоретической информатике для описания поведения дискретных систем 
  • Включает состояния и переходы с метками, которые могут быть уникальными или общими 
  • Может быть представлена в виде направленных графов или абстрактных систем перезаписи 

• Отличия от конечных автоматов

  • Множество состояний и переходов не обязательно конечны 
  • Нет «начального» и «конечного» состояний 
  • Переходы могут быть помечены для дополнительной информации 

• Формальное определение

  • Пара (S, T), где S — множество состояний, T — переходное отношение 
  • Переход от состояния p к состоянию q обозначается p → q 

• Маркированные переходные системы

  • Включают набор меток Λ и переходное отношение T 
  • Метки могут представлять входные данные, условия или действия 

• Особые случаи

  • Детерминированные переходы: существует только один кортеж (p, α, q) в T для каждого p и α 
  • Исполняемые переходы: существует хотя бы один кортеж (p, α, q) в T для каждого p и α 

• Формулировка коалгебры

  • Помеченные системы перехода соответствуют взаимно однозначным функциям S → P(Λ × S) 
  • Коалгебра для функтора P(Λ × −) 

• Связь с системами перезаписи

  • Немаркированная система перехода эквивалентна абстрактной системе перезаписи 
  • В системах перезаписи основное внимание уделяется преобразованию объектов, в то время как в системах перехода — интерпретации меток как действий 

• Расширения

  • Системы перехода могут включать дополнительную функцию маркировки состояний 
  • Языки действий расширяют системы перехода, добавляя беглые выражения и значения 

• См. также

  • Список связанных понятий, включая бинарные и троичные отношения, моноиды и структуры Крипке