ВОПРОСЫ К ЭКЗАМЕНУ ПО ТЕОРИИ АВТОМАТОВ. Вопросы к экзамену Строки. Префиксы, суффиксы, подстроки. Формальные языки
Скачать 3.16 Mb.
|
Минимизация сложности комбинационных схем: аналитический метод, метод Карт Карно (3,4,5 переменных). Критерием сложности к реализации является колич-во переменных и знаков логических д-ий в представляемой ф-ии. Основная идея минимизации сост в выполнении операции склеивания,в рез-те которой уменьшается кол-во термов и ранг полученных термов меньше ранга исходных.Термы,отлич-ся значением одной переменной,наз соседними. Суть аналитического метода сост в том,что к исходной записи ф-ии непосредственно примен-ся аксиомы и теоремы алгебры логики. F(x,y,z)=xyz + xy + z = xy(z+1)+z = xy + z. Метод Карт Карно: 1).исходная ф-ия представл в виде СДНФ 2) Минтермы, образующие СДНФ, заносятся в карту Карно в соответствующие клетки в виде “1”. Пустые “0”. 3).выделение групп.Каждая группа-это множ-во соседних клеток,заполненных единицами,причём колич-во клеток в группе м.б.=2,4,8…2k. Нужно стремится к тому чтобы групп было как можно меньше, но сами они были как можно больше. 4).анализ групп и склеивание.Если группа содержит две соседних клетки,то в рез-те склеивания получается терм,имеющий ранг на единицу меньший,чем исходный терм.Если группа сод-т четыре соседних клетки,то ранг рез-та уменьшен на два.Если в группе k-соседей,то ранг рез-та уменьшен на k. 5) полученные после склеивания термы объединяются знаком дизъюнкции. Карты Карно 5-ти переменных им особенности: 1.группы д.б. симметричны относительно разделяющей линии.2.м.б. группы,имеющие аналитическое,но не геометрическое соседство.Такие группы следует искать в симметричных относительно разделительной линии столбцах. Понятие базиса логических функций. Примеры Примеры базисов. Базис Буля: {∧, v, ¬} Базис Жегалкина: {1,⊕,&} Конъюктивный базис: {&; −} Дизъюктивный базис: {+; −} Базис Вебба: {↓} Базис Шеффера: {|} 7Сокращенный базис Буля (ИЛИ-НЕ) 8Универсальный базис Буля (И-НЕ) Минимизация сложности комбинационных схем: метод Квайна-Мак-Класски Логические ф-ии м.б. представлены различным количеством переменных и знаком логических д-ий.Основная идея минимизации сост в выполнении операции склеивания,в рез-те которой уменьшается кол-во термов и ранг полученных термов меньше ранга исходных.Термы,отлич-ся значением одной переменной,наз соседними. Сначала метод был предложен Квайном,суть кот сост в том,что составлялась таблица,где в столбцах и строках перебирались все термы,входящие в минимизируемую функцию,представленную в виде СДНФ.Если некоторая пара склеивалась,то в соответствующую клетку таблицы вписывался рез-т склеивания.Результаты склеивания формировали вторую таблицу и т.д.Недостаток сост в том,что обработка происходила в символьных изображениях и была трудоёмка при большом колич-ве переменных.Мак-Класски ввёл двоичное представление термов, вместо символьного,что позволило резко снизить кол-во перебираемых пар. 1)Выписываются 0-кубы. 0000, 0001, 0011,0101,0110,0111,1000, 1001,1101,1111 2)0-ые кубы группируются по кол-ву 1 в них. 3) Склеивание 0-ых кубов в 1-ые кубы, только м/у соседними кубами, особое внимание на термы, которые не участвовали в склеивании- претенденты на ответ. В данном примере таких нет. 4).упорядочивание одномерных кубов по месту расположения x 5)Склеивание внутри 1-кубов. 011x не участвовал в склеивании 6).вычёркивание одной из двух одинаковых импликант 7).построение и заполнение таблицы для поиска минимального покрытия.По горизонтали выписываются все исходные нульмерные кубы в двоичной форме,а по вертикали-оставшиеся простейшие импликантыи и те импликанты,которые ни разу не участвовали в склеивании. Проверка:-не д.б. столбцов,не имеющих хотя однц метку; -каждая строка должна содерж точно 2k-клеток,гдк k-колич-во крестов в вертикальном первом столбце таблицы.8) вычеркивание столбцов, помеченных существенными импликантами. 8).поиск минимального покрытия начинается с поиска существенных импликант.Импликанта-терм,входящий в состав термов,образующих ф-ию.Существенная импликанта порождает единственную метку в столбце.Такая импликанта обязательно входит в окончательный ответ.Если присутсствуют несущественные импликанты(имеющие несколько меток в соответ столбцах),то в ответ войдут некоторые из них.Сама процедура выбора одной из нескольких несуществующих импликант наз поиском минимального покрытия,состоящая в вычёркивании столбцов,порождающие существенные импликанты. Выписываем ответ 011x +x00x+0xx1+1xx1 ___________________Вопрос 33____________________ Синтез комбинационных схем по не полностью определенным ФАЛ Если значения ф-и на нек-х наборах не заданы, то она называется не полностью определенной. Пусть дана ф-ия от n-переменных:f(x1,x2,…,xn). Если функция нк определена на n наборах, то ее можно доопределить 2^n наборов способами, доведя до определенной ф-й таких, что они будут совпадать с ф-ией f на всех определённых наборах Т.к. можно построить 2p различных эквивалентных ф-ий, то возникает задача, какую конкретно из них выбрать, чтобы её сложность была минимальной. Чаще всего такие задачи решаются с пом карт Карно. ___________________Вопрос 35____________________ Синтез комбинационных схем на дешифраторах и мультиплексорах Дешифратор - схема реализующая все конституенты единицы.ДШ имеет n входов и 2^n выходов. Синтез ДШ сводится к дизъюнктивному объединению необходимых выходов ДШ. Объединение дешифратора с помощью мультиплексора. Мультиплексор- схема с 1 выходом и 2мя группами входов: данных и адресными _____________________Вопрос 36____________________ Соединение автоматов: параллельное, последовательное. Параллельное: В результате получается автомат A=A1*A2 W=фи(W1*W2) -ф-я переходов - ф-я выходов., Рассмотрим 2 автомата, заданные таблицами переходов-выходов и функцию фи. Последовательное: При послед. соединении число выходов автом S1 и число входов авт S2 должны совпадать. Единственное отличие от парал соединения это функция выходов А=А1*А2 Z2=w1 и w=w2 _____________________Вопрос 37____________________ Соединение автоматов с обратной связью. Соединения с обратной связью: Хотя бы один должен быть автоматом Мура.
___________________Вопрос 38___________________ Синтез схем по временным булевым функциям(ВБФ) Работа реальных автоматов, происходит во времени, чтобы описать работу реальных автоматов вводят понятие автоматного времени. Вводит в себя последовательность временных интервалов на к-е разбито все время работы автомата. S- число интервалов. 0, 1…- длит. врем. интервалов. В течение каждого интервала, время считается остановившимся, и тогда логика работы автомата будет описываться только лог. переменными. Синтез: строим временную диаграмму. Сколько проводов, столько интервалов. Функцию представим в виде логических функций По уравнениям строим логическую схему, реализующую ВБФ. ___________________Вопрос 39____________________ Синтез и анализ последовательностных автоматов. РБФ - лог. ф-я, зависящая от текущих и от предшествующих значений ф-ци. Значения y(t+1) получаются задержкой сигнала y(t) на J тактов с помощью операторов задержки D. x-входные переменные, у- сигналы обратной связи. Пример, поступают только сигналы обратной связи. Задание РБФ всегда должно происходить с оговоренными начальными условиями. Пусть обратная связь осуществляется с задержкой на 1 такт, тогда: Схемы описываемые уравнениями и заданными нач. условиями, называются последовательностными автоматами. Чтобы провести анализ последовательностной схемы, необходимо: получить мат. модель По полученной математической модели, строим таблицу истинности по таблице истинности и начальным условиям строим таблицу переходов. выявляем наличие циклов Строим круговую диаграмму Выписываем циклы и тупиковые состояния Все состояния автомата должны быть проверены на тупиковые состояния, если имеется хотя бы 1 такое состояние, необходимо предусмотреть меры, обеспечивающие невозмножность попадание в него. ___________________Вопрос 43____________________ Определение абстрактного автомата. Автоматы Мура и Мили. Абстрактная теория изучает лишь переходы, к-е выполняет автомат под воздействием входных сигналов и те выходные сигналы, к-е он выдает. Не рассмат-я структуру автомата. Абстрактный автомат имеет один вход и один выход. Абстрактный автомат- мат. модель дискретного устройства, заданная: : S=(A,Z,W,сигма,лямда,а0) : 1. A={a1, a2, ... ,am} - множество состояний автомата 2. Z={z1, z2, ... ,zf} - множество входных сигналов 3. W={w1, w2, ..., wg} - множество выходных сигналов 4. сигма- функция переходов, показыв в какое сост аs перейдёт авт-т,находясь в сост am ,при входном сигнале zf . 5. лямда - функция выходов,показ. в какой выходной сигнал вырабатыв на выходе авт-та am под действием сигнала zf 6. a0 - начальное состояние автомата. Абстрактный автомат называется конечным, если конечны множества А = {a1, a2, ..., am}, Z = {z1, z2, ..., zf}, W = {w1, w2, ..., wg}. Автомат называется конечным, если множество его внутренних состояний, а также множества значений входных и выходных сигналов конечны. Конечный автомат в графическом представлении-это направленный граф,имеющий один начальный и один или несколько конечных узлов. В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата, причем в начальный момент t = 0 он всегда находится в начальном состоянии a(0)=a1. В момент t, будучи в состоянии a(t), автомат воспринимает сигнал z(t) на входном канале, и вырабатывает на выходном канале сигнал W(t)=лямда(a(t), z(t)) и в соответствии с функцией переходов перейдет в следующее состояние a(t+1)=сигма[a(t), z(t)] Распространенные Мили и Мура. Мили(1ый род R): Мура(2ой род S): Видно, что, в отличие от автомата Мили, выходной сигнал в автомате Мура зависит только от текущего состояния автомата и в явном виде не зависит от входного сигнала. Автомат Мура можно рассматривать как частный случай автомата Мили, имея в виду, что последовательность состояний выходов автомата Мили опережает на один такт последовательность состояний выходов автомата Мура, т.е различие между автоматами Мили и Мура состоит в том, что в автоматах Мили состояние выхода возникает одновременно с вызывающим его состоянием входа, а в автоматах Мура - с задержкой на один такт, т.к в автоматах Мура входные сигналы изменяют только состояние автомата. ___________________Вопрос 44____________________ Способы задания автоматов. Табличный метод: Мили задается двумя таблицами 1ая сигма, 2ая лямда. Часто эти две табл совмещ в одну и она наз совмещённой табл переходов-выходов: Поскольку в автоматах Мура выходной сигнал зависит только от состояния, он задается только одной таблицей. Графический метод: Задается в виде ориентированного графа, вершины которого соответствуют состояниям, а дуги - переходам между ними. Дуга, направленная из вершины am, задает переход в автомате из состояния am в состояние as. В начале этой дуги записывается входной сигнал Zf, вызывающий данный переход as=сигма(am,zf). Для графа автомата Мили выходной сигнал wg формируемый на переходе, записывается в конце дуги, а для автомата Мура - рядом с вершиной am, отмеченной состоянием am, в котором он формируется. Автоматы могут быть заданы с помощью матриц: Читается так, из состояния а0 в состояние а1 переходит под действием сигнала z1, при этом вырабатывается выходной сигнал w1. ___________Вопрос 45(совпадает с 21, читай выше)___________ ___________________Вопрос 47____________________ Элементарные автоматы RS-, D-, DV- триггеры. Триггер - устройство, имеющее 2 устойчивых состояния, в к-е он переходит под действием определенных входных сигналов. D-триггер – элемент задержки – имеет один информационный вход D и один выход Q и осуществляет задержку поступившего на его вход сигнала на один такт. Граф RS-триггер – триггер с раздельными входами.Данный триггер имеет два входных канала R и S и один выходной Q. Вход S (set) называется входом установки в единицу, вход R (reset) – входом установки в нуль. Граф, описывающий поведение RS триггера На основе графа может быть составлена таблица, в к-й указаны значения входов для осуществления всевозможных переходов триггера. DV- триггер ___________________Вопрос 48____________________ Элементарные автоматы JK-, T- триггеры. T триггер реализует ___________________Вопрос 49____________________ Реакции автомата Мили и Мура. Реакции автоматов Мили и Мура на входные сигналы имеют различное представление. Пусть цепочка выходных данных имеет вид: Z=z1z2z1z2z2 После окончания входной цепочки Мили находится в нек-м состоянии и выходной сигнал не вырабатывается, а в Мура находится в нек-м состоянии и вырабатывает выходной сигнал. Каждому автомату Мура можно поставить в соответствие Мили и наоборот. На примере видно, что реакции автоматов совпали. В Мура начальный выходной сигнал не учитывается. |