Таблица - переход - автомат
Cтраница 2
В этом параграфе будет предполагаться, что автомат, над которым проводится эксперимент, рассматривается как черный ящик, так что для анализа допустимо лишь использование прилагаемой входной и наблюдаемой выходной последовательностей и, возможно, таблицы переходов автомата. [16]
Бели в автомате Мили А имеется состояние а, для которого функция выходов не определена ни при каком входном сигнале, то такое состояние можно исключить из автомата, выбросив обозначенные им столбцы из таблиц переходов и выходов автомата А и заменив все остальные вхождения состояния а в таблицу переходов автомата А черточками. Возникший в результате такой операции автомат Мили В индуцирует то же самое отображение, что и автомат А. [17]
В случае необходимости найденный автомат Мура интерпретируется как автомат Мили В. Таблица переходов автомата А при этом принимается за таблицу переходов автомата В, а таблица выходов автомата В получается в результате подстановки в его таблицу переходов вместо символов состояний символов, отмечающих эти состояния выходных сигналов ( отметок) автомата А. [18]
Входные сигналы автомата также предполагаются закодированными в двоичном структурном алфавите. Заменяя в таблице переходов автомата каждое его структурное ( закодированное) состояние структурным входным сигналом памяти автомата, вызывающим указанный в таблице переход, мы приходим к понятию таблицы возбуждений автомата. По ней, а также по структурной таблице выходов автомата непосредственно строится его функциональная таблица ( см. § 2), являющаяся исходным пунктом для построения комбинационной части схемы данного автомата. [19]
Для реализации УА на основе модели автомата Мили необходимо построить его таблицу переходов. Для этого в таблице переходов автомата Мура ( табл. 5.1) объединим те состояния автомата Мура, переходы из которых полностью совпадают. [20]
По заданной области запрета или области допустимых слов автсм та Мура А находятся неопределенные состояния автомата. Все вхождения неопределенных состояний в отмеченную таблицу переходов автомата А заменяются черточками, а обозначенные этими состояниями столбцы исключаются из таблицы. Если к числу неопределенных относится начальное состояние автомата, то обозначенный им ( начальный) столбец сохраняется в таблице, но отметка начального состояния делается неопределенной. В случае возникновения недостижимых состояний обозначенные ими столбцы также вычеркиваются. [21]
В случае необходимости найденный автомат Мура интерпретируется как автомат Мили В. Таблица переходов автомата А при этом принимается за таблицу переходов автомата В, а таблица выходов автомата В получается в результате подстановки в его таблицу переходов вместо символов состояний символов, отмечающих эти состояния выходных сигналов ( отметок) автомата А. [22]
Рассмотрим теперь метод получения функций возбуждения элементарных автоматов и функций выходов по графу автомата или по матрице соединений. Эта методика менее громоздка, чем построение функций возбуждения по кодированной таблице переходов автомата в случае канонического метода синтеза, и очень удобна для перехода от этапа абстрактной декомпозиции к функциональной схеме автомата. [23]
Разбиение на 1-классы совершается непосредственно по таблице выходов автомата: в один и тот же 1-класс объединяются все состояния, которым соответствуют одинаковые столбцы в таблице выходов. Далее строится так называемая 1-таблица, получающаяся в результате замены в таблице переходов автомата, внутренних состояний содержащими их 1-классами. [24]
Первый столбец таблицы обозначим символом 1 начальной вершины графа и с нее начинаем построение таблицы переходов автомата. В начале построения таблицы в состояние qj входит один индекс начальной вершины. Если таких стрелок нет, в клетку вписывается - - символ пустого состояния автомата. После заполнения клеток столбца таблицы содержимое каждой клетки, если оно полностью не совпадает с содержимым состояний, отмечающих столбцы, выписывается как новое отмечающее состояние. Процесс построения таблицы переходов считается законченным, если все содержимое каждой клетки таблицы выписано как отмечающее состояние. [25]
Приетупая к классификации автоматов с двумя внутренними состояниями, заметим прежде всего, что в таблицах переходов таких автоматов не может быть более четырех различных строк. Ясно также, что нет смысла различать входные сигналы в автомате Мура, если им соответствуют одинаковые строки в таблице переходов автомата. [26]
Там, где задача раскраски усложнена дополнительными условиями одноцветности вершин, эффективным может оказаться и подход, предполагающий нахождение наибольшего пустого или полного подграфа, а затем группирование около вершин, вошедших в этот подграф, остальных вершин заданного графа. С помощью этого подхода, как показано в [26], можно решить такие задачи, как минимизация длины кода состояний асинхронного автомата, сжатие таблицы переходов автомата ( по строкам и столбцам), параллельная декомпозиция автомата, упрощение системы булевых функций, описывающих асинхронный автомат. Точно так же можно решать и все остальные задачи, перечисленные выше. Из рассмотренных здесь подходов к решению задач логического проектирования данный подход единственно пригоден для решения таких задач абстрактного синтеза автоматов, как минимизация числа состояний синхронного автомата и его декомпозиция. [27]
Неопределенными в этом случае будут все выходные сигналы, в состав которых входит символ области запрета S. Неопределенные состояния характеризуются с помощью предложения 7.2. В частности, для автоматов Мура неопределенными будут все состояния, отмеченные неопределенными выходными сигналами. Начальное состояние является неопределенным, если оно не входит в число элементов таблицы переходов автомата. [28]
В расширенной таблице переходов номера выходных векторов получались из их значений, а здесь в нерасширенной таблице - выходные вектора нумеровались по мере их появления на выходах автомата при его восстановлении. Если номера выходных векторов считать внутренними состояниями, соответствующими этим векторам, то получим восстановленную таблицу переходов автомата. Если теперь в таблице переходов состояния заменить соответствующими им выходными векторами, то получим восстановленную таблицу выходов автомата. [29]
 |
Граф функционирования цифрового автомата. [30] |
Страницы: 1 2 3