Cтраница 1
Задача синтеза автоматов Мура является, более общей, чем задача синтеза автоматов Мили: поскольку всякий автомат Мура можно интерпретировать как автомат Мили, то, научившись синтезировать автоматы Мура, тем самым научимся синтезировать и автоматы Мили. [1]
Задача синтеза автоматов - в вычислительной среде ( ВС) состоит из двух задач: общей задачи синтеза автоматов в ВС и задачи реализации логических сетей автоматов в ВС. Эти задачи заключаются в получении программы настройки элементов вычислительной среды либо по абстрактному автомату, заданному графом или матрицей соединений, либо по структурной схеме ( логической сети) автомата, причем задача реализации логической сети в ВС является частью общей задачи синтеза автоматов в ВС. Оптимизация синтеза автоматов в ВС, по существу, сводится к минимизации числа элементов вычислительной среды, настраиваемых на схему синтезируемого автомата. Задача оптимизации структурной схемы заключается в минимизации числа функциональных элементов, образующих схему автомата, а задача оптимизации топологического размещения логической сети в среде сводится к минимизации количества связей и минимизации суммарной длины связей в схеме автомата. Оптимальная декомпозиция автоматов решает задачу минимизации числа функциональных элементов структурной схемы и задачу минимизации количества связей в схеме автомата. [2]
Решение задачи синтеза автоматов, имеющих оптимальные параметры, с помощью электронных цифровых машин требует разработки алгоритмов процессов проектирования. Для этого необходимо математизировать процессы проектирования и разработать методику оптимального решения основных задач синтеза схем машин-автоматов и автоматических линий с помощью быстродействующих вычислительных машин. [3]
Что касается канонической задачи синтеза автоматов, то она по своему существу неоднозначна. [4]
Обоснование описанного метода решения задачи синтеза автомата по индуцируемому им отображению вытекает из результатов второго параграфа настоящей главы и из сущности описанных в предыдущих параграфах алгоритмов синтеза автоматов по представляемым ими событиям. Некоторых пояснений заслуживает лишь способ образования областей запрета. [5]
Тем самым предложенный метод решения задачи синтеза автомата по индуцируемому им отображению полностью обоснован. Попутно доказано следующее предложение. [6]
В свою очередь, решая задачу синтеза автомата Мура, мы можем, в силу результатов § 4, считать, что заданные нам регулярные события требуется представить не множествами выходных сигналов, а множествами ( внутренних) состояний автомата. [7]
Вопрос о близости общей и канонической задач синтеза автоматов не столь очевиден. Тем не менее существует стандартный прием сведения общей задачи синтеза автоматов к канонической задаче синтеза, которая всегда имеет решение, основанный на следующем утверждении. [8]
Гораздо менее ясен вопрос о близости канонической и общей задач синтеза автомата. Более того, заранее неясно, имеет ли вообще решение произвольная общая задача синтеза. Нетрудно видеть, что умение решить общую задачу синтеза позволяет решить и каноническую задачу. Если применить к этому множеству метод решений общей задачи синтеза ( в предположении, что такой метод существует), то мы найдем автомат, в котором каждое событие Sf множества М будет представлено некоторым множеством TV, выходных сигналов. Ввиду автоматности множества событий М различные события этого множества попарно не пересекаются. Но тогда не могут, очевидно, пересекаться и представляющие их множества выходных сигналов. Заменяя все выходные сигналы каждого такого множества одним выходным сигналом ( особым для каждого множества), мы решаем тем самым каноническую задачу синтеза. [9]
Задача синтеза автоматов Мура является, более общей, чем задача синтеза автоматов Мили: поскольку всякий автомат Мура можно интерпретировать как автомат Мили, то, научившись синтезировать автоматы Мура, тем самым научимся синтезировать и автоматы Мили. [10]
Абстрактная теория автоматов без памяти совершенно тривиальна, а структурная теория таких автомате много легче, чем теория произвольных автоматов с памятью. Основная идея излагаемой методики синтеза автомата состоит в том, чтобы еще на уровне абстрактной теории преодолеть основные затруднения, вызванные наличием памяти, а на уровне структурной теории свести задачу синтеза автомата к задаче синтеза комбинационных схем. [11]