Cтраница 1
Представление автомата, при котором е-переходы определяются только состояниями, назовем стандартной формой. [1]
Возможность такого представления автомата состоит в следующем. [2]
Графический способ удобен для представления автоматов с небольшим числом состояний. [3]
Переход от табличной формы представления автомата к графу и обратно не представляет труда. Например, граф автомата, изображенный на рис. 3.2, б и табл. 3.3, задает один и тот же абстрактный автомат. [4]
Теорема Крона - Роудза имеет приложения в теории автоматов и превращается там в утверждение о представлении автомата каскадной композицией триггеров и автоматов простых групп; см. [4], гл. Теоремы декомпозиции для конечных моноидов рассматриваются также в [22], гл. [5]
Примером этому служит задача представления исходного автомата совместной работой заданных стандартных автоматов в виде больших интегральных схем на МОП-транзисторах, которая рассмотрена в предыдущей главе. Весьма перспективным направлением по созданию надежных, быстродействующих автоматов в микроэлектронном исполнении являются однородные универсальные вычислительные среды [153, 375], использование которых позволяет применять методы автоматического синтеза цифровых автоматов с программно изменяемой структурой. [6]
А имеют две координаты: a ( al, а2), Ь - ( bL, Ьг), причем вторая координата нового состояния ( выхода) зависит от второй ( а не от обеих) координаты предыдущего состояния. Аналогичная ситуация имеет место в случае представления автомата в виде каскадного соединения нескольких автоматов. [7]
Описание автоматов Мура и автоматов Мили с асинхронными выходами совпадают по форме и отличаются только логическими соотношениями, задающими функции выходов. В автоматах Мура выход зависит только от состояния, а в автоматах Мили и от входа. Для представления автомата Мили с синхронизируемыми выходами следует его выходные переменные специфицировать как триггеры, а на входы синхронизации и установки этого дополнительного регистра подать те же сигналы начальной установки и синхронизации, что и на остальные управляющие входы автомата. В листинге 3.69 приведено описание автомата Мили, заданного графом переходов ( рис. 3.27), с использованием оператора таблицы. [8]
Когда для данной системы установлены входной и выходной алфавиты и множество состояний, ее словесное описание может быть формализовано с помощью таблицы, графа или матрицы. Таблицы, графы и матрицы - различные формы представления функций F и G конечного автомата, который описывает данную систему. Такое представление необходимо для1 проведения точного анализа или синтеза конечного автомата. Поскольку одной формой представления автомата целесообразно пользоваться при одних обстоятельствах, другой - при других, полезно познакомиться со всеми указанными формами представления. Способы задания являются общими как для неинициальных, так и инициальных автоматов. Для последних должно быть дополнительно указано его начальное состояние. [9]
Главы I-IV посвящены методам теории графов, на которых основано решение задач логического проектирования автоматов. В них рассматриваются теоретико-множественные и алгебраические операции над ориентированными графами, определяются свойства операций и основные алгебраические структуры, которые они образуют по аналогии с известными структурами множеств. Решаются задачи разложения графов по алгебраическим и теоретико-множественным операциям. Доказываются теоремы о разложении графов по различным операциям, формулируются алгоритмы разложения, даются оценки числа разложимых графов, а также решается задача отыскания минимального дополнения неразложимых графов до разложимых. Главы V-IX посвящены изложению логического проектирования автоматов и вычислительных структур с помощью методов теории графов. Здесь излагается алгебра абстрактных автоматов, которая на абстрактном уровне описывает различные виды соединений автоматов при построении схем сложных автоматов, и проблема декомпозиции абстрактных автоматов, которая заключается в представлении сложного абстрактного автомата совместной работой более простых абстрактных автоматов. Решается задача общей декомпозиции, позволяющая любой абстрактный автомат представлять работой элементарных абстрактных автоматов с минимальным числом связей между ними, и задача декомпозиции автомата на заданные блоки, которая приводит к представлению автомата в виде однородной структуры заданных стандартных блоков, соединенных между собой последовательно, параллельно или произвольным образом. Описывается декомпозиционный метод синтеза автоматов, основанный на решении задачи общей декомпозиции автоматов, исключающий этап структурного синтеза и приводящий к единому сквозному синтезу автоматов, который решает задачи логического проектирования на абстрактном уровне. [10]