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

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

Виникнення

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

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

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

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

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

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

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

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

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

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)

 Рядки цих таблиць відповідають вхідним сигналам x (t), а стовпці - станам. На перетині стовпця a _i і рядки 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

      

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

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

При графічному способі завдання автомата здійснюється за допомогою графа. Цей спосіб заснований на використанні орієнтованих зв'язкових графів. Вершини графів відповідають станам автомата, а дуги - переходам між ними. Дві вершини графа 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, рос. вид. 1974;
• Філософський словник / за ред. В. І. Шинкарука. — 2-ге вид., перероб. і доп. — К. : Головна ред. УРЕ, 1986.

Див. також

Автомат скінченний Регулярний вислів Автоматів суперпозиція Автомат мікропрограмний Автомат лінійний Автомат вільний

Автомат без пам'яті Автомат частковий Автомат операційний Автомат мінімальний Структурна теорія автоматів