Logo GenDocs.ru


Поиск по сайту:  


Лекции по теории автоматов - файл ЛЕКЦИИ~1.DOC


Лекции по теории автоматов
скачать (65.5 kb.)

Доступные файлы (1):

ЛЕКЦИИ~1.DOC292kb.09.01.2000 01:08скачать

содержание

ЛЕКЦИИ~1.DOC

Реклама MarketGid:

4Алгоритмические модели.


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

Типы алгоритмов:

1)Матем. Ф-ия(как алгор. Модель),рекурсивная ф-ия(Ф-ия, полученная из других ф-ий путём суперпозиций).

Операция суперпозиции- это подстановка в некоторую ф-ию, вместо её аргументов, значений других функций.

Пусть есть ф-ии: f(x1,x2,…,xm);

g1(x1,x2,…,xn);

g2(x1,x2,…,xn);

………………

gm(x1,x2,…,xn);



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

3)Преобразование слов в другие слова, заданные в конечном алфавите в другие слова, заданные либо в том же, либо в другом алфавите(конечный автомат). ]
^

5Машина Тьюринга.


Вычислитель подобен человеку, производящему большое кол-во операций и обладающий большим объёмом памяти. Вычислитель работает в дикр. времени (в каждый момент времени известно известно только, что будет производиться в следующий момент времени).

Структура МТ

МТ нах. в одном из множества состояний Q={q1,q2,q3,…,qn},это мн-во обозначает кол-во операций, которых может выполнять МТ.

Один из блоков МТ- Устройство Управления (УУ)- выполняя одну операцию оно нах. в одном состоянии, другую- в другом.

Q={q1,q2,q3,…,qn}-УУ

q1- начальное состояние;

qz- конечное состояние (Пассивное);

Состояния, отличные от qz- активные.

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

В МТ имеется устройство обращения к ленте, которое с помощью записывающей или считывающей головки обрабатывает ленту. В зависимости от того, в каком состоянии нах-ся МТ, и какой символ нах-ся в поле зрения головки, записывается в ячейку новый символ. Также имеется ф-ия dk={L,R,E}, показывающая направление( знак) сдвига.


10Основная гипотеза Тьюринга.

С помощью МТ можно произвести любое выч-е .

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


32Устойчивость автоматов.

Если на вход автомата поступают сигналы из алфавита z={z1,z2,…,zn}, то в этом автомате устойчивым состоянием наз-ся состояние ak, в кот-е автомат переходит под действием сигналов отличных от zk.Состояния ak изображаются так:




zk




zk

Если все состояния автомата устойчивы, то автомат наз-ся устойчивым.


V W V


W

Триггер типа Т-не устойчивый автомат, т.е. на вх. Присутствует сигнал W ,то он будет менять своё состояние непредсказуемо.

Q(t+1)

q(t)



пусть <t

>t

Вывод:триггер T- очень чувствителен к задержки.

RS-триггер устойчивый триггер.


V Z V




Z U U





Q(t+1)

q(t)




Так как RS триггер не зависит от длительности входного сигнала, то элемент задержки не нужен.
^

33Состязания и гонки конечных автоматов.





Q1 Q2 Qn


………


q1 q2 q3


Особенности:

1)Разная длина линий комбинационной схемы, вызывающее неодинаковое поступление ф-ией возбуждения на входы.

2)Разное время срабатывания каждого из триггеров блока памяти.

Структурный автомат у которого изм. состояний его элементов памяти происходит в момент поступления на вход ф-ии возбуждения назыв. асинхронным автоматом.Фрагмент графа асинхронного автомата:

Zk


Zk


Km=1 0 1 1

Q1Q2Q3Q4

T1T2 T3 T4

T1 быстрее T2 =>=0011-ложный код;

T2 быстрее T1 =>=1111-ложный код;

Ситуации, когда из-за неодновременного срабатывания триггеров, вызванного выше указанными причинами автомат отказывается в непредусмотренные состояния al вместо as и под действием присутствующего на входе сигнала Zk переходит в новое состояние, наз. cсостязаниями.

Состязания:

1)Критические (гонки)- состязания, когда из непредусмотренного состояния мы переходим далее по графу и не попадаем в состояние as.

2)Не критические –состязания, в результате которых автомат всё таки оказывается в нужном состоянии as после изменения состояния последнего из самых медленных триггеров.

Меры по устранению гонок в структурном автомате.

1)Направленное кодирование состояний абстрактного автомата(Превращение критических состояний в некритические).

Способы превращения:

a)Не исп-ть ложные коды для кодирования состояния.

b)Ложными кодами кодировать из которых по сигналу Zk переход был бы в состояние as.

c)Ложными кодами кодировать состояния, устойчивые относительно Zk.

Во всех этих ситуациях увеличение аппаратных затрат из-за ув. рразрядности кода, которое оказывается неизбежным.

2) Cоседние кодирование соседних состояний.

Соседними состояниями наз-ся сост-я соединённые между собой дугами. Соседними кодами наз коды у кот-ых расстояние по Хэммингу(tms=1) .Расстоянием по Хэммингу между двумя разрывными кодами наз-ся число, отличающееся друг от друга разрядов кода.Такое кодирование обычно влечёт за собой избыточность разрядности кодов и все вышеизложенные проблемы.

3)Синхронизация структурного автомата.




Q1 Q2


q1 q2


Cn-Вентель

(Коньюнктор)

Автомат, в кот-ом время срабатывания триггеров определяется моментом поступления синхронизирующих импульсов называется синхронизирующим. В такой схеме очень жёсткие требования к моменту поступления и длительности сигнала. Их цель- исключить не одновременность срабатывания триггеров из-за разной длины линии в комбинационной схеме.Использование такой не даёт 100%-ное избавление от гонок.

4)Двойная память.




T

си

р

Q


y

си p y



x


p +





p _


си- сигнализирующие сигналы;

Двойная память позволяет 100% -но избавиться от гонок!


14Абстрактный автомат и способы его задания.

Автоматы: 1)расспознователи (опр. принадлежит ли подмножество поданных на вход сигналов заданному мн-ву слов).

2)преобразователи;(Преобразуют исходное мн-во входн. слов, записанных в конечном автомате в мн-во выходн. Слов представленных либо в том же, либо в другом конечном автомате.

Пример расспознователя: я- I,ты- You,вы- You…

Арифм оператор –правило по кот. Производиться отображение слов, заданных в другом алфавите. Каждый символ любого слова поступает в определённый момент времени t={t1,t2,…,tn}. Каждый входной символ опред-ся не только тем, входным символом ,в данный момент времени t, но и всеми символами, которые поступили ранее=>преобразователь должен обладать памятью.Преобразователь инф-ии, способный воспринимать входные сигналы, вызывать соответствующие им вых. сигналы, наз-ся автоматом. Если число состояний автомата конечно, то такой автомат наз-ся конечным.конечные автоматы бывают структурными и абстрактными.

X
преобразователь
={x1,x2,x3};Y={y1,y2,y3}




(1)





Z W


……

……

Будем считать, что символы являются элементами алфавита нашего преобразователя Z={,,,…,}.Аналогичную процедуру можно произвести выходными символами

……

W={,,,…,}.

Эта мат модель и есть абстрактный автомат, т.к. она не зависит от конкретной технической реализации. (1)-структурный автомат :конкретное устройство, реализованное в заданном элементарном базисе.

Абстрактный автомат описывается 6-ю параметрами:

S={Z,W,A,};

Z={,,,…,}.

W={,,,…,}.

A={,,,…,}.

-начальное состояние;

-ф-ия входов;

-ф-ия выходов;

В зависимости от ф-ий выходов и переходов различают два типа автоматов:

Автомат первого рода (Мили)



Автомат второго рода (Мура)



Правильный автомат второго рода (Мура)



Входные сигналы зависят только от того состояния, в которое автомат переходит, не зависит от того, каким путём.

6Детерминированность и способы задания МТ.

Совокупность операций dk={L,R,E} наз-ся действием (шагом МТ). Под детерминированностью понимается фиксация нового состояния и нового символа МТ в процессе вып-я каждого элементарного действия. И новый символ и новое состояние опр-ся с помощью логической ф-ии. Лог. ф-ией МТ ставит в соответствие паре параметров qi Sj тройку параметров (Sj’,qi’,dk).Мн-во A={l,R,E,q1,q2,…,qn} наз-ся внутренним алфавитом МТ, мн-во S-внутренний алфавит.

3-и способа задания МТ:

1)С помощью функциональной схемы (таблицы строки которой отмечены символами входного алфавита).На пересечении qi столбца и Sj строки записывается тройка символов (qi’,Sj’,dk).

Пример: Табл.1




q1

q2



qn

S1













S2




q7S8R





















Sn













2)Система Тьюринговых команд вида:

(qi,Sj)(qi’,Sj’,dk);

3)Описание в виде графа, в узлах которого записываются состояния перехода, а на рёбрах, обозначающих переход- выр-е: SjSj’dk.Тогда граф заданный в табл1 будет выглядеть так:

S2S5R


8Конфигурация МТ.

Конфигурацией МТ наз-ся совокупность её след. характеристик: внутреннее состояние МТ, слова, записанного на ленте и положения считывающей головки.

Обозн. конфиг.:Ki=qi ,где qi-сост-е МТ;-посл-ть символов располженных в ячейках слева от головки. -слово, первый символ кот-ого является обозреваемым,а остальные распологаются справа от головки.

21Канонический метод структурного синтеза конечного автомата.

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

Этапы структурного синтеза

^ Автомат Мили

A={a1,a2,a3,a4,a5};

Z={z1,z2,z3};

W={w1,w2};

Таблица переходов- двумерная таблица, строки которой отмечены входными сигналами, а столбцы- состояниями.(можно и наоборот).На пересечении i-той строки и j-того столбца записывается состояние автомата aij, в которое он переходит из состояния aj под действием сигнала Zj ;Таблица выходов - аналогично, но таблица переходов на пересечении строки и столбца – выходные сигналы.




a1

a2

a3

a4

Z1

a2

a1

a4

-

Z2

-

a3

a2

a3

Z3

a3

-

a1

a1







a1

a2

a3

a4

Z1

W1

W2

W2

-

Z2

-

W1

W1

W2

Z3

W1

-

W1

W2

В совмещённой таблице переходов – выходов на пересечении i-ой строки и j-того столбца записывается:aij/wis

Автомат Мура

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

A={a1,a2,a3,a4,a5};

Z={z1,z2,z3};

W={w1,w2};




W1

W2

W1




a1

a2

a3

Z1

a2

a1

a2

Z2

a3

-

a3

Z3

-

a3

a1


20Теорема Глушкова.Обобщённая схема структурного автомата.

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

Автомат мура обладает полной системой переходов, если для любой пары состояний (ai,aj) найдётся входной сигнал, переводящий один элемент пары в другой, включая случай, когда i=j.

Пример (рис1)

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

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


Память

КС
q(t+1) y(t)







x(t)- структурный входной сигнал.(Векторный)

y(t)- структурный выходной сигнал.(Векторный)

X={x1,x2,…,xn}

Y={y1,y2,…,yn}

Q={q1,q2,…,qm},где m-число элементов памяти.

Элементы памяти- автоматы мура с полной системой переходов и выходов.

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

22Графический метод задания.

Граф перходов представляет собой ориентированный связный граф.В вершинах которого состояния (Мили) или состояния и соответствующие выходные сигналы(Мура).На рёбрах записываются входные сигналы, вызывающиесоотвующий переход (Мура) или входные и выходные сигналы, соответствующие этому переходу(Мили).

Замечания:

1)Связность графа переходов означает, что все состояния достижимы.

2)Автомат у которого для некоторой пары (ai,zi) отсутствует переход, наз-ся частичным автоматом ,у него в таблице переходов – выходов имеются прочерки.Иначе, автомат полностью определён.

3)У полностью определённого автомата из каждого узла графа перехода должно выходить число дуг, равное кол-ву символов входного алфавита.

4)Все рассмотренные автоматы должны быть детерминированы, т.е. для них недопустимы переходы в различные состояния из одного и того же состояния под действием одинаковых входных сигналов.

z1







z2

недопустимо


35Риск в асинхронных автоматах.

Возникает если лог. выр-е ф-ий возбужд. этого автомата содержит одновременно и прямое и инверсное значение какой- либо переменной.Пример:

Причины неправильного срабатывания:

1)Не одновременность появления единичного и нулевого сигналов на входах триггера (прямой и инверсный). В результате оказывается, что на прямом и инверсном выходах в какой-то момент оказываются равными (Из-за неодинаковой задержки на триггере).



Q





Наличие задержки на лог. элементах из-за которой прямой и инверсный сигналы вырабатываются не одновременно, когда используется элемент НЕ”. В результате прямой и инверсный сигналы сливаются.

x




()








T2=00011001

Риск опасе для элементов, которые не должны менять своё состояние. В данном выше случае ложный сигнал-1.Тоже самое наблюдается и при

Такие ситуации наз-ся статическим риском в 1 или нуле. Глушков доказал, что СДНФ булевой ф-ии свободна от любого риска по всем переменным.

Меры по устранению риска-ф-ия задана в мин. ддизъюнктивной норм. форме .Если ф-ия образованна на элементах Не И”( элемент Шифера)-риск в 1. Если ф-ия образованна на элементах Не Или” ( элемент Пирса)-риск в 0.

1)Н-ти знач-я наборов аргументов, при которых ф-ия остаётся постоянной при изменении анализируемого элемента c 0 на 1 и с 1 на 0, остальные элементы не меняются


N

x

y

z

f

0

0

0

0

0

1

0

0

1

1

2

0

1

0

0

3

0

1

1

1

4

1

0

0

0

5

1

0

1

0

6

1

1

0

1

7

1

1

1

1

Ф-ия не зависит от x на наборах:(0,4),(3,7)


N

x

y

z

f

0

0

0

0

0

3

0

1

1

1

4

1

0

0

0

7

1

1

1

1

3)Необходимо н-ти лог выр-е ф-ии ,в которой принять



4)Определить знач-я ф-ии на выбранных наборах аргументов.

N

x

y

z

f



0

0

0

0

0

0-риска нет

3

0

1

1

1

0-риска нет

4

1

0

0

0

0-единичн риск

7

1

1

1

1

1

5)Сравнить знач-я ф-ии f и на выбранных наборах. Чтобы избавиться от риска, необходимо записать вместо минимальной ДНФ, сокращённую ДНФ.В сокращённой Днф присутствуют лишние импликанты.









1




1




1

1


Лишняя импликанта



6)Проверяем знач-е и на тех же наборах.

N

x

y

z

f





0

0

0

0

0

0

0

3

0

1

1

1

0

0

4

1

0

0

0

0

1

7

1

1

1

1

1

1

Поэтому для того чтобы гарантировать не отказ схемы необходимо когда встречаются и прямые и инверсные выр-я записать в Сокращённой ДНФ добавив лишнюю импликанту.

36Определение ГСА, ф-ии переходов и пути в ГСА.Матричные схемы алгоритмов.

В условной вершине записывается знач-е осведомительных сигналов.

1)Первый этап синтеза- кодирование содержательной ГСА:каждая микрооперация представленная в ГСА кодируется и ставиться в соответствие какому-то устройству.

2)Осведомительные сигналы или их содержания находящиеся в ГСА ,кодируются в -мн-во логических условий.Результатом такого кодирования получается ГСА.

Особенности ГСА:

В каждой ГСА, между любыми операторными вершинами исуществует путь вида:



- отметка условной вершины.




,если -отмечено 1-ей,

то можно записать

-ф-ия перехода в пути от к.



В каждый момент автоматного времени значения лог операций может меняться ,и если это происходит, то ход вып-я задачи может быть различен ,тогда вводят понятие значение ГСА на лог. усл..

Пусть даны 5 лог условий:




X1

X2

X3

X4

X5




t1

1

1

0

1

1



t2

1

0

1

0

0



t3

0

1

1

0

0



t4

1

1

1

1

1



Н-ти значения ГСА для данной последовательности логических условий.

В каждый момент автоматного времени сущ. тот путь между двумя вершинами ф-ия переходов которого равна 1и этот путь всегда должен быть единственным :

t1:





=>

t2:



=>следующая вершина

t3:





Значение ГСА на данной последовательности лог. условий .

Матричная схема алгоритма.(МСА)

МСА-таблица, строки которой помечены Y0,Y1,Y2,…,Yk. На пересечении строк и столбцов записаны логические условия.

Пример:на пересечении Yi и Yj записываются ф-ии переходов, определённые на соответствующем пути.




Y1

Y2

Y3

Y4

Y5

Yk

Y0

X1














Y1









X3







Y2












X4

X3X5

Y3










X3







Y4















X5

Y5
















1



^ ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ ПО КУРСУ ТЕОРИЯ АВТОМАТОВ

1. Кибернетика как наука. Предмет исследования и методы исследования кибернетики.

2. Понятие алгоритма. Требования, предъявляемые к алгоритмам.

3. Блок-схемы алгоритмов, композиция алгоритмов.

4. Алгоритмические модели.

5. Машина Тьюринга и ее структура.

6. Детерминированность и способы задания машины Тьюринга.

7. Алгоритм работы машины Тьюринга.

8. Конфигурация машины Тьюринга.

9. Тьюрингово вычисление (операция «Сложение»)

10. Основная гипотеза теории алгоритмов (Тезис Тьюринга).

11. Непрерывная и дискретная формы представления информации. Дискретное время. Алфавит.

12. Понятие о конечном автомате. Автоматы Мили и Мура.

13. Эквивалентные автоматы Мили и Мура.

14. Абстрактный автомат и способы его задания.

15. Алфавитный и автоматный операторы соответствия.

16. Синтез абстрактного автомата Мили по оператору соответствия.

17. Синтез абстрактного автомата Мура по оператору соответствия.

18. Минимизация абстрактного автомата по графу переходов.

19. Композиция автоматов. Условия корректности построения структурных схем автоматов.

20. Теорема Глушкова. Обобщенная схема структурного автомата.

21. Канонический метод структурного синтеза конечного автомата (табличный)

22. Графический метод структурного синтеза конечного автомата.

23. Элементарные автоматы. Т-триггер, его характеристическое уравнение. Матрица переходов.

24. Элементарные автоматы. D-триггер, его характеристическое уравнение. Матрица переходов.

25. Элементарные автоматы. RS-триггер, его характеристическое уравнение. Матрица переходов.

26. Элементарные автоматы. JK-триггер, его характеристическое уравнение. Матрица переходов.

27. Элементарные автоматы. DV-триггер, его характеристическое уравнение. Матрица переходов.

28. Элементарные автоматы. S-триггер, его характеристическое уравнение. Матрица переходов.

29. Элементарные автоматы. R-триггер, его характеристическое уравнение. Матрица переходов.

30. Элементарные автоматы. Е - триггер, его характеристическое уравнение. Матрица переходов.

31. Элементарные автоматы. RST-триггер, его характеристическое уравнение. Матрица переходов.

32. Устойчивость автоматов, устойчивые и неустойчивые триггеры.

33. Гонки в автоматах и методы их устранения. Синхронные и асинхронные автоматы.

34. Техническая реализация RS-триггера. MS-триггер.

35. Риск в асинхронных автоматах.

36. Определение ГСА, функции переходов и пути в ГСА. Матричные схемы алгоритмов.

37. Синтез абстрактного автомата Мили по ГСА. Модель Уилкса-Стринджера.

38. Синтез абстрактного автомата Мура по ГСА. Модель Уилкса-Стринджера.



Реклама:





Скачать файл (65.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru
Разработка сайта — Веб студия Адаманов