Лекції з теорії автоматів

ЛЕКЦІЇ 1.DOC (1 стор.)
Оригінал


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

Якщо всі стани автомата стійкі, то автомат наз-ся стійким.


VWV


W

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

Q (t +1)

q (t)



нехай <T

> T

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

RS-тригер стійкий тригер.


VZV




ZUU





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

з і py



x


p +





p _


сі-сигналізують сигнали;

Подвійна пам'ять дозволяє 100%-во позбутися гонок!


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

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

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

Приклад расспознователя: я-I, ти-You, ви-You ...

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

X
перетворювач
= {X1, x2, x3}; Y = {y1, y2, y3}




(1)





ZW


......

......

Будемо вважати, що символи є елементами алфавіту нашого перетворювача 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-внутрішній алфавіт.

Третій способи завдання МТ:

1) За допомогою функціональної схеми (таблиці рядки якої відзначені символами вхідного алфавіту). На перетині qi стовпця і Sj рядки записується трійка символів (Qi ', Sj', dk).

Приклад: Табл.1




q1

q2

...

qn

S1













S2




q7S8R







...













Sn













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

(Qi, Sj) (Qi ', Sj', dk);

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

S2 S5R


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)

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

З TCAS: Cхема, побудована на лот. елементах, які явл. кінцевими автоматами з одним станом наз-ся комбінаційної схемою.


Пам'ять

КС
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 = 0001 1001

Ризик небезпечний для елементів, які не повинні змінювати свій стан. В даному вище випадку помилковий сигнал-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. Синтез абстрактного автомата Мура по ДСА. Модель Уїлкса-Стрінджера.


Навчальний матеріал
© uadoc.zavantag.com
При копіюванні вкажіть посилання.
звернутися до адміністрації