Теория автоматов. Ответы на вопросы экзамена. Теория автоматов ответы к экзамену. Вопросы к экзамену Строки. Префиксы, суффиксы, подстроки. Формальные языки

• Название: Вопросы к экзамену Строки. Префиксы, суффиксы, подстроки. Формальные языки
• Анкор: Теория автоматов. Ответы на вопросы экзамена
• Дата: 03.01.2023
• Размер: 4.63 Mb.
• Имя файла: Теория автоматов ответы к экзамену.docx
• Тип: Вопросы к экзамену; #871438
• страница: 3 из 4

_____________________Вопрос 24___________________

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

Задача синтеза: по заданному множ-ву входных переменных и по заданному множ-ву логических ф-ий построить цифровую схему,реализующую эту функцию. При этом необходимо учесть ограничения:синтезировать в заданном базисе,учесть ограничения по числу входов и выходов логических элементов,учесть ограничения на время и.т.д. При решении задач синтеза схем используют простейшую их классификацию:

1).схемы с несколькими входами и одним выходом. Задача сост в том,что логическую ф-ию нескольких переменных представляют в заданном базисе(штрих Шеффера или стрелка Пирса) с минимальной сложностью и с учётом ограничений на число входов и выходов.Задачу минимизации можно решить двумя способами:1.ф-ия минимизируется в булевом базисе,а рез-т преобразуется в требуемый базис.2.ф-ия сразу записывается в требуемый базис и минимизируется в нём.Т.к. для булова базиса наиболее широко разработаны методы преобразования и минимизации,а также исходные ф-ии чаще всего заданы именно в нём,то 1-ый способ используется чаще.

2).схемы с несколькими входами и несколькими выходами. Задача построения таких схем возникает в том случае,если требуется реализовать систему логических уравнений,причём кол-во выходов в схеме равно числу уравнений в системе,а кол-во входов определяется числом переменных,на которых построена данная система.Эту задачу можно решить двумя способами:

а).рассмотреть каждую ф-ию системы в отдельности и разработать схему,состоящую из k-отдельных схем,каждая из которых представляет собой схему с несколькими входами и одним выходом.k-число ф-ий в системе.Недостатком этого способа является то,что результируемая схема будет иметь большую избыточность,т.к. некоторые фрагменты отдельных схем могут повторяться.Достоинством метода является простота.

б).всю схему,реализующую систему логических выражений,можно представить в виде (n,k)-полюсника,где n-число входов, k-число выходов.При этом подходе учитываются внутренние взаимосвязи между ф-ями.В рез-те схемы получаются проще,но процедура синтеза сложне

____________________Вопрос 25____________________

Полнота переходов и полнота выходов автомата Мура.






____________________Вопрос 26____________________

Синтез комбинационных n,k полюсников

n-кол-во переменных, k-кол-во выходов схем.

2 способа решений:

1. 
   решается отдельно k задач без исп-я связей м/у уравнениями.
   
2. 
   решение сист. урав. с целью поиска повторяющихся аргументов. Решение сложное, но получается более простой ответ.
   

Пр-р

1 метод:



Минимизируем( Пi- картами карно)



ci - 6К и 3Д

Пi - 2К и 2Д

схема



2 метод:

Если предположить что Пi уже сформирован можно переписать в виде



ci - 3К и 3Д

Пi - 2К и 2Д Более простое решение

схема



Наиболее удобным для синтеза многовыходных схем яв-ся метод с применением карт Карно. Строится k карт Карно, во всех картах ищется одинаково помеченные клетки(ядро).

__

___________________Вопрос 27____________________

Элементарные автоматы.

В качестве ЭП используют элементарные авт-ты Мура,отвечающие условиям теоремы Глушкова (Система элементарных автоматов явл структурно полной тогда и только тогда,когда содержит:1)авт-ты Мура,облад полнотой переходов и выходов. 2).комбинацион схему,постороенную на функционал полной системе логических элементов. В этом случае задача структурного синтеза произвольных автоматов сводится к задаче структурного синтеза комбинационных схем).

В настоящее время-это триггеры. Триггер – это устройство, имеющее два устойчивых состояния(0,1), в которые он переходит под действием определённых входных сигналов.Обычно в триггерах выделяют два вида входных сигналов (и соответственно входов): информационные и синхросигналы.Информационные сигналы определяют новое состояние триггера и присутствуют в любых триггерах. Синхросигнал не является обязательным и вводится в триггерах с целью фиксации момента перехода триггера в новое состояние, задаваемое информационными входами. Обычно, при синтезе ЦА используются триггеры с синхровходом. На синхровход триггера поступают тактирующие импульсы задающего генератора, синхронизирующего работу ЦА. Период следования импульсов соответствует одному такту автоматного времени ЦА. Триггер имеет два выхода прямой и инверсный. Состояние триггера определяется по прямому выходу.

RS-триггер.Вход S (set) называется входом установки в единицу, вход R (reset) – входом установки в нуль.



Таблица функций выходов и условное обозначение:

На основании таблицы можно получить функцию возбуждения памяти автомата при синтезе на базе RS-триггеров. Например, если автомат переходит из состояния a_i= 010 в состояние a_j=110, то для обеспечения такого перехода функции возбуждения должны быть:

для первого триггера при переходе из 0 в 1 R₁ =0, S₁ = 1;

для второго триггера при переходе из 1 в 1 R₂ =0, S₂ = X;

для третьего триггера при переходе из 0 в 0 R₃ =X, S₃= 0.

Т-триггер.(триггер со счётным входом). Имеет один информационный вход Т и два выхода прямой и инверсный. Осуществляет суммирование по модулю два значений сигнала T и состояний Q и Q инверсноев заданный момент времени.

Таблица функций выходов и условное обозначение:

На основании этой таблицы можно получать функцию возбуждения элементов памяти при синтезе автомата на базе T-триггера. Например, если автомат перешел из состояния a_i = 010 в состояние a_j = 110, то для обеспечения этого перехода функции возбуждения должны быть:

для первого триггера при переходе из 0 в 1 T₁ = 1,

для второго триггера при переходе из 1 в 1 T₂ = 0,

для третьего триггера при переходе из 0 в 0 T₃ =0 .

D-триггер.(элемент задержки).Имеет один информационный вход D и два выхода прямой и инверсный, и осуществляет задержку поступившего на его вход сигнала на один такт.

Таблица функций выходов и условное обозначение:



На основании этой таблицы можно получать функцию возбуждения элементов памяти при синтезе автомата на базе D-триггера. Например, если автомат перешел из состояния a_i = 010 в состояние a_j = 110, то для обеспечения этого перехода функции возбуждения должны быть:

для первого триггера при переходе из 0 в 1 D₁ = 1,

для второго триггера при переходе из 1 в 1 D₂ = 1,

для третьего триггера при переходе из 0 в 0 D₃ =0 .

____________________Вопрос 28____________________

Минимизация сложности комбинационных схем: аналитический метод, метод Карт Карно (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____________________

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

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

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



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₂