Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
Глава 10. АБСТРАКТНЫЕ ЦИФРОВЫЕ АВТОМАТЫ10.1. ОСНОВНЫЕ ПОНЯТИЯЦифровом (дискретный) автомат можно трактовать как устройство, осуществляющее прием, храпение и преобразование дискретной информации по некоторому алгоритму. С определенной точки зрения к автоматам можно отнести как реальные устройства (вычислительные машины, живые организмы и т. п.), так и абстрактные системы (математические машины, аксиоматические теории Общую теорию автоматов подразделяют на абстрактную и структурную. Различие между ними заключается в том, что абстрактная теория, отвлекаясь от структуры автомата (т. е. не интересуясь способом его построения), изучает лишь поведение автомата относительно внешней среды. Абстрактная теория автоматов близка, таким образом, теории алгоритмов, являясь по существу ее дальнейшей детализацией. В противоположность абстрактной теории, структурная интересуется как структурой самого автомата, так и структурой входных воздействий и реакций автомата на них. В структурной теории изучаются способы построения автоматов, способы кодирования входных воздействий и реакций автомата. Таким образом, структурная теория автоматов является продолжением и дальнейшим развитием абстрактной теории. Опираясь на аппарат булевых функций и на абстрактную теорию автоматов, структурная теория дает эффективные рекомендации по разработке реальных устройств вычислительной техники. Абстрактный цифровой автомат А определяется совокупностью пяти объектов
Рис. 10.1.
Рис. 10.2. автомата А, задающая отображение Иныш словами, функция переходов По способу формирования функции выходов выделяют три типа абстрактных автоматов: автомат Мили, автомат Мура, С-автомат. В абстрактном автомате Мили функция выходов X задает отображение Произвольный абстрактный автомат Милан или Мура имеет один входной и один выходной каналы (рис. 10.1). Произвольный абстрактный С-автомат имеет один входной и два выходных канала (рис. 10.2). Выделяют полностью определенные и частичные автоматы. Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов и функция выходов определены для всех пар Частичным называется абстрактный цифровой автомат, у которого функция переходов или функция выходов, или обе эти функции определены не для всех пар Абстрактный цифровой автомат называется инициальным, если на множестве его состояний 5 выделяется специальное начальное со стояние Говорят, что абстрактный автомат функционирует в дискретном автоматном времени состояние
автомат Мура — системой уравнений;
а С-автомат — системой уравнений:
Иными словами, если на вход инициального абстрактного автомата Мили или Мура, установленного в начальное состояние подавать буква за буквой некоторую последовательность букв входного алфавита Таким образом, на уровне абстрактной теории функционирование цифрового автомата понимается как преобразование входных слов в выходные слова. Понятие состояния в определении абстрактного автомата введено в связи с тем, что большинство реальных процессов, которыми управляют реально построенные цифровые автоматы, требуют для своего правильного течения знания предыстории развития процесса во времени. Иными словами, выходной сигнал, выдаваемый автоматом в данный момент времени, определяется не только входным воздействием на автомат, но и состоянием, в котором автомат в этот момент времени находился Например, если нужно построить автомат управления переключением светофора при условии, что на вход автомата поступает только сигнал «переключить светофор», то в каждый момент времени для организации правильной работы автомата, кроме входного сигнала «переключить светофор», необходимо иметь информацию о положении светофора в предшествующий момент времени. Эта информация и обеспечивается наличием различных состояний абстрактного автомата. Абстрактные цифровые автоматы, соответствующие введенному определению абстрактного автомата, называют также абстрактными автоматами с памятью, так как существование в автомате множества различных его состояний возможно только при наличии у автомата памяти. Ряд процессов, которыми управляют реальные автоматы, не требуют для своего правильного течения знания предустории развития процесса во времени. В автоматах, управляющих такими процессами, Таблица 10.1
выходной сигнал определяется только входным воздействием на автомат. У казанные автоматы на абстрактном уровне представления определяются с помощью тройки Алфавиты входов, состояний и выходов автоматов задаются, как обычные множества, например, перечислением своих элементов. Функции переходов и выходов могут быть заданы матрично, графически и При матричном способе автомат представляется либо двумя таблицами: таблицей переходов и таблицей выходов, либо матрицей соединений Таблица переходов задает отображение Таблица переходов произвольного полностью определенного абстрактного автомата строится следующим образом. Столбцы таблицы помечаются буквами входного алфавита автомата, а строки таблицы — буквами алфавита состояний автомата. В клетке таблицы переходов, находящейся на пересечении столбца, отмеченного входным сигналом Таблица 10.2
Таблица 10.3
Таблица 10.4
находящейся на пересечении столбца, отмеченного входным сигналом Таблица выходов полностью определенного автомата Мура строится более просто: каждому состоянию автомата приписывается свой выходной сигнал. Пример таблицы выходов автомата Мура с алфавитом состояний Очевидно, абстрактный полностью определенный С-автомат задается двумя таблицами выходов, первая из которых ечть таблица выходов автомата Мили, а вторая — таблица выходов автомата Мура. Если автомат Мили частичный, то в некоторых клетках его таблицы выходов может стоять прочерк, означающий отсутствие выходного сигнала. При этом прочерк обязательно ставится в тех клетках таблицы выходов, которые соответствуют таким же клеткам с прочерком в таблице переходов автомата Мили. Последнее связано с тем, что если в частичном автомате Мили имеется пара Прочерки в некоторых клетках таблицы выходов частичного автомата Мура не связаны с прочерками в клетках его таблицы переходов. Это определяется тем, что выходной сигнал автомата Мура зависит только от состояния, в котором находится автомат. Например, таблица выходов частичного автомата Мура, заданного таблицей переходов (табл. 10.2), Таблица 10.5
Таблица 10.6.
Таблица 10.7
может быть представлена и как табл. 10.4, если в каждом своем состоянии автомат выдает какой-то выходной сигнал, и как табл. 10.6, если значение выходного сигнала автомата для некоторых состояний неоиределено. На практике таблицы переходов и выходов автомата часто совмещаются в одну таблицу, называемую отмеченной таблицей переходов автомата. Отмеченная таблица переходов полностью определенного автомата Мили, представленного таблицей переходов (табл. 10.1) и таблицей выходов (табл. 10.3), сведена в табл. 10.7. Отмеченная таблица переходов частичного автомата Мура (табл. 10.2) и таблица выходов (табл. 10.4), сведена в табл. 10.8. Кроме рассмотренных выше таблиц переходов и выходов, произвольный абстрактный автомат может быть описан матрицей соединений. Такое описание — один из способов матричного задания абстрактных автоматов. Матрица соединений произвольного абстрактного автомата является квадратной и содержит столько столбцов (строк), сколько различных состояний имеет рассматриваемый автомат. Каждый столбец (строка) матрицы соединений помечается буквой состояния автомата. Если автомат инициальный, то первый слева столбец и первая сверху строка матрицы его соединений помечаются буквой начального состояния автомата В клетке матрицы соединений, находящейся на пересечении столбца, помеченного буквой состояния Если матрицей соединения задается абстрактный автомат Мура, то выходными сигналами помечаются состояния автомата, идентифицирующие строки матрицы соединений. Таблица 10.8
Рис. 10.3
Рис. 10.4
Рис. 10.5 При графическом способе задания абстрактные автоматы представляются ориентированными графами; состояния автомата изображаются вершинами графа, а переходы между состояниями — дугами между соответствующими вершинами. При этом каждой дуге графа приписывается некоторая буква При аналитическом способе задания абстрактные автоматы представляются четверкой объектов
Аналитическое задание автомата Мили, представленного отмеченной таблицей переходов (табл. 10.7), имеет следующий вид. Автомат
Рассмотрим эквивалентное преобразование автоматов. Эквивалентными называются автоматы, индуцирующие одно и то же отображение множества слов во входном алфавите в множество слов в выходном алфавите. Рассмотрим только преобразование автомата Мура в эквивалентный ему автомат Мили. Преобразование автомата Мили в эквивалентный ему автомат Мура осуществляется несколько сложнее. Переход от автомата Мура к эквивалентному ему автомату Мили удобно осуществлять при графическом способе задания автоматов. В этом случае он сводится к переносу выходного сигнала Разработка реальных автоматов (представленных хотя бы на уровне принципиальных электрических схем) требует их задания сначала на абстрактном уровне с последующим переходом на структурный уровень, учитывающий используемые в схеме автомата логические элементы и связи между ними. В связи с этим возникает задача синтеза абстрактного автомата, исходя из какого-то начального, например, словесного описания его работы. Существующие алгоритмы синтеза абстрактных автоматов на практике обычно не используются из-за сложности и громоздкости вычислеиий и поэтому не включены в материал учебника. Однако для лучшего уяснения понятия абстрактного автомата и способов его задания здесь рассмотрим пример синтеза абстрактного автомата, основываясь на чисто умозрительных соображениях. Пример. Построить абстрактный цифровой автомат управления переключением спетофора при условии, что на вход автомата поступает только сигнал «переключить светофор». Обозначим этот сигнал буквой
Рис. 10.6
Рис. 10.7 Очевидно, входной алфавит X такого автомата будет состоять из двух букв: В заключение отметим, что мы рассматриваем только детерминированные автоматы, у которых выполнено условие однозначности переходов: автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейти более чем в одно состояние. Автомат, заданный таблицей переходов, всегда детерминированный, так как на пересечении столбца
|
1 |
Оглавление
|