Теорія автоматів
Тео́рія автома́тів — логіко-математична теорія, об'єктом дослідження якої є абстрактні автомати — покрокові перетворювачі інформації; розділ кібернетики[1].
Виникнення
Виникнення й розвиток теорії автоматів пов'язані зі створенням технічних засобів автоматизації, проектуванням складних цифрових обчислювальних систем з програмним керуванням, розробкою математичних моделей процесів переробки інформації в складних динамічних системах тощо.
Як цілісна конструктивна структурна теорія теорія автоматів склалася на початку 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) |
Рядки цих таблиць відповідають вхідним сигналам , а стовпці — станам. На перетині стовпця і рядка в таблиці переходів ставиться стан a s = d [a i, x j], в які автомат перейде зі стану a i під впливом сигналу x j; а в таблиці виходів — відповідний цьому переходу вихідний сигнал y g = l [a i, x j]. Іноді автомат Мілі задають суміщеною таблицею переходів і виходів, вона в деяких випадках більш зручна.
Суміщена таблиця переходів і виходів автомата Мілі.
| x j \ a i |
|
… | 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) \
|
Завдання таблиць переходів і виходів повністю описує роботу кінцевого автомата, оскільки задаються не тільки самі функції переходів і виходів, але також і всі три алфавіту: вхідний, вихідний і алфавіт станів. Так як в автоматі Мура вихідний сигнал однозначно визначається станом автомата, то для його завдання потрібно тільки одна таблиця, яка називається зазначеної таблицею переходів автомата Мура.
Зазначена таблиця переходів автомата Мура
| 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, який виникає при переході. Усередині кружечка, що позначає вершину графа, записується стан.
Синтез логіки
У синтезі логічних схем формують систему з елементарних логічних елементів (наприклад, таких, як регістри, або елементи комбінаційної логіки), еквівалентну заданому абстрактному автомату. Така система може бути названа структурним автоматом.[джерело?]
Основною сферою практичного застосування теорії автоматів є проектування цифрових електронних схем (таких, наприклад, як центральні процесори).[джерело?]
Завдяки успішному розв'язанню проблеми спряження етапів абстрактного[що це?] й структурного[що це?] синтезів, досягненням теорії надійного і блокового синтезу стало можливим викласти теорію синтезу цифрових схем як єдину[джерело?] математичну теорію.
Див. також
Примітки
- ↑ а б Глушков, 1973, p. 54.
Джерела
- Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973.
- Філософський словник / за ред. В. І. Шинкарука. — 2-ге вид., перероб. і доп. — К. : Головна ред. УРЕ, 1986.
- Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (англ.) (вид. 2nd). Addison–Wesley. с. 521. Посилання на друге видання книги.
- Роджерс Х.. Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
- Автоматів теорія [Архівовано 24 вересня 2020 у Wayback Machine.] // ВУЕ
|
Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |
|
Це незавершена стаття про інформаційні технології. Ви можете допомогти проєкту, виправивши або дописавши її. |
Джерело: стаття у Вікіпедії та історія редагувань (автори).