Теорія автоматів

Класи автоматів

Теорія автоматів
Тема вивчення/дослідження	автомат і автоматон
Підтримується Вікіпроєктом	Вікіпедія:Проєкт:Математика
Теорія автоматів у Вікісховищі

Тео́рія автома́тів — логіко-математична теорія, об'єктом дослідження якої є абстрактні автомати — покрокові перетворювачі інформації; розділ кібернетики.

Виникнення

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

Як цілісна конструктивна структурна теорія теорія автоматів склалася на початку 50-х рр. XX сторіччя.

Завдання, що вирішує теорія автоматів

Коло проблем, що розв'язуються теорією автоматів, досить широке: від проблем «геделівського типу» (повнота, розв'язність тощо) до проблем самовдосконалення, самоорганізації, самопроектування комп'ютерів включно.

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

Способи задання автоматів

Табличний спосіб

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

Таблиця переходів

x j \ a i	a 0	…	a n
x 1	d (a 0, x 1)	…	d (a n, x 1)
…	…	…	…
x m	d (a 0, x m)	…	d (a n, x m)

Таблиця виходів:

x j \ a i	a 0	…	a n
x 1	(a 0, x 1)	…	(a n, x 1)
…	…	…	…
x m	(a 0, x m)	…	(a n, x m)

Рядки цих таблиць відповідають вхідним сигналам $\mathbf {x} (t)$, а стовпці — станам. На перетині стовпця $\mathbf {a} _{i}$ і рядка $\mathbf {x} _{j}$ в таблиці переходів ставиться стан a _s = d [a _i, x _j], в які автомат перейде зі стану a _i під впливом сигналу x _j; а в таблиці виходів — відповідний цьому переходу вихідний сигнал y _g = l [a _i, x _j]. Іноді автомат Мілі задають суміщеною таблицею переходів і виходів, вона в деяких випадках більш зручна. 

Суміщена таблиця переходів і виходів автомата Мілі.

x j \ a i	a 0	…	a n
x 1	d (a 0, x 1) \ (a 0, x 1)	…	d (a n, x 1) \  (a n, x 1)
…	…	…	,..
x m	d (a 0, x m) \  (a 0, x m)	…	d (a n, x m) \  (a n, x m)

            

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

Зазначена таблиця переходів автомата Мура 

y g	l (a 0)	…	l (a n)
x j \ a c	a 0	…	a n
x 1	d (a 0, x1)	…	…
x m	d (a 0, xm)	…	d (a n, xm)

У цій таблиці кожному стовпцю приписаний, крім стану a _i, ще й вихідний сигнал y (t) = l (a (t)), що відповідає цьому стану. Таблиця переходів автомата Мура називається зазначеної тому, що кожний стаан відзначено вихідним сигналом. Приклади табличного завдання автоматів Мілі і Мура. 

Автомат Мура: 

yg	y 2	y 1	y 3	y 3	y 2
x j \ x j	a 0	a 1	a 2	a 3	a 4
x 1	a 2	a 1	a 3	a 4	a 2
x 2	a 3	a 4	a 4	a 0	a 1

Автомат Мілі:  

x j \ a i	a 0	a 1	a 2	a 3
x 1	a 1 / y 1	a 2 / y3	a 3 / y2	a 0 / y1
x 2	a 0 / y 2	a 0 / y1	a 3 / y1	a 2 / y3

      

За цими таблицями можливо знайти реакцію автомата на будь-яке вхідне слово.   

Графічний спосіб

При графічному способі завдання автомата здійснюється за допомогою графа. Цей спосіб заснований на використанні орієнтованих зв'язкових графів. Вершини графів відповідають станам автомата, а дуги — переходам між ними. Дві вершини граф a _i і a _s з'єднуються дугою, спрямованої від a _i до a _s, якщо в автоматі є перехід з a _i в a _s,тобто a _s = d (a _i, x _j). В автоматі Мілі дуга відзначається вхідним сигналом x _j, що викликав перехід, і вихідним сигналом y _g, який виникає при переході. Усередині кружечка, що позначає вершину графа, записується стан. 

Синтез логіки

У синтезі логічних схем формують систему з елементарних логічних елементів (наприклад, таких, як регістри, або елементи комбінаційної логіки), еквівалентну заданому абстрактному автомату. Така система може бути названа структурним автоматом.^{[джерело?]}

Основною сферою практичного застосування теорії автоматів є проектування цифрових електронних схем (таких, наприклад, як центральні процесори).^{[джерело?]}

Завдяки успішному розв'язанню проблеми спряження етапів абстрактного^{[що це?]} й структурного^{[що це?]} синтезів, досягненням теорії надійного і блокового синтезу стало можливим викласти теорію синтезу цифрових схем як єдину^{[джерело?]} математичну теорію.

Див. також

• Скінченний автомат
• Регулярний вираз
• Суперпозиція автоматів
• Мікрокод
• Лінійний автомат
• Автомат вільний
• Автомат частковий
• Операційний автомат
• Мінімальний автомат
• Структурна теорія автоматів
• Автоматні відображення

Джерела

• Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973.
• Філософський словник / за ред. В. І. Шинкарука. — 2-ге вид., перероб. і доп. — К. : Головна ред. УРЕ, 1986.
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
• Роджерс Х.. Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
• Автоматів теорія [Архівовано 24 вересня 2020 у Wayback Machine.] // ВУЕ