Лекция: Система переходов

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

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

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

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

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

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

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

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