Теорія автоматів є розділом дискретної математики, що вивчає моделі перетворювачів дискретної інформації. Такими перетворювачами є як реальні пристрої (комп'ютери, живі організми), і уявні пристрої (аксіоматичні теорії, математичні машини). Насправді кінцевий автомат можна охарактеризувати як пристрій М , Що має вхідний і вихідний канали при цьому кожен з дискретних моментів часу, званих тактовими моментами, воно знаходиться в одному з кінцевих станів.

По вхідному каналу в кожний момент часу t =1, 2, ... пристрій М надходять вхідні сигнали (з деякої кінцевої множини сигналів). Задається закон зміни стану до наступного моменту часу в залежності від вхідного сигналу та стану пристрою у поточний момент часу. Вихідний сигнал залежить від стану та вхідного сигналу у поточний момент часу (рис. 1).

Кінцевий автомат є математичною моделлю реальних дискретних пристроїв із переробки інформації.

Кінцевим автоматом називається система А = (X , Q , Y ,  ,  ), де X , Q , Y - довільні непусті кінцеві множини, а  і   функції, з яких:

безліч X ={a 1 , ..., a m ) називається вхідним алфавітом , а його елементи - вхідними сигналами , їх послідовності - в хідними словами ;

безліч Q ={q 1 , ..., q n ) називається безліччю станів автомата, а його елементи - станами ;

безліч Y ={b 1 , ..., b p ) називається вихідним алфавітом , його елементи - вихідними сигналами , їх послідовності - вихідними словами ;

функція  : X  Q Q називається функцією переходів ;

функція  :X  Q Y називається функцією виходів .

Таким чином,  (x , q )Q ,  (x , q )Y для  x X , q Q .

З кінцевим автоматом асоціюється уявний пристрій, який працює в такий спосіб. Воно може бути в стані з безлічі Q , сприймати сигнали з множини X і видавати сигнали з множини Y .

2. Способи завдання кінцевого автомата

Існує кілька еквівалентних способів завдання абстрактних автоматів, серед яких можна назвати три: табличний , геометричний і функціональний .

2.1.Таблічне завдання автомата

З визначення автомата слід, що його можна задати таблицею з двома входами, що містить т рядків та п стовпців, де на перетині стовпця q та рядки а стоять значення функцій  (a i , q j ),  (a i , q j ).

q a	q 1		q j		q n
a 1	(a 1 , q 1),  (a 1 , q 1)		(a 1 , q j ),  (a 1 , q j )		(a 1 , q n ),  (a 1 , q n )
a i	(a i , q 1),  (a i , q 1)		(a i , q j ),  (a i , q j )		(a i , q n ),  (a i , q n )
a m	(a m , q 1),  (a m , q 1)		(a m , q j ),  (a m , q j )		(a m , q n ),  (a m , q n )

2.2. Завдання автомата діаграмою Мура

Інший спосіб завдання кінцевого автомата – графічний, тобто за допомогою графа. Автомат зображується як позначеного орієнтованого графа Г(Q , D ) з безліччю вершин Q і безліччю дуг D ={(q j ,  (a i , q j ))| q j Q , a i X ), при цьому дуга ( q j ,  (a i , q j )) позначається парою ( a i ,  (a i , q j )). Таким чином, при цьому способі стану автомата зображують кружками, які вписують символи станів q j (j = 1, …, n ). З кожного гуртка проводиться т стрілок (орієнтованих ребер) взаємно-однозначно відповідних символам вхідного алфавіту X ={a 1 , ..., a m ). Стрілці, що відповідає літері a i X і виходить із гуртка q j Q , приписується пара ( a i ,  (a i , q j )), причому ця стрілка веде до гуртка, відповідного  (a i , q j ).

Отриманий малюнок називається графом автомата або, діаграмою Мура . Для не дуже складних автоматів цей спосіб наочніший, ніж табличний.

Основні визначення n Кінцевим автоматом називається система M = (А, B, S, y), в якій n n n А = (а 1, . . . , am) – кінцевий вхідний алфавіт, B = (b 1, . . , bk ) - кінцевий вихідний алфавіт, S = (s 1, . . . , sn) - кінцевий алфавіт станів, : А S S - функція переходів, y: А S B - функція виходів. n Якщо в автоматі M виділено один стан, званий початковим (зазвичай буде вважатися, що це s 1), то отриманий автомат називається ініціальним і позначається (M, s 1). n Існує два способи завдання автомата: Автоматна таблиця, діаграма переходів

Автоматна таблиця n 1) 2) 3) 4) Приклад: задати автомат для читання слова "001", якщо на вхід подаються символи "0" і "1". Вхідний алфавіт A = (0, 1) Вихідний алфавіт A = (Y, N) Алфавіт станів S = (s 0 "", s 1 "0", s 2 "00" s 3 "001") Автоматна таблиця двома способами. задається 1) Рядки – стану автомата. Стовпчики – вхідні символи. На перетині рядків і стовпців вказуються функції y. 2) S, A, y задаються по шпальтах. Упр 25 Побудувати автомат для пошуку слова КАКАДУ SA 0 1 S 0 S 1, N S 0, N S 1 "0" S 2, N S 0, N S 2 "00" S 2, N S 3, Y S 3 "001" S 1 , N S 0, N S Вх y S 0 0 S 1 N 1 S 0 N 0 S 2 N 1 S 3 Y 0 S 1 N 1 S 0 N S 1 S 2 S 3

Діаграма переходів n Орієнтований графом, що називається діаграмою переходів мультиграф, переходів або графа відповідають станам. Якщо (Si, aj) = Sk, y (Si, aj) = bl, то з вершини Si у вершину Sk ведена дуга на якій написано (aj, bl) n У кожній вершині si умовами коректності: 0 1 S 0 «» S 1, N S 0, N S 1 "0" n Вершини, y S 2, N S 0, N S 2 "00" S 2, N S 3, Y S 3 "001" S 1, N S 0, N 1, N виконані 1) для будь-який вхідний літери aj є дуга, яка виходить з si, де написано aj (умова повноти); 2) будь-яка буква aj, зустрічається тільки на одному ребрі, що виходить із si (умова несуперечності або детермінованості) S 0 S 1 (0, N) (1, N) (0, N) (1, N) S 2 (1, Y) S 3

Автомати та вхідні слова n Для цього автомата M його функції M та y. M можуть бути визначені не тільки на множині всіх вхідних літер, але і на множині А * всіх вхідних слів. n Для будь-якого вхідного слова = aj 1 aj 2. . . ajk (si, aj 1 aj 2. . . ajk) = ((… (si, aj 1), aj 2), . . . , ajk-1), ajk). y (si, aj 1 aj 2. . . ajk) = y((… (si, aj 1), aj 2), . . . , ajk-1), ajk).

Приклад: Автомати та вхідні слова Приклад: = 0101 (S 1, 0101) = ((S 1, 0), 1) (S 1, 0101) = (((S 2, 1), 0), 1) (S 1, 0101) = ((S 3, 0), 1) (S 1, 0101) = (S 1, 1) (S 1, 0101) = S 0 0 1 S 0 «» S 1, N S 0, N S 1 "0" S 2, N S 0, N S 2 "00" y(S 1, 0101) = y((((S 1, 0), 1) y(S 1, 0101) = y(((S 2 , 1), 0), 1) y(S 1, 0101) = y((S 3, 0), 1) y(S 1, 0101) = y(S 1, 1) y(S 1, 0101) = N , y S 2, N S 3, Y S 3 "001" S 1, N S 0, N

Автоматне відображення n Зафіксуємо M початковий стан S 0 і кожному вхідному слову = a 1 a 2. . . ak поставимо у відповідність слово у вихідному алфавіті: = y(S 0, a 1) y(S 0, a 1 a 2). . . y(S 0, a 1. . . ak). (3 a) n Ця відповідність, що відображає вхідні слова у вихідні слова, відображенням називається автоматним n Якщо результатом застосування оператора до слова є вихідне слово, то це будемо позначати відповідно M() = .

Приклад: Автоматне відображення Вхідному слову = 0101 поставимо у відповідність слово у вихідному алфавіті: = y(S0,0) y(S0,01)y(S0,0101). y (S 0, 0) = N , y 0 S 0 "S 1, N S 0, N S 1 "0" S 2, N S 0, N S 2 "00" S 2, N S 3, Y 1 S 3 "001 » S 1, N S 0, N y(S 0, 01) = y((S 0, 0), 1) = y(S 1, 1) = N y(S 0, 010) = y(((S 0, 0), 1), 0) = y((S 1, 1), 0) = y(S 0, 0)=N y(S 0, 0101) = y((((S 0, 0) , 1) =y(((S 1, 1), 0), 1) = = y((S 0, 0), 1) = y(S 0, 1) = NNNN

Властивості автоматного відображення 1) слова = M() мають однакову довжину: | | = | | (Властивість збереження довжини); 2) якщо = 12 і M(12) = 12, де | 1| = | 1|, то M(1) = 1; інакше кажучи, образ відрізка довжини і дорівнює відрізку образу тієї ж довжини.

Види автоматів n Загальна модель кінцевого автомата (S-звичайно), яка розглядалася раніше, називається автоматом Милі. n Автомат називається автономним, якщо його вхідний алфавіт складається з однієї літери: А = (а). Усі вхідні слова автономного автомата мають вигляд аа. . . а. n Кінцевий автомат називається автоматом Мура, якщо його функція виходів залежить лише від станів, тобто для будь-яких s, ai, aj y (s, ai) = y (s, aj). Функція виходів автомата Мура звичайно одноаргументна; зазвичай її позначають буквою і називають функцією позначок. У графі автомата Мура вихід пишеться не так на ребрах, а при вершині.

Автомати Мура Теорема: Для будь-якого автомата Мілі існує еквівалентний йому автомат Мура. n При дослідженні можливостей автоматів достатньо користуватися автоматами Мура. Це зручно тому, що автомат Мура можна розглядати як автомат без виходів, стан якого різним чином відзначений.

Приклад автономного автомата SA а S 1 S 3, 0 S 2 S 4, 0 S 3 S 4, 0 S 4 S 7, 0 S 5 S 4, 2 S 6 S 5, 0 S 7 S 6, 1 S 8 S 9, 0 S 9, 1 S S S S S A = (a), B = (0, 1, 2), S = (S 1, S 2, S 3, S 4, S 5, S 6, S 7, S 8, S 9)

Невідмінні стани n Нехай M і Т - два автомати з однаковими вхідними та вихідними алфавітами. Стан s автомата M і стан r автомата Т називаються невідмінними, якщо будь-якого вхідного слова M(s,) = T(r,). n Автомати M і Т називаються невідмінними, якщо для будь-якого стану s автомата M знайдеться стан, що не відрізняється від нього, r автомата Т і, навпаки, для будь-якого r з Т знайдеться невідмінний від нього s з M. n Невідмінні стани називаються еквівалентними

Мінімальний автомат n Перехід від автомата M до еквівалентного автомата називається еквівалентним перетворенням автомата M. n Можна ставити різні завдання про пошук автоматів, еквівалентних даному і які мають задані властивості. Найбільш вивченою серед таких завдань є задача про мінімізацію числа станів автомата: серед автоматів, еквівалентних M, знайти автомат із найменшою кількістю станів – мінімальний автомат.

Аспекти «роботи» автоматів n Можна виділити два основних аспекти «роботи» автоматів: 1) автомати розпізнають вхідні слова, тобто відповідають на запитання, чи належить подане на вхід слово даній множині (це автомати розпізнавачі); 2) автомати перетворять вхідні слова у вихідні, тобто реалізують автоматні відображення (автомати-перетворювачі).

ТА в рамках метаматематики n Предмет теорії алгоритмів і формальних систем у рамках метаматематики - які об'єкти та дії над ними слід вважати точно певними, якими властивостями та можливостями мають комбінації елементарних дій, що можна і чого не можна зробити за їх допомогою. n Головний додаток теорії алгоритмів - доказ неможливості алгоритмічного (тобто точного та однозначного) вирішення деяких математичних проблем.

Алгоритм n Алгоритм - припис, що однозначно задає процес перетворення вихідних даних до необхідного результату n Сам процес перетворення складається з елементарних дискретних кроків, застосування яких кінцевого числа разів призводить до результату

Основні типи алгоритмів Теорія алгоритмів – це метатеорія, що вивчає різні (якісні та кількісні) властивості алгоритмів. n Для дослідження якісних властивостей визначено 3 основні типи алгоритмів: 1) Рекурсивні функції 2) Машина Тьюринга 3) Канонічні системи Посту та нормальні алгоритми Маркова.

Найпростіші рекурсивні функції n S 1(x) = x+1 - функція залежить від однієї змінної х і дорівнює х+1. n On(x 1…xn) =0 - функція залежить від n змінних і завжди дорівнює 0. n Imn(x 1…xn) = xm - функція залежить від n змінних і завжди дорівнює значенню змінної xm

Примітивна рекурсія n Функція f(x 1…xn+1) одержувана алгоритмом примітивної рекурсії з функцій g(x 1…xn) та h(x 1…xn+2), якщо f(x 1, …xn, 0) = g (x 1, …xn) (1) f(x 1, …xn, y+1) = h(z), де z=f(x 1, …xn, y) (2) Функція f називається примітивно-рекурсивною якщо її можна отримати з найпростіших функцій S 1, On, Imn кінцевим числом операцій суперпозиції та примітивної рекурсії.

Приклад n Для доказу того, що функція є примітивно рекурсивною необхідно: 1) Відповідно до рівнянь (1) та (2) у явному вигляді визначити функції g() та h(). 2) Показати, що g() і h() є найпростішими функції S 1, On, Imn або доведеними раніше примітивно рекурсивні функції. Упр 26: Довести, що функція f(x, y) = x+y є примітивно рекурсивною Теза Черча: Клас алгоритмічно обчислюваних числових функцій збігається з класом усіх рекурсивних функцій.

Машина Тьюринга Машина Тьюринга містить: n 1) Зовнішню пам'ять – стрічку з n осередків. Кожна перша комірка знаходиться в стані аi. Задано алфавіт станів. Стрічка може бути нескінченною в обох напрямках. Порожні стани опускаються. n 2) Внутрішню пам'ять машини – пристрій у поточний час перебуває у стані qi. Задано алфавіт внутрішнього стану. Початковий стан q1, заключний q0 або qz. n 3) Покажчик – вказує на поточну комірку та переміщається вздовж стрічки. n 4) Керуючий пристрій – зчитує символ комірки, яку вказує покажчик. Відповідно до програми змінює стан комірки та переміщає покажчик.

Стан та програма МТ n Стан машини Тьюринга називається слово n n n n a 1…ak-1 qi ak…ar , утворене вставкою символу внутрішнього стану перед осередком, що оглядається. Програма машини Тьюринга – сукупність команд, які може виконати машина qi aj qi' aj' D, де qi - внутрішній стан машини aj - стан оглядового комірки qi' - новий стан машини aj' - новий символ записується в оглядову комірку D = ( L, R, E) – символи, що символізують зсув покажчика на одну комірку вліво, вправо та відсутність зсуву відповідно.

Приклад МТ Упр 27: Знайти кінцевий стан машини Тьюринга Початковий алфавіт: А = (0, 1) Алфавіт внутрішнього стану: Q = (q 0, q 1, q 2) Програма: ( 1) q 10 q 20 R, 2)q 20 q 01 E, 3) q 11 R, 4) q 21 R ) Початкове слово: q 111

Приклад МТ Упр 28 Знайти кінцевий стан машини Тьюринга Початковий алфавіт: А = (0, 1, ) Алфавіт внутрішнього стану: Q = (q 0, q 1, q 2, q 3) Програма: ( 1) q 1 q 00 R, 2) q 11 q 20 R, 3) q 21 R, 4) q 2 q 31 L, 5) q 30 q 00 R, 6) q 31 L ) А) Початкове слово: q 111 1 Б) Початкове слово: q 11 111

Теза Тьюринга Теза Тьюринга: для кожного алгоритму А може бути побудована машина Тьюринга, яка за однакових вихідних даних дає ті ж результати, що і алгоритм А. n Якщо 1 q 1 2 1 qz 2, то говоритимемо, що машина Т переробляє слово 1 2 у слово 1 2 і позначати це Т(1 2) = 1 2. n Запис Т() - позначення машини Т з вихідними значеннями.

Нормальні алгоритми Маркова n Нормальні алгоритми Маркова (НАМ) перетворюють слова кінцевої довжини один одного за допомогою підстановки. n Завдання НАМ Алфавіт Підстановки u v Заключна підстановка u v n Упр 29 Задано нормальний алгоритм Маркова: Алфавіт – алфавіт російської. Схема підстановки (Я У, Л У, С М, В Б, Р Т, Т Р, О Х, Н А) Початкове слово СЛОН. n Знайти кінцеве слово.

Оцінка складності алгоритмів n Припустимо, що функції f(n) і g(n) вимірюють ефективність двох алгоритмів, зазвичай називають функціями тимчасової складності. Будемо говорити, що порядок зростання функції f(n) не більше, ніж у g(n), якщо знайдеться така позитивна константа, що | f(n) |

Ефективність алгоритмів A B C D E n 3 n 2 2 n 2+4 n n 3 2 n 1 1 мс 3 мс 6 мс 2 мс 10 10 мс 300 мс 240 мс 1 024 з 100 мс 30 с 20, 4 століть 0, 56 год 11, 6 днів 10176 століть 1000 мс 0, 83 год 1 мс

Теорія алгоритмів n Теорія алгоритмів – класифікує задачі за складністю. У цьому класифікуються лише розпізнавальні завдання. n Розпізнавальна задача – це завдання, що відповідає на запитання: чи мають вхідні дані певну властивість. У разі: вхідні дані – граф, властивість – чи є граф Гамільтоновим?

Класи P і NP n Складаний клас P: існує алгоритм A, який вирішує завдання за поліноміальний час. n Складаний клас NP - існує алгоритм А, що перевіряє запропоноване рішення, за поліноміальний час. n Завдання про гамільтоновий цикл полягає у з'ясуванні, чи має заданий граф G гамільтонів цикл відноситься до NP-класу.

Приклади NP задач n Завдання про здійсненність булевих функцій: дізнатися за цією булевою формулою, чи існує набір змінних, що входять до неї, що обертає її в 1. n Завдання про кліку: за даним графом дізнатися, чи є в ньому кліки (повні підграфи) даного розміру . n Проблема існування гамільтонова циклу у графі. n Існування цілого рішення системи лінійних нерівностей.

Можливість розв'язання NP задач перебором n Спочатку рішення не відоме. Тому важливим виявляється те, що будь-яке завдання, що відноситься до NP-класу, можна вирішити за експоненційний час перебором усіх можливих комбінацій.

Співвідношення Р і NP n Будь-яке завдання з P належить NP. n Таким чином, клас NP включає клас P. На даний час, невідомо чи збігаються класи P і NP, але більшість фахівців вважає, що ні.

Співвідношення Р і NP n Якщо виявиться, що Р= NP 1) NP задачі виявляться розв'язувані за розумний час. 2) Існує ряд завдань, які навмисно використовують завдання експоненційної складності (тобто припускаючи, що завдання вирішити неможливо). Наприклад, у криптографії існує розділ про шифрування з відкритим ключем, розшифрувати які практично неможливо. Якщо раптом P = NP, то багато секретів перестануть бути такими.

NP-повні завдання n Найбільш серйозна причина вважати, що P ≠ NP - існування NP повних завдань. n Неформально!!!, задача Q зводиться до задачі Q′, якщо задачу Q можна вирішити за поліноміальний час для будь-якого входу, вважаючи відомим рішення задачі Q′ для якогось іншого входу. Наприклад, завдання розв'язання лінійного рівняння зводиться до завдання розв'язання квадратного рівняння.

NP-повні завдання n NP-повне завдання - це таке завдання з класу NP, до якого можна звести будь-яке інше завдання з класу NP. n NP-повні завдання утворюють підмножину «найскладніших» завдань у класі NP. Якщо для будь-якої NP-повної задачі буде знайдено поліноміальний алгоритм розв'язання, то будь-яке інше завдання з класу NP може бути вирішене за поліноміальний час. n Усі перелічені NP-завдання є NP-повними. У тому числі завдання про цикл Гамільтона.

Комбінаційні схеми, хоч і дозволяють реалізувати будь-які фіксованізалежності між вхідними і вихідними сигналами, що неспроможні змінювати характеру своєї поведінки (тобто. послідовності обробки даних) - будь-яка така зміна вимагає зміни структури схеми, тобто, власне, переходу до інший схемі. Вирішити проблему перебудови роботи без зміни структури схеми можливо, якщо ввести до неї елементи пам'яті,які дозволяли б фіксувати і зберігати проміжні стану пристрою - у разі вихідний сигнал залежатиме лише від вхідного сигналу, а й стану схеми. Якщо кількість таких елементів звичайно, то, як зазначалося вище, дискретний пристрій буде називатися кінцевим автоматом.

Кінцевим автоматомназивається система Y, Q> , в якій X і Y є кінцевими вхідним та вихідним алфавітами, Q - кінцевим безліччю внутрішніх станів, Y (x, q) - функцією переходів та Q (x, q) - функцією виходів.

Як зазначалося раніше, Y (x, q)задає порядок перетворення вхідних символів та стану автомата на попередньому такті у стан на наступному, a Q (x, q) -перетворення вхідних символів та стану автомата на поточному такті у вихідний символ. Якщо q 0 - початковий стан автомата, а i- Номер такту, то його робота описується системою:

Ці співвідношення отримали назву системи канонічних рівнянькінцевий автомат. Користуючись ними можна, починаючи з q 0 ,послідовно знаходити всі наступні стани автомата та вихідні символи.

Виділяються два типи автоматів - ініційніі неініційні. Уініціальних автоматах початковий стан фіксований (тобто вони завжди починають працювати з одного й того ж стану q 0).У неініціальних автоматах як початковий стан може бути обрано будь-яке з безлічі Q; цим вибором визначається подальша поведінка автомата.

Подання конкретного кінцевого автомата фактично зводиться до опису автоматних функцій, що його задають. З системи (9.3) слід, що з кінцевому числі можливих внутрішніх станів кількість можливих значень автоматних функції також виявляється кінцевим. Їх опис можливий різними способами, найбільш поширеними з яких є табличнийта за допомогою діаграм.

У табличному способіавтоматичні функції задаються двома кінцевими таблицями, що називаються відповідно матрицею переходіві матрицею виходів.У цих таблицях рядки позначаються літерами вхідного алфавіту, а стовпці - літерами внутрішнього алфавіту (символами, що кодують внутрішній стан автомата). У матриці переходів на перетині рядка (x k)та стовпця (q r)містяться значення функції Y ( q r, x k),а у матриці виходів - значення функції Q (q r, x k).

Подання кінцевого автомата фактично зводиться до опису автоматних функцій, що його задають.

Існують три способи завдання кінцевих автоматів:

· Табличний (матриці переходів та виходів);

· Графічний (за допомогою графів);

· Аналітичний (за допомогою формул).

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

Табличний метод.Складається таблиця стану автомата для функції переходу – і функції виходу. При цьому:

· Стовпці таблиці відповідають елементам вхідного алфавіту X,

· Рядки таблиці відповідають станам (елементи кінцевої множини Q).

Перетину i-и рядка і j-го стовпця відповідає клітина (i, j), яка є аргументом функцій 8 і λ автомата в момент, коли він перебуває в стані q iна його вході – слово x j ,а в відповідній клітині запишемо значення функцій 8 і λ. Таким чином, вся таблиця відповідає безлічі Qх X.

При заповненні таблиці переходів кожна клітина однозначно визначається парою символів: символом наступного стану та символом вихідного сигналу.

Насправді автоматні функції задаються двома кінцевими таблицями, іменованими відповідно матрицею переходуі матрицею висновків. При цьому рядки позначаються літерами вхідного алфавіту, а стовпці літерами внутрішнього алфавіту (символами, що кодують внутрішній стан автомата).

У матриці переходів на перетині рядка x k і стовпця q r міститься значення функції переходу δ(q i , х)та функції висновків λ(q, х). У ряді випадків обидві таблиці поєднуються в одну таблицю.

Графічний метод.

Автомат задається з допомогою графа, схеми, графіка та інших. Завдання з допомогою орієнтованого графа – зручніша і компактна форма опису автомата.

Граф автоматамістить

· Вершини,відповідні станом q iÎQ,

· Дуги,сполучні вершини – переходи автомата з одного стану до іншого. На дугах прийнято вказувати пари вхідних та вихідних сигналів – сигналів переходів.

Якщо автомат переходить із стану q 1у стан q 2під впливом кількох вхідних сигналів, то відповідної дузі графа цей варіант буде представлений через диз'юнкцію. Для представлення автомата використовують двополюсні графи з виділеними початковим та кінцевим станами.

Розробка шкали "приладу для вимірювання ємності"

№	індикація	+	-	перевантаження.	вимк.	┤
0	вих.сост.	1	0	0	0	ні
1	0	2	0	13	0	так
2	50	3	1	13	0	так
3	100	4	2	13	0	так
4	150	5	3	13	0	так
5	200	6	4	13	0	так
6	250	7	5	13	0	так
7	300	8	6	13	0	так
8	350	9	7	13	0	так
9	400	10	8	13	0	так
10	450	11	9	13	0	так
11	500	13	10	13	0	так
12	ОВ	0	0	0	0	ні
13	аварія	0	0	0	0	ні

Рис.2.5. Граф шкали приладу для вимірювання ємності

Висновок

Оскільки застосування генераторів з коливальними контурами (типу RC) для генерування коливань високої частоти не задовольняє, для генератора, що розробляється, була взята схема типу LC (в якості фазуючого ланцюжка взята триточкова схема з автотрансформаторним зв'язком, активний елемент - транзистор).

У теоретичній частині даної курсової роботи було розглянуто елементи генераторів LC-типу. Також було розглянуто класифікацію генераторів LC-типу, їх призначення, і навіть різні схеми генераторів. А також технічні характеристики генераторів елементів.

У практичній частині було розкрито тему, що стосується шифраторів, дешифраторів, їх призначення, а також були спроектовані електричні функціональні та електричні принципові схеми шифраторів та дешифраторів. Було розкрито тему карт Карно. Також було розроблено сегмент “b” семисегментного індикатора. Було розроблено кінцевий автомат для шкали приладу для вимірювання ємності, а також граф для нього.

Можна виділити два класи мов для опису функціонування цифрових автоматів: початкові мови та стандартні або автоматні мови.

Початкові мови задають функцію переходів та функцію виходів у неявному вигляді. Поведінка автомата описується термінах вхідних і вихідних послідовностей, реалізованих оператором, чи послідовностей управляючих сигналів, які впливають управляючий автомат.

Для опису функціонування абстрактних ЦА початковою мовою можна використовувати:

Мова регулярних виразів алгебри подій;

Мова обчислення предикатів;

Мова логічних схем алгоритмів (ЛСА);

Мова граф схема алгоритмів (ГСА).

Мова ДСА разом із мовою ЛСА називають одним загальним терміном: мова операторних схем алгоритмів (ОСА). Насправді найчастіше використовується мова ДСА.

3.3.1 Завдання цифрових автоматів на стандартних
мовами

Стандартні чи автоматні мовизадають функції переходів виходів у явному вигляді. До них відносяться таблиці, графи, матриці переходів та виходів та їх аналітична інтерпретація. Щоб задати автомат, необхідно описати всі компоненти вектора
S =(A, Z, W, d, l, a 1).

При табличному способі завданняавтомат Милі описується за допомогою двох таблиць: таблиці переходів та таблиці виходів. Таблиця переходів задає функцію d(табл.3.4.), таблиця виходів функцію - l(Табл.3.5.). Кожному стовпцю табл.3.4 і 3.5 поставлено у відповідність один стан з множини А, кожному рядку – один вхідний сигнал з множини Z. На перетині стовпця a mта рядки z fу табл.3.4 записується стан
as, в яке повинен перейти автомат зі стану a m, під дією вхідного сигналу z f, тобто. a s = d(a m, z f). На перетині стовпця a mта рядки z fу табл.3.5 записується вихідний сигнал w g, що видається автоматом у стані a mпри надходженні на його вхід сигналу z f, тобто.
w g = l(a m, z f).

Таблиця 3.4 Таблиця 3.5

Таблиця переходів автомата Мілі		Таблиця виходів автомата Мілі
	a 1	a 2	a 3	a 4			a 1	a 2	a 3	a 4
z 1	a 2	a 2	a 1	a 1		z 1	w 1	w 1	w 2	w 4
z 2	a 4	a 3	a 4	a 3		z 2	w 5	w 3	w 4	w 5

Для зазначених таблиць А ={ a 1 , a 2 , a 3 , a 4 } ; Z ={ z 1 , z 2 };
W ={w 1 , w 2 , w 3 , w 4 , w 5 }.

Автомат Милі може бути заданий також однією суміщеною таблицею переходів та виходів (табл.3.6), в якій кожен елемент as/w g, записаний на перетині стовпця a mта рядки z f, визначається так:

a s = d(a m, z f);w g = l(a m, z f).

Автомат Мура задається однією зазначеною таблицею переходів (табл.3.7), у якій кожному стовпцю приписані як стану a mале ще й вихідний сигнал w g, що відповідає цьому стану, де w g = l(a m). Для табл. 3.7 A ={a 4 , a 2 , a 3 , a 4 }; Z ={z 1 , z 2 };
W ={w 1 , w 2 , w 3 }.

Однією з переваг цього способу завдання є те, що будь-яка таблиця переходів та виходів задає кінцевий автомат. При цьому мають задовольнятися дві умови:

Умова однозначності(детермінованості), що означає, що для будь-якої пари a m z fпоставлено єдиний стан переходу asта єдиний вихідний сигнал w g, що видається на переході.

Умова повної визначеностіщо означає, що для всіх можливих пар a m z fзавжди вказано стан та вихідний сигнал.

Таблиця 3.6 Таблиця 3.7

Поєднана таблиця переходів та виходів автомата Мілі		Позначена таблиця переходів та виходів автомата Мура
	a 1	a 2	a 3	a 4			w 3	w 2	w 3	w 1
z 1	a 2 /w 1	a 2 /w 1	a 1 /w 2	a 1 /w 4			a 1	a 2	a 3	a 4
z 2	a 4 /w 5	a 3 /w 3	a 4 /w 4	a 3 /w 5		z 1	a 1	a 3	a 1	a 4
						z 2	a 2	a 4	a 4	a 1

Автомат називається неповністю визначенимабо частковим, якщо функція dвизначена не на всіх парах ( a m z f)Î A x Z, або функція lвизначена не на всіх зазначених парах у разі автомата Милі та на безлічі не всіх внутрішніх станів для автомата Мура. Для часткових автоматів Мілі та Мура у розглянутих таблицях на місці невизначених станів та вихідних сигналів ставиться прочерк.

Граф автомата– це орієнтований граф, вершини якого відповідають станам, а дуги – переходам з-поміж них. Дуга, спрямована з вершини a mу вершину as, задає перехід в автоматі зі стану a mу стан as. На початку цієї дуги записується вхідний сигнал z f Î Z, що викликає цей перехід: a s = d(a m, z f). Для графа автомата Мілі вихідний сигнал w g Î W, що формується на переході, записується в кінці дуги, а для автомата Мура поряд з вершиною , зазначеною станом a m, У якому він формується. Якщо перехід в автоматі зі стану a mу стан asпроводиться під дією кількох вхідних сигналів, то дузі графа, спрямованої з a mв as, приписуються всі ці вхідні та відповідні вихідні сигнали. Графи автоматів Мілі та Мура, побудовані за табл.3.6 та 3.7 наведені відповідно на рис.3.7. а, б.

Щодо графа умови однозначності та повної визначеності будуть укладені в наступному:

Немає двох ребер з однаковими вхідними позначками, які з однієї й тієї вершини;

Для будь-якої вершини a mі для будь-якого вхідного сигналу z fє таке ребро, позначене символом z f, що виходить з a m.

Рис.3.7. Графи автоматів: a- Милі; б– Мура

При завданні графів із великою кількістю станів і переходів наочність втрачається, тому виявляється кращим задавати цей граф як списку – таблиці переходів.

Пряма таблиця переходів- Таблиця, в якій послідовно перераховуються всі переходи спочатку з першого стану, потім з другого і т.д. Табл.3.8 - пряма таблиця переходів автомата Милі, побудована за графом, наведеним на рис.3.7.а.

У ряді випадків виявляється зручним користуватися зворотнійтаблицею переходів, у якій стовпці позначені так само, але спочатку записуються всі переходи у перший стан, потім у друге тощо. Табл.3.9 - зворотна таблиця переходів автомата Милі, побудована за графом, наведеним на рис.3.7, а.

Як і граф таблиці переходів повинні задовольняти умови однозначності та повноти переходів.

Таблиця 3.8 Пряма таблиця переходів автомата Милі		Таблиця 3.9 Зворотна таблиця переходів автомата Милі
a m(t)	z f(t)	as(t+ 1)	w g(t)		a m(t)	z f(t)	as(t+ 1)	w g(t)
a 1	z 1	a 2	w 1	a 3	z 1	a 1	w 2
	z 2	a 4	w 5	a 4	z 1	w 4
a 2	z 1	a 2	w 1	a 1	z 1	a 2	w 1
	z 2	a 3	w 3	a 2	z 1	w 1
a 3	z 1	a 1	w 2	a 2	z 2	a 3	w 3
	z 2	a 4	w 4	a 4	z 2	w 5
a 4	z 1	a 1	w 4	a 1	z 2	a 4	w 5
	z 2	a 3	w 5	a 3	z 2	w 4

Пряма таблиця переходів автомата Мура будується як і для автомата Милі. Різниця лише в тому, що вихідний сигнал w g(t) приписується стану автомата a m(t) (табл. 3.10), або вихідний сигнал w g(t as(t+ 1) (табл. 3.11).

Зворотня таблиця переходів автомата Мура будується як і для автомата Милі. Різниця лише в тому, що вихідний сигнал w g(t+1) приписується стану автомата as(t+ 1) (табл. 3.12).

У деяких випадках для завдання автомата використовуються матриці переходів та виходів, які є таблицею з двома входами. Рядки та стовпці таблиці відзначені станами. Якщо існує перехід з a mпід дією z fв asз видачею w g, то на перетині рядка a mта стовпця asзаписується пара z f w g. Зрозуміло, що не всяка матриця задає автомат. Як граф та таблиця переходів та виходів вона повинна задовольняти умовам однозначності та повноти переходів.

Таблиця 3.10 Пряма таблиця переходів автомата Мура Варіант 1		Таблиця 3.11 Пряма таблиця переходів автомата Мура Варіант 2
a m(t)	w g(t)	z f(t)	as(t+ 1)		a m(t)	z f(t)	as(t+ 1)	w g(t+1)
a 1	w 3	z 1	a 1	a 1	z 1	a 1	w 3
		z 2	a 2		z 2	a 2	w 2
a 2	w 2	z 1	a 3	a 2	z 1	a 3	w 3
		z 2	a 4		z 2	a 4	w 1
a 3	w 3	z 1	a 1	a 3	z 1	a 1	w 3
		z 2	a 4		z 2	a 4	w 1
a 4	w 1	z 1	a 4	a 4	z 1	a 4	w 1
		z 2	a 1		z 2	a 1	w 3

Таблиця 3.12 Зворотня таблиця переходів автомата Мура Варіант 2
a m(t)	z f(t)	as(t+ 1)	w g(t+1)
a 1	z 1	a 1	w 3
a 3	z 1
a 4	z 2
a 1	z 2	a 2	w 2
a 2	z 1	a 3	w 3
a 2	z 2	a 4	w 1
a 3	z 2
a 4	z 1

Системи канонічних рівнянь (СКУ) та системи вихідних функцій (СВФ)є аналітичною інтерпретацією таблиць переходів та виходів чи графів автоматів. СКУ – визначає функції переходів ЦА, а СВФ – визначає функції виходів ЦА.

Кожен стан ЦА інтерпретується як подія, що відповідає безлічі переходів у цей стан:

Для скорочення запису СКУ та СВФ будемо надалі скрізь, де це можливо, опускати знаки кон'юнкції та часу tу правій частині рівнянь типу (3.10).

Для автомата Милі заданого табл.3.8 або табл. 3.9 запишемо СКУ та СВФ (3.811 та 3.12. відповідно):

a 1 (t+1) = z 1 a 3 Ú z 1 a 4 ; a 2 (t+1) = z 1 a 1 Ú z 1 a 2 ; a 3 (t+1) = z 2 a 2 Ú z 2 a 4 ; a 4 (t+1) = z 2 a 1 Ú z 2 a 3 .

(3.11)

w 1 (t) = z 1 a 1 Ú z 1 a 2 ; w 2 (t) = z 1 a 3 ; w 3 (t) = z 2 a 2 ; w 4 (t) = z 1 a 4 Ú z 2 a 3; w 5 (t) = z 2 a 1 Ú z 2 a 4.

(3.12)

Запишемо СКУ та СВФ для автомата Мура, заданого табл. 3.10 – 3.12, (3.13 та 3.14 відповідно).