Тео́рія автома́тів — логіко-математична теорія, об'єктом дослідження якої є абстрактні автомати — покрокові перетворювачі інформації; розділ кібернетики.
Теорія автоматів | |
Тема вивчення/дослідження | автомат і автоматон |
---|---|
Підтримується Вікіпроєктом | |
Теорія автоматів у Вікісховищі |
Виникнення
Виникнення й розвиток теорії автоматів пов'язані зі створенням технічних засобів автоматизації, проектуванням складних цифрових обчислювальних систем з програмним керуванням, розробкою математичних моделей процесів переробки інформації в складних динамічних системах тощо.
Як цілісна конструктивна структурна теорія теорія автоматів склалася на початку 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) |
Рядки цих таблиць відповідають вхідним сигналам , а стовпці — станам. На перетині стовпця і рядка в таблиці переходів ставиться стан 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, с. 54.
Література
- Глушков, В. (1973). Енциклопедія кібернетики. Т. 1. Київ.
- Філософський словник / за ред. В. І. Шинкарука. — 2-ге вид., перероб. і доп. — К. : Головна ред. УРЕ, 1986.
- Автоматів теорія [ 24 вересня 2020 у Wayback Machine.] // ВУЕ
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Це незавершена стаття про інформаційні технології. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет