Эквивалентные автоматы

Автоматы являются устройствами для переработки дискретной инфы. При всем этом нравом перерабатываемой инфы определяется входной и выходной алфавиты (X и Y); алфавит внутренних состояний (Q) определяется строением автомата и, вообщем говоря, он может различаться у различных автоматов с схожими входными и выходными алфавитами. Как следует, одно и то же преобразование инфы может быть осуществлено автоматами с различным числом состояний и, как следует, средством различного числа команд. Введем ряд определений:

Состояния q автомата М и q’ автомата М’ числятся эквивалентными, если оба автомата, получив одну и ту же (всякую) входную последовательность знаков, перерабатывают ее в схожую выходную последовательность.

Автоматы М и М’ именуются эквивалентными, если для каждого состояния автомата М существует эквивалентное ему состояние автомата М’ и напротив.

Другими словами, эквивалентные автоматы реализуют однообразные преобразования, но могут иметь различное число внутренних состояний.

Понятие эквивалентности состояний применимо и к одному автомату (формально можно считать, что М и М’ совпадают). Для 1-го автомата эквивалентными будут разные состояния, через которые одна и та же входная последовательность знаков преобразуется в схожую выходную.

В связи с синтезом схем практический энтузиазм представляет задачка построения автомата, выполняющего данный набор преобразований при наименьшем числе внутренних состояний.

Автомат, эквивалентный данному и имеющий меньшее из всех вероятных число состояний именуется наименьшим.

Задачка построения малого автомата именуется задачей минимизации автомата. Ее решение осуществляется в два шага: поначалу инсталлируются все неэквивалентные состояния начального автомата, а потом по ним стоится малый автомат. В свою очередь, для определения неэквивалентных состояний нужно выявить классы эквивалентных состояний.

Пусть имеется автомат с обилием внутренних состояний Q, посреди которых могут быть эквивалентные. Дела эквивалентности состояний владеют обыкновенными качествами эквивалентности, т.е. рефлексивностью, симметрией и транзитивностью. Потому огромное количество Q может быть разбито на классы эквивалентности. Функцию разглядим на примере.