Cтраница 2
Использование теоремы 8.15 позволяет значительно сократить перебор по сравнению с полным, однако при большом п число подстановок, подлежащих перебору, достаточно велико. Поэтому предложим эвристический прием, ведущий к существенному сокращению перебора при поиске подстановки, приводящей матрицу соединений автомата к виду квазиправильной матрицы соединений. [16]
Отсюда следует, что нужно проводить декомпозицию автомата А на элементарные автоматы с минимальным числом связей между ними. Так как число связей зависит от числа запрещенных переходов в матрице соединений исходного автомата, то требуется таким образом изоморфно преобразовать матрицу соединений R автомата А, чтобы она содержала минимальное число запрещенных переходов. [17]
Общая декомпозиция абстрактных автоматов решает проблему кодирования состояний автомата и приводит к декомпозиционному методу структурного синтеза, который состоит в следующем. Матрица соединений абстрактного автомата дополняется до правильной клеточной матрицы с некоторым числом запрещенных переходов. Путем преобразования матрицы соединений автомата отыскивается такой изоморфный автомат, матрица соединений которого содержит минимальное число запрещенных переходов и обеспечивает наилучший или близкий к нему вариант кодирования состояний. По этой матрице записываются обобщенные функции переходов и выходов автомата, из которых после минимизации получаются функции возбуждения и выходов элементарных автоматов. По функциям возбуждения и выходов строится близкая к оптимальной ( с точки зрения минимального числа логических элементов) структурная схема синтезированного автомата. [18]
Очевидно, что обратный автомат существует только тогда, когда отображение f является биективным отображением. В этом случае в любой строке его матрицы соединений не может быть двух пар вход - выход, которые имеют одинаковые выходные сигналы. Поэтому для построения матрицы соединений обратного автомата А-1 достаточно в матрице соединений R автомата А в каждой паре вход - выход поменять местами элементы этой пары. [19]
Очевидно, что обратный автомат существует только тогда, когда отображение f является биективным отображением. В этом случае в любой строке его матрицы соединений не может быть двух пар вход - выход, которые имеют одинаковые выходные сигналы. Поэтому для построения матрицы соединений обратного автомата А-1 достаточно в матрице соединений R автомата А в каждой паре вход - выход поменять местами элементы этой пары. [20]
Основной задачей структурного синтеза автоматов является построение функциональной ( структурной) схемы сложного автомата из более простых автоматов, которые называют элементарными автоматами, по графу исходного автомата. Пусть задано некоторое конечное множество элементарных автоматов и задан произвольный конечный автомат А. Необходимо найти алгоритм, позволяющий по заданному графу или матрице соединений автомата строить некоторую композицию) элементарных автоматов так, чтобы полученный в результате композиции автомат индуцировал отображение, совпадающее с отображением или продолжающее отображение, индуцируемое автоматом А. [21]
До сих пор рассматривались автоматы первого и второго рода, у которых отображение F множества состояний Q в себя определено для любой пары элементов ( 7, х), где q Q и х е X. Такие автоматы называются вполне определенными. Автоматы ( любого рода), у которых отображение F множества Q в себя определено не для всех пар q Q и х Х, называются частичными автоматами. В тех местах таблиц переходов и выходов, а также матриц соединений автоматов, в которых соответствующие переходы и выходы не определены, будем ставить нули или черточки. [22]