Система переходов имеет две составляющие – множество конфигураций (состояний) и бинарное отношение .
Определение 1. Термины и условные обозначения системы переходов .
1) обозначает бинарное отношение на множестве , которое является рефлексивно-транзитивным замыканием отношения . Другими словами, отношение имеет место только в том случае, если
имеет место для некоторой последовательности , где , а ситуация интерпретируется как .
2) обозначает, что не существует такого состояния , для которого имеет место .
3) система переходов называется детерминированной, если для любых имеет место
(иногда используют термин «моногенная»).
4) часто и множества выделяются подмножества и , содержащие элементы, которые называются начальными и конечными состояниями соответственно. Тогда пара представляет выполнение системы переходов. При этом если тогда . Состояния, удовлетворяющие условию , называются отказами.