Спирина, М.С. Дискретная математика

исходный автомат, т.е. те, у которых либо меньшее число состоя­ ний, либо меньшее число входных каналов. Поэтому задача де­ композиции решается неоднозначно. Тождественными принято считать такие автоматы, которые одинаково ведут себя при различном числе состояний. Основная задача декомпозиции автоматов состоит в поиске эффективных процедур, позволяющих по заданному автомату находить компо­ зицию, моделирующую исходный. Так, с практической точки зре­ ния представляют значительный интерес замены сложной систе­ мы на более простые и экономически более выгодные системы, выполняющие те же функции, что и исходная. Композицией автоматов называют операции, используемые для создания новых автоматов из других, исходных. Автоматы, полу­ ченные в результате таких операций, также называют компози­ цией автоматов. Основная задача композиции —минимизация числа состояний автомата, т.е. построение по произвольно заданному конечному автомату нового с наименьшим числом возможных состояний и обладающего теми же свойствами, что и исходный. На практике задача синтеза автоматов может встретиться в сле­ дующей ситуации: заказчик придумал конкретный оператор, ре­ ализуемый некоторым автоматом, но его базовая подготовка не дает возможности описать и построить задуманный автомат. Тогда исполнитель при помощи заказчика описывает автомат, что дает возможность его синтезировать. Проблемы синтеза автоматов аналогичны проблемам, возни­ кающим в современной алгебре при рассмотрении представления некоторой общей системы в виде отдельных более простых систем того же вида. На практике большое значение имеют задачи, свя­ занные с необходимостью получить информацию о свойствах и состоянии автомата на данный момент времени, не «вскрывая» его, а только сравнивая результаты входного и выходного алфа­ вита. Эта проблема составляет основу поиска методов техниче­ ской диагностики конечного автомата, т. е. поиска его неисправ­ ностей. Порой, только с помощью прочтения или расшифровки «черного ящика» удается узнать о причинах гибели транспортных средств в экстремальных ситуациях. Известны два способа структуризации автомата, его конкрети­ зации: • если абстрактные автоматы могут быть соединены в сети под­ ключением выходов одних автоматов ко входам других, то реша­ ются две задачи: задача композиции —построение автомата, эквивалентного не­ которой сети из исходных автоматов, например на рис. 7.3; задача декомпозиции — представление автомата в виде сети из исходных по заданным свойствам или имеющим заданную структуру; 353