Топ питань
Часова шкала
Чат
Перспективи
Теорія автоматів
З Вікіпедії, вільної енциклопедії
Remove ads
Тео́рія автома́тів — логіко-математична теорія, об'єктом дослідження якої є абстрактні автомати — покрокові перетворювачі інформації; розділ кібернетики[1].

Класи автоматів
Remove ads
Виникнення
Виникнення й розвиток теорії автоматів пов'язані зі створенням технічних засобів автоматизації, проектуванням складних цифрових обчислювальних систем з програмним керуванням, розробкою математичних моделей процесів переробки інформації в складних динамічних системах тощо.
Як цілісна конструктивна структурна теорія теорія автоматів склалася на початку 50-х рр. XX сторіччя[1].
Завдання, що вирішує теорія автоматів
Коло проблем, що розв'язуються теорією автоматів, досить широке: від проблем «геделівського типу» (повнота, розв'язність тощо) до проблем самовдосконалення, самоорганізації, самопроектування комп'ютерів включно.
У дискретній математиці, інформатиці, теорія автоматів вивчає абстрактні машини у вигляді математичних моделей, і проблеми, які вони можуть вирішувати.
Remove ads
Способи задання автоматів
Узагальнити
Перспектива
Табличний спосіб
При табличному способі завдання автомат Мілі описується двома таблицями: таблицею переходів і таблицею виходів.
Таблиця переходів
Таблиця виходів:
Рядки цих таблиць відповідають вхідним сигналам , а стовпці — станам. На перетині стовпця і рядка в таблиці переходів ставиться стан a s = d [a i, x j], в які автомат перейде зі стану a i під впливом сигналу x j; а в таблиці виходів — відповідний цьому переходу вихідний сигнал y g = l [a i, x j]. Іноді автомат Мілі задають суміщеною таблицею переходів і виходів, вона в деяких випадках більш зручна.
Суміщена таблиця переходів і виходів автомата Мілі.
Завдання таблиць переходів і виходів повністю описує роботу кінцевого автомата, оскільки задаються не тільки самі функції переходів і виходів, але також і всі три алфавіту: вхідний, вихідний і алфавіт станів. Так як в автоматі Мура вихідний сигнал однозначно визначається станом автомата, то для його завдання потрібно тільки одна таблиця, яка називається зазначеної таблицею переходів автомата Мура.
Зазначена таблиця переходів автомата Мура
У цій таблиці кожному стовпцю приписаний, крім стану a i, ще й вихідний сигнал y (t) = l (a (t)), що відповідає цьому стану. Таблиця переходів автомата Мура називається зазначеної тому, що кожний стаан відзначено вихідним сигналом. Приклади табличного завдання автоматів Мілі і Мура.
Автомат Мура:
Автомат Мілі:
За цими таблицями можливо знайти реакцію автомата на будь-яке вхідне слово.
Графічний спосіб
При графічному способі завдання автомата здійснюється за допомогою графа. Цей спосіб заснований на використанні орієнтованих зв'язкових графів. Вершини графів відповідають станам автомата, а дуги — переходам між ними. Дві вершини граф a i і a s з'єднуються дугою, спрямованої від a i до a s, якщо в автоматі є перехід з a i в a s,тобто a s = d (a i, x j). В автоматі Мілі дуга відзначається вхідним сигналом x j, що викликав перехід, і вихідним сигналом y g, який виникає при переході. Усередині кружечка, що позначає вершину графа, записується стан.
Remove ads
Синтез логіки
У синтезі логічних схем формують систему з елементарних логічних елементів (наприклад, таких, як регістри, або елементи комбінаційної логіки), еквівалентну заданому абстрактному автомату. Така система може бути названа структурним автоматом.[джерело?]
Основною сферою практичного застосування теорії автоматів є проектування цифрових електронних схем (таких, наприклад, як центральні процесори).[джерело?]
Завдяки успішному розв'язанню проблеми спряження етапів абстрактного[що це?] й структурного[що це?] синтезів, досягненням теорії надійного і блокового синтезу стало можливим викласти теорію синтезу цифрових схем як єдину[джерело?] математичну теорію.
Див. також
Примітки
Джерела
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads