Система переходов

Система переходов имеет две составляющие – множество конфигураций (состояний) и бинарное отношение .

Определение 1. Термины и условные обозначения системы переходов .

1) обозначает бинарное отношение на множестве , которое является рефлексивно-транзитивным замыканием отношения . Другими словами, отношение имеет место только в том случае, если

имеет место для некоторой последовательности , где , а ситуация интерпретируется как .

2) обозначает, что не существует такого состояния , для которого имеет место .

3) система переходов называется детерминированной, если для любых имеет место

(иногда используют термин «моногенная»).

4) часто и множества выделяются подмножества и , содержащие элементы, которые называются начальными и конечными состояниями соответственно. Тогда пара представляет выполнение системы переходов. При этом если тогда . Состояния, удовлетворяющие условию , называются отказами.