Cтраница 1
Матрица соединений автомата обладает тем свойством, что в любой ее строке каждая буква входного алфавита должна встречаться не более одного раза. Это условие связано с однозначностью функций переходов и выходов автомата и называется условием однозначности. [1]
Матрицу соединений RA автомата А разбиваем на k2 клеток порядка I каждая. [2]
Пусть матрица соединений R автомата А является ПКМС или существует подстановка t T, которая приводит ее к виду ПКМС. [3]
Записываем матрицы соединений Rz автономных автоматов Аг и разбиваем их на 4 клетки. [4]
Предположим, что матрица соединений R автомата А является / г-правильной клеточной матрицей. [5]
Определим теперь по матрице соединений автомата функции выходов. [6]
Применяем полученную подстановку к матрице соединений RA автомата А. [7]
Применяем полученную подстановку t e Т к матрице соединений RA автомата А. [8]
Более часто, чем указанные матрицы, используется квадратная матрица, называемая матрицей соединений автомата, которая строится следующим образом. Строки и столбцы матрицы соединений соответствуют различным состояниям автомата, причем первая строка и первый столбец соответствует начальному состоянию q Q. Y или дизъюнкция выходных букв, которые появляются на выходе автомата. Если ни одна из букв входного алфавита не переводит автомат из состояния qh в qi, то на соответствующем пересечении ставится нуль. [9]
Теорема 8.9. Автомат А представим последовательной работой двух автоматов Л4 и AZ, если и только если существует подстановка t T, переводящая матрицу соединений R автомата А в k - правильную клеточную матрицу соединений. [10]
Теорема 8.6. Автомат А с п k I состояниями представим суммой двух автоматов AI и А2 соответственно с k и t состояниями ( параллельной поочередной работой двух автоматов), если и только если существиет подстановка t e Т алфавита состояний, которая преобразует матрицу соединений R автомата А к виду регулярной клеточной матрицы соединений. [11]
Легко видеть, что автомат не может перейти в недостижимое состояние из начального под действием допустимых входных слов. Поэтому в матрице соединений автомата строки и столбцы, помеченные недостижимыми состояниями, можно вычеркнуть. В этом случае индуцируемое автоматом отображение не изменится. Следовательно, при изучении автоматных отображений, которые будут описаны в следующем параграфе, можно ограничиться рассмотрением лишь связных автоматов. [12]
По графу автомата или матрице соединений требуется получить программу настройки ВС, реализующую отображение, индуцируемое исходным автоматом. Для этого вначале по матрице соединений автомата производим оптимальную декомпозицию, в результате которой получаем матрицы соединений элементарных абстрактных автоматов. По ним записываем функции возбуждения элементарных автоматов и функции выходов, минимизируем их и описанным выше способом получаем программу настройки ВС. В качестве примера синтеза синхронных автоматов в ВС на рис. 9.15 и 9.16 соответственно показаны программы настройки ВС, в которой используется модифицированный элемент, на реализацию автомата, моделирующего выработку условного рефлекса ( пример 9.2) и дешифратора последовательного действия ( пример 9.3), построенные по минимизированным функциям возбуждения триггеров и функциям выходов, найденным в результате декомпозиции. [13]
Если в абстрактной теории автоматов везде под автоматом подразумевается абстрактный автомат, заданный либо графоидом, либо матрицей соединений, то в структурной теории автоматов, говоря об автомате, имеют в виду структурную схему, состоящую из элементов некоторого стандартного комплекса, в который входят набор элементарных автоматов и функционально полный набор логических элементов. Поэтому на структурном уровне изучаются методы перехода от гра-фоида или матрицы соединений автомата к структурной схеме автомата, приемы построения схем сложных автоматов из схем элементарных автоматов и логических элементов, рассматриваются способы кодирования состояний, входных и выходных сигналов автомата, различные варианты которых определяют, в конечном счете, сложность структурной схемы автомата при неизменном законе его функционирования. [14]
Отсюда следует, что нужно проводить декомпозицию автомата А на элементарные автоматы с минимальным числом связей между ними. Так как число связей зависит от числа запрещенных переходов в матрице соединений исходного автомата, то требуется таким образом изоморфно преобразовать матрицу соединений R автомата А, чтобы она содержала минимальное число запрещенных переходов. [15]