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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Виникнення[ред.ред. код]

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

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

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

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

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

Способи задання автоматів[ред.ред. код]

1. Табличний спосіб [ред.ред. код]

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

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

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

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

j \ a i  0  ... n 
1  (a 0, x 1) ... (a n, x 1) 
... ... ... ...
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]. Іноді автомат Мілі задають суміщеною таблицею переходів і виходів, вона в деяких випадках більш зручна. 

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

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


(a 0, x 1) 

... d (a n, x 1) \ 


(a n, x 1) 

... ... ... ,..
m  d (a 0, x m) \ 


(a 0, x m) 

... d (a n, x m) \ 


(a n, x m) 

            


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

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

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

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

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

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

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

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

      

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

2. Графічний спосіб[ред.ред. код]

Файл:Граф для для автомата Мура.png
Граф для для автомата Мура
Файл:Автомат Мура й еквівалентний йому автомат Мілі.jpg
Автомат Мілі є еквівалентним автомату Мура

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


Синтез автоматів[ред.ред. код]

Докладніше: Синтез автоматів

У синтезі автоматів формують систему з елементарних автоматів, еквівалентну заданому абстрактному автомату. Такий автомат називається структурним.

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

Тенденції[ред.ред. код]

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

Література[ред.ред. код]


Див. також[ред.ред. код]