АВТОМАТОВ СИНТЕЗ
— построение автомата по заданному его поведению «вход — выход». Проблема синтеза наиболее подробно исследовалась для автоматов конечных, поскольку к этому случаю сводятся многие практические задачи, связанные с проектированием разного рода управляющих и вычисл. устройств дискретного действия. Синтез
бесконечных автоматов в большинстве случаев имеет теор. интерес. Он не представляет больших трудностей, т. к. к синтезируемым автоматам, как правило, не предъявляют дополнительных требований, кроме единственного, — чтобы они
реализовали требуемое отображение «вход — выход». Оно же задается так, что метод синтеза оказывается достаточно простым. Напр., по частично рекурсивной ф-ции, заданной формулой, в которой использованы только знаки операторов суперпозиции, примитивной рекурсии и минимизации, нетрудно построить Тьюринга машину, вычисляющую эту ф-цию. Более сложная проблема возникает только в тех случаях, когда приходится синтезировать бесконечные автоматы, исходя из практических задач, напр., в случае автоматов регистровых. К синтезу таких автоматов обращаются при проектировании операционных устройств ЦВМ.
Трудности А. с. зависят в основном от того, как заданы условия функционирования автомата. Чем выразительнее язык, применяемый для задания условий функционирования автомата (т. е., чем удобнее он для заказчика), тем сложнее метод синтеза. Во многих случаях может оказаться, что единого метода синтеза не существует. Поэтому для ряда классов автоматов, в частности для конечных автоматов, разрабатывают спец. языки, с помощью которых удобно задавать условия функционирования автоматов и для которых существуют методы синтеза (см. Регулярные события и выражения, Язык логический для задания автоматов).
Процесс синтеза сложного конечного автомата обычно подразделяют на несколько этапов. На 1-м этапе, называемом этапом блочного синтеза, осуществляется разбиение автомата на отдельные блоки, определяются задачи, которые должны решать эти блоки, намечается общий план обмена информацией между блоками. На 2-м этапе, называемом этапом абстрактного синтеза, на основании задач, решаемых каждым отдельным блоком, определяется объем памяти, необходимый для данного блока, и устанавливаются те изменения состояний памяти под воздействием входных сигналов, которые должен реализовать данный блок для того, чтобы он мог выполнять поставленные перед ним задачи. На 3-м этапе — этапе структурного синтеза — осуществляется выбор элементов для построения схемы и устанавливаются правила соединения этих элементов. Во многих случаях элементы бывают заданы заранее, тогда схема строится на этих элементах. На 4-м этапе — этапе надежностного синтеза — преобразовывают построенные схемы с целью обеспечения надежности их функционирования. Наконец, если автомат надо построить из физ. элементов, на 5-м этапе — этапе тех. синтеза — обнаруживают искажения сигналов, возникающие вследствие неидеальности применяемых элементов, и принимают меры к устранению этих искажений. За исходные данные более высокого этапа синтеза берут, как правило, результаты, получаемые на предыдущих этапах.
Приведенное выше разделение А. с. на этапы позволяет лишь в общем ориентироваться в том, через какие стадии проходит решение задачи А. с. В ряде случаев приходится делать те или иные отступления от приведенной выше последовательности этапов. Напр., при синтезе достаточно простых автоматов этап блочного синтеза обычно опускается. Наоборот, при синтезе особо сложных автоматов возможно многократное возвращение к этому этапу. При некоторых спец. приемах синтеза этапы абстрактного, структурного и тех. синтеза так переплетаются между собой, что не всегда удается четко разграничить их. Наконец, учет соображений надежности обычно начинается на более ранних этапах. В результате этого на последнем этапе получают окончательное решение. Проблема А. с. обратна проблеме автоматов анализа, но обычно сложнее проблемы анализа.
Лит.: Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464—469].
В. М. Глушков, М. И. Кратко.
