Antik (1082243), страница 3
Текст из файла (страница 3)
Заголовками строк служат либо идентификаторы состояний, либокоды состояний. Каждому входному символу соответствует столбец с заголовком в виде символа или его кода. (Разумеется, можно использовать транспонированную таблицу со строками входными символами и столбцами - состояниями.) Каждая клеткатаблицы с координатами [i,j] содержит, в общем случае, два значения: (bp , sq), где bp =f(si, аj) - выходное значение, sq:=g(si, аj) –новое (следующее) состояние.
Таблица автомата Мура будет содержать во всех клетках одной строки одно и тоже выходное значение. Поэтому изображение таблицы автомата Мура будет проще, если клетка содержит только одно значение - новое состояние, но есть столбец с выходными значениями для каждого состояния.
Первая строка таблицы для инициальных автоматов,чаще всего, соответствует начальному состоянию автомата (начальному шагу алгоритма).Пример 4.1.-1. Инкрементор. Автомат - инкрементор с одноразрядным входом (a) и одноразрядным выходом (b). На входпоступает последовательно многоразрядное число в дополнительном коде, начиная с младших разрядов. На выходе синхронно появляется результат - число на единицу большее, чем исходное.Решение: Пусть автомат имеет два состояния p1 и p0.p1 - соответствует значению переноса 1, это состояние является начальным;p0 - соответствует значению переноса 0.Тогда согласно правилам сложения одноразрядных двоичных кодов, получим таблицу 1.
Таблица 2 получена из таблицы 1присваиванием двоичных кодов состояниям. По таблице 2 могутбыть получены таблицы истинности (например, в виде картыКарно) функций f и g - табл.3, табл.4.14Таблица-1входсостояниеp1p0011,p00,p00,p11,p0Таблица -3f10Таблца-2010b=s+a10110011,00,00,11,0Таблица-4g10000110s’ = s & aСхема СЦА - инкрементора может быть такой, как на рис.7а.a)б)Рис.7. Инкрементор в дополнительном кодеДля правильной интерпретации работы схемы необходимоусловиться о правилах (протоколе) взаимодействия схемы свнешней средой. Например: 1) начальное входное значение и начальное состояние устанавливается при start=1; 2) выходные значения читаются при значениях start=0 и syn=0.
Если считать, чтофункция суммирования одноразрядных двоичных чисел задана(р,s)=HS(x,y), то аналогичную схему можно получить, синтезируяСЦА как автомат операционного типа. В этом случае каноническое уравнение автомата конкретизируется как(s:,b)=HS(s,a) при s(0)=1.Соответствующая схема приведена на рис.7б.4.2.Автоматный граф (граф переходов).При описании автоматов удобно отобразить математическую структуру абстрактного автомата на другую математическую структуру - ориентированного графа.15G = (S,D),где S - множество вершин графа,D - множество дуг графа - упорядоченных пар вершин.Структура графа помогает выделить два объекта математической структуры автомата: состояния - вершины графа и функцию переходов - дуги графа, остальные объекты автомата вводятся как пометки дуг или вершин.
Дуги помечаются символамивходного алфавита, а символами выходного алфавита помечаются дуги или вершины в зависимости от типа автоматаG = ({si},{dj[ak/bh]}) для автомата Мили,G = ({si[bh]},{dj[ak]})для автомата Мура.Диаграммой будем называть какое-либо геометрическоеизображение графа. Диаграмма автомата - инкрементора можетиметь вид рис.8.Дуги смежные одной и той же паре вершин и одинаково направленные (параллельные дуги) могут быть объединены в однудугу, помеченную соответствующим образом - рис.8б (а - имявходной переменной).a)б)Рис.8.
Диаграмма автомата - инкрементораАвтоматный граф должен удовлетворять условию однозначности, т.е. не должно существовать двух дуг, выходящих изодной и той же вершины, с одинаковыми входными пометками.Автоматный граф полностью определенного автомата удовлетворяет условию полноты, т.е. для всякой вершины s и для всякоговходного символа q имеется дуга, помеченная символом q и выходящая из s.Рис.9. Автоматная диаграмма D-триггераПримером диаграммы автомата Мура может служить авто-16матная диаграмма D-триггера (рис.9).Отличие этой диаграммы от предыдущей в том, что выходным значением помечены не дуги, а состояния.4.3.
Блок-схемаБлок-схема автомата управляющего типа – это некотораяграфическая вариация диаграммы автомата. В блок-схеме имеются вершины двух типов: 1) операторные (прямоугольные), в которых записывается выходное значение, в общем случае какфункция входного значения (при этом одна операторная вершинасоответствует одному состоянию автомата); 2) условные илипредикатные (непрямоугольные, чаще всего ромбовидные), в которых записываются некоторые логические функции от двоичных входных переменных автомата. Выходящие из условнойвершины стрелки помечаются значениями этих функций.
Вершины соединяются дугами, показывающими все возможные переходы. Начальная вершина помечается.Рис.10. Блок-схема автомата D-триггераБлок-схема удовлетворяет условию однозначности, еслилюбой путь, соединяющий две операторные вершины, не содержит входных переменных, которые участвует в вычислении условия более одного раза. Блок-схема автомата D-триггера приведена на рис.10.4.4.Блок-текстБлок-текст это описание блок-схемы в виде последовательного текста. В блок-тексте используются блоки двух типов операторные и блоки переходов: операторные блоки - в скобках вида{.....}, блоки перехода - в скобках вида <<...>>.
И те, и другиеблоки могут снабжаться метками, стоящими перед блоком. Операторный блок соответствует операторной вершине блок-схемы.В блоках перехода используется оператор GO в одной из двухформ:17GO m - безусловный переход,GO (P; m0,m1,m2,...) - условный переход,где, m0,m1,... - метки блоков, P - значение, интерпретируемоеоператором GO как неотрицательное целое число, являющеесяпорядковым номером метки в списке меток оператора GO. С этойметки должно быть продолжено выполнение алгоритма.
Блокиусловных переходов соответствуют условным вершинам блоксхемы. Например, см. рис.11.Рис.11. Блок-текст5.Автономные автоматыСЦА, у которого единственным изменяющимся входнымсигналом является сигнал синхронизации, называется автономным автоматом.Автомат, имеющий n-разрядную память, имеет 2n состояний. Соответственно полный граф переходов автомата имеет 2nвершин. У автономного автомата из каждой вершины выходитровно по одной дуге. Граф автомата может иметь более одногокомпонента связности. В каждом компоненте связности графа автономного автомата может быть только один цикл, к этому циклумогут быть подвешены деревья, ориентированные в его сторону.Граф инициального автомата имеет только один компонент связности с числом вершин N≤2n (рис.12).
Число состояний (вершин)в цикле инициального автономного автомата называют модулемсчета.Рис.12. Диаграмма инициального автономного автомата18Любой неавтономный автомат можно сделать автономным,если зафиксировать входной символ. При этом все переходы вновое состояние осуществляются при одном и том же значениивходного символа.В инженерной практике автономные автоматы используются как счетчики и в качестве генераторов периодических последовательностей.5.1.Параллельная композицияПараллельная или синхронная композиция автономных автоматов приведена на рис.13. Интересны счетные возможноститакой композиции, т.е. число состояний в цикле (модуль счета).Этот модуль равен наименьшему общему кратному всех модулейавтоматов, входящих в синхронную композицию.
Модуль будетнаибольшим, если модули автоматов взаимно простые числа –тогда он будет равен их произведению.AA1TAA2CLCLTРис.13. Параллельноевключение АА5.2.AA1t AA2Рис.14. Последовательноевключение ААПоследовательная композицияПоследовательная или асинхронная композиция синхронных автономных автоматов приведена на рис.14. Для переключения автомата АА2 используется изменение значения какого-либоодноразрядного выходного сигнала автомата АА1. Счетные возможности такой композиции максимальны, если сигнал t выбрантак, что он изменяет свое значение за цикл автомата AA1 не более двух раз, т.е.
переключающий фронт ровно один за цикл. Тогда модуль композиции равен произведению модулей автономных автоматов.196.Эквивалентные автоматы6.1.Изоморфные и эквивалентные автоматыАвтоматы изоморфны если их описание одинаково с точностью до переобозначений.Два инициальных автомата будем называть эквивалентнымиавтоматами, если любую одну и ту же входную последовательность они перерабатывают в одну и туже выходную последовательность. Неинициальные автоматы будем называть эквивалентными, если для любого состояния взятого в качестве начального одного из автоматов найдется в другом автомате состояние,назначив которое начальным получим эквивалентность переработки информации входной в выходную.6.2.Минимальные автоматыАвтомат, эквивалентный заданному и имеющий наименьшеевозможное число состояний, называется минимальным.
Если автоматы всюду определены и эквивалентны, то они имеют изоморфные минимальные автоматы. Для частично-определенныхавтоматов это положение может не выполняться.Минимизация автомата возможна, если в автомате есть состояния, которые могут быть объединены в одно состояние. Такие состояния называют эквивалентными состояниями. Иначеговоря, автомат минимальный, если у него нет эквивалентных состояний.Воспользуемся понятием эквивалентности автоматов и переформулируем его для состояний. Состояния si, sj одного и тогоже автомата эквивалентны, если при подаче одной и той же (любой) входной последовательности с начальными состояниями siили sj образуются одинаковые выходные последовательности.Для эквивалентности двух состояний автомата Мили с N состояниями (N>1) достаточно, чтобы совпадали реакции этих двухсостояний на любые возможные входные последовательностидлины, не превышающей N-1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
