ВОПРОСЫ К ЭКЗАМЕНУ ПО ТЕОРИИ АВТОМАТОВ. Вопросы к экзамену Строки. Префиксы, суффиксы, подстроки. Формальные языки

• Название: Вопросы к экзамену Строки. Префиксы, суффиксы, подстроки. Формальные языки
• Анкор: ВОПРОСЫ К ЭКЗАМЕНУ ПО ТЕОРИИ АВТОМАТОВ
• Дата: 10.01.2023
• Размер: 3.16 Mb.
• Имя файла: Voprosy_k_ekzamenu (2).docx
• Тип: Вопросы к экзамену; #879376
• страница: 4 из 4

Минимизация сложности комбинационных схем: аналитический метод, метод Карт Карно (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.м.б. группы,имеющие аналитическое,но не геометрическое соседство.Такие группы следует искать в симметричных относительно разделительной линии столбцах.

29. 
    Понятие базиса логических функций. Примеры
    

Примеры базисов. 

1. 
   Базис Буля: {∧, v, ¬}
   
2. 
   Базис Жегалкина: {1,⊕,&} 
   
3. 
   Конъюктивный базис: {&; −}
   
4. 
   Дизъюктивный базис: {+; −}
   
5. 
   Базис Вебба: {↓} 
   

6. 
   Базис Шеффера: {|}
   

7Сокращенный базис Буля (ИЛИ-НЕ)

8Универсальный базис Буля (И-НЕ)

30. 
    Минимизация сложности комбинационных схем: метод Квайна-Мак-Класски
    

Логические ф-ии м.б. представлены различным количеством переменных и знаком логических д-ий.Основная  идея минимизации сост в выполнении операции склеивания,в рез-те которой уменьшается кол-во термов и ранг полученных термов меньше ранга исходных.Термы,отлич-ся значением одной переменной,наз соседними.

Сначала метод был предложен Квайном,суть кот сост в том,что составлялась таблица,где в столбцах и строках перебирались все термы,входящие в минимизируемую функцию,представленную в виде СДНФ.Если некоторая пара склеивалась,то в соответствующую клетку таблицы вписывался рез-т склеивания.Результаты склеивания формировали вторую таблицу и т.д.Недостаток сост в том,что обработка происходила в символьных изображениях и была трудоёмка при большом колич-ве переменных.Мак-Класски ввёл двоичное представление термов, вместо символьного,что позволило резко снизить кол-во перебираемых пар.



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).построение и заполнение таблицы для поиска минимального покрытия.По горизонтали выписываются все исходные нульмерные кубы в двоичной форме,а по вертикали-оставшиеся простейшие импликантыи и те импликанты,которые ни разу не участвовали в склеивании.

Проверка:-не д.б. столбцов,не имеющих хотя однц метку; -каждая строка должна содерж точно 2^k-клеток,гдк 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 должны совпадать.

Единственное отличие от парал соединения это функция выходов А=А₁*А₂  Z₂=w₁ и w=w₂

_____________________Вопрос 37____________________

Соединение автоматов с обратной связью.

Соединения с обратной связью:



Хотя бы один должен быть автоматом Мура.

Если ав-т нах-ся в сост-ии а2,т.е.S1 в сост-ии а11, а S2 в сост-ии а22.S2 в сост-ии а22 выраб-т сигнал w2'кот-й поступает на 2й вход элемента γ. На 1й вход элем-а γ пост-т вход.сигнал из мн-ва z, пусть б/т z1, тогда по таблице γ находим что по z1 и w2'выраб-ся сиг-л р2, кот-й поступ-т на вход ав-та S1. По условию ав-т S1 нах-ся в сост-ии а11. под дейст-м р2 он переходит в а21, выраб-вая при этом w3",кот-й явл-ся одновременно и выходным сиг-м эквив-го ав-та и входным для S2. Ав-т S2, находясь по умолчанию в сост-ии а22 под дейс-м w3" переходит в а12. на этом реакция на дан.вход.сигнал заканч-ся. Окончательно из а2 под дейс-м z1 ав-т переходит в а3 с выроботкой w3".

___________________Вопрос 38___________________

Синтез схем по временным булевым функциям(ВБФ)

Работа реальных автоматов, происходит во времени, чтобы описать работу реальных автоматов вводят понятие автоматного времени. Вводит в себя последовательность временных интервалов на к-е разбито все время работы автомата. S- число интервалов. 0, 1…- длит. врем. интервалов. В течение каждого интервала, время считается остановившимся, и тогда логика работы автомата будет описываться только лог. переменными.



Синтез:

1. 
   строим временную диаграмму. Сколько проводов, столько интервалов.
   
2. 
   Функцию представим в виде логических функций
   
3. 
   По уравнениям строим логическую схему, реализующую ВБФ.
   

___________________Вопрос 39____________________

Синтез и анализ последовательностных автоматов.

РБФ - лог. ф-я, зависящая от текущих и от предшествующих значений ф-ци.



Значения y(t+1)  получаются задержкой сигнала y(t) на J тактов с помощью операторов задержки D. x-входные переменные, у- сигналы обратной связи. Пример, поступают только сигналы обратной связи.



Задание РБФ всегда должно происходить с оговоренными начальными условиями. Пусть обратная связь осуществляется с задержкой на 1 такт, тогда:



Схемы описываемые уравнениями и заданными нач. условиями, называются последовательностными автоматами.

Чтобы провести анализ последовательностной схемы, необходимо:

1. 
   получить мат. модель
   
2. 
   По полученной математической модели, строим таблицу истинности
   
3. 
   по таблице истинности и начальным условиям строим таблицу переходов.
   
4. 
   выявляем наличие циклов
   
5. 
   Строим круговую диаграмму
   
6. 
   Выписываем циклы  и тупиковые состояния
   

Все состояния автомата должны быть проверены на тупиковые состояния, если имеется хотя бы 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ая лямда.



Часто эти две табл совмещ в одну и она наз совмещённой табл переходов-выходов:



Поскольку в автоматах Мура выходной сигнал зависит только от состояния, он задается только одной таблицей.



Графический метод:

Задается в виде ориентированного графа,  вершины которого соответствуют состояниям, а дуги - переходам между ними. Дуга, направленная из вершины a_m, задает  переход  в автомате из состояния a_m в состояние a_s.  В начале этой дуги записывается входной сигнал Z_f,  вызывающий данный  переход a_s=сигма(a_m,z_f).  Для графа автомата Мили выходной сигнал w_g формируемый на переходе, записывается в конце дуги,  а  для  автомата  Мура - рядом с вершиной a_m, отмеченной состоянием a_m, в котором он формируется.

Автоматы могут быть заданы с помощью матриц:

Читается так, из состояния а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



После окончания входной цепочки Мили находится в нек-м состоянии и выходной сигнал не вырабатывается, а в Мура находится в нек-м состоянии и вырабатывает выходной сигнал. Каждому автомату Мура можно поставить в соответствие Мили и наоборот. На примере видно, что реакции автоматов совпали. В Мура начальный выходной сигнал не учитывается.