3.12. Свойства минимальной формы

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

Теорема 3.6. Если М является минимальной формой автомата то: (а) является единственной минимальной формой с точностью до ; (в) никакие два состояния в М не являются эквивалентными (г) не существует автомата, эквивалентного и меньшего, чем

Доказательство, (а) По лемме является единственным для любого и, следовательно, является единственным. Так как при определенном P построение из является единственным, не учитывая обозначения, то является единственным с точностью до изоморфизма. (б) Рассмотрим какую-нибудь входную последовательность приложенную к . Пусть соответствующая последовательность состояний будет и соответствующая выходная последовательность будет . Теперь пусть та же входная последовательность приложена к . По условию (3.15), на основании которого строится соответствующая последовательность состояний должна быть и соответствующая выходная последовательность должна

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

Из доказательства части (б) следует, что эквивалентно состояниям М, принадлежащим классу эквивалентности эквивалентно состояниям М, принадлежащим классу эквивалентности Так как ни одно состояние - из класса не эквивалентно никакому состоянию из класса то состояния и о автомата М должны быть различимыми, (г) Предположим, что имеется автомат М, эквивалентный М и меньший М. Так как то это значит, что и что каждое состояние М является эквивалентным некоторому состоянию М. Так как М больше, чем то имеются, по крайней мере, два состояния М, которые эквивалентны одному и тому же состоянию М и, следовательно, эквивалентны друг другу. Однако, согласно части (в) теоремы, это невозможно, что доказывает от противного тот факт, что не существует автомата, эквивалентного М, и меньшего, чем М.

Автомат, который является своей минимальной формой и потому не имеет эквивалентного себе меньшего автомата, называется минимальным автоматом. Автомат, имеющий n состояний и n классов эквивалентности, в котором, следовательно, все пары состояний различимы, является минимальным автоматом. Из теоремы 3.6 следует, что если задан какой-либо автомат М, то мы можем найти минимальный автомат М, эквивалентный М и являющийся единственным с точностью до изоморфизма. Этот вывод является исключительно важным, поскольку он говорит нам, что каждый автомат имеет некоторое «каноническое» представление, независящее от способа задания исходного автомата. Действительно в общем случае существует ряд способов,

которыми автомат может быть описан (особенно если это сделано устно), и оказывается, что все это многообразие описаний может быть, в конце концов, сведено к некоторому стандартному представлению. Более того, из сделанного вывода следует, что стандартное представление является наиболее компактным в смысле числа используемых состояний. Если вследствие недостатка опыта или изобретательности у исследователя начальное представление получается сильно избыточным, то имеется прямой способ уменьшить избыточность до предела и получить минимальное представление.

Рис. 3.10. Автомат

Чтобы проиллюстрировать сказанное, рассмотрим следующую игру: монета подбрасывается многократно; очко засчитывается при подбрасывании, если при подбрасывании выпадают соответственно: цифра, герб, герб или герб, герб, герб; в других случаях очко не засчитывается. Обозначив «герб» буквой а -буквой «Ц», «очко» - «1», а «отсутствие очка» — «О», мы можем выбрать следующие входной алфавит, выходной алфавит и множество состояний:

где указанные четыре состояния отождествляются со всеми возможными исходами при подбрасывании. Граф переходов автомата соответствующего этому описанию игры, показан на рис. 3.10. Однако более компактное представление получается, если заметить, что счет очков при подбрасывании не зависит на самом деле от исхода (хотя это может быть замаскировано устным описанием игры). Тогда мы можем выбрать следующие входной и выходной алфавиты и множество

состояний:

где указанные два состояния отождествляются со всеми возможными исходами при подбрасывании. В результате получим граф переходов для автомата изображенный на рис. 3.11.

Рис. 3.11. Автомат

Методом, описанным в § 3.10, легко проверить, что Таким образом, если мы не сумели обнаружить избыточности в устном описании, мы все равно можем получить (с точностью до изоморфизма) применением к любой стандартной методики минимизации автоматов.

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