Конечный автомат определяет правоинвариантное конечное отношение эквивалентности на множестве входных последовательностей. Входные последовательности, для которых ... - Большая Энциклопедия Нефти и Газа
Выдержка из книги
Арбиб М.N.
Алгебраическая теория автоматов,языков и полугрупп
Конечный автомат определяет правоинвариантное конечное отношение эквивалентности на множестве входных последовательностей. Входные последовательности, для которых соответствующие состояния одинаковы, будем считать эквивалентными. И наоборот, для заданного правоинвариантного конечного отношения эквивалентности на множестве входных последовательностей мы можем построить автомат с минимальным множеством состояний, который определяет отношение эквивалентности на множестве входных последовательностей, совпадающее с первоначальным. Каждому классу эквивалентности соответствует вполне определенное состояние автомата. Следует как-то выделить начальное состояние, для этого дополним множество входных последовательностей пустой последовательностью. Класс эквивалентности, содержащий элемент Л, соответствует начальному состоянию. Может так случиться, что этот класс содержит только пустую последовательность. Функция переходов определяется с помощью соотношения 8 ( Ы, аг) [ xat ], где Ы обозначает состояние, соответствующее классу эквивалентности, содержащему входную последовательность к. Приведем примеры отождествления различных входных последовательностей, когда состояния, не принадлежащие минимальному множеству, не учитываются.