Абстрактний автомат (в теорії алгоритмів) - математична абстракція. модель дискретного пристрою, що має один вхід, один вихід і в кожен момент часу знаходиться в одному стані з безлічі можливих. На вхід цього пристрою надходять символи одного алфавіту. на виході воно видає символи (в загальному випадку) іншого алфавіту.
Формально абстрактний автомат визначається як п'ятірка
Де S - кінцеве безліч станів автомата, X, Y - кінцеві вхідний і вихідний алфавіти відповідно, з яких формуються рядки, зчитувальні і видаються автоматом, - функція переходів, - функція виходів.
Функціональна схема абстрактного автомата
Абстрактний автомат з виділеним початковим станом називається ініціальним автоматом. Таким чином, абстрактний автомат визначає сімейство ініціальних автоматів
Якщо функції переходів і виходів однозначно визначені для кожної пари, то автомат називають детермінованим. В іншому випадку автомат називають недетермінованим або частково певним.
Якщо функція переходів і / або функція виходів є випадковими, то автомат називають імовірнісним.
Обмеження числа параметрів абстрактного автомата визначило таке поняття як кінцевий автомат.
Функціонування автомата полягає в породженні двох послідовностей: послідовності чергових станів автомата і послідовності вихідних символів, які для послідовності символів розгортаються в моменти дискретного часу t = 1, 2, 3, ... Моменти дискретного часу отримали назву тактів.
Функціонування автомата в дискретні моменти часу t може бути описано системою рекурентних співвідношень:
Для уточнення властивостей абстрактних автоматів введена класифікація.
Абстрактні автомати утворюють фундаментальний клас дискретних моделей як самостійна модель, і як основна компонента машин Тьюринга. автоматів з магазинної пам'яттю. кінцевих автоматів та інших перетворювачів інформації.
Модель абстрактного автомата широко використовується, як базова, для побудови дискретних моделей автоматів, які розпізнають, що породжують і перетворюють послідовності символів.
Дивитися що таке "Абстрактний автомат" в інших словниках:
абстрактний автомат - abstraktusis automatas statusas T sritis automatika atitikmenys: angl. abstract automaton vok. abstrakter Automat, m rus. абстрактний автомат, m pranc. automate abstrait, m ... Automatikos terminų žodynas
Кінцевий автомат - кінцевий автомат абстрактний автомат без вихідного потоку, число можливих станів якого звичайно. Результат роботи автомата визначається по його кінцевого стану. Існують різні варіанти завдання кінцевого автомата. Наприклад, ... ... Вікіпедія
Тьюринг, МАШИНА - Абстрактний автомат (тобто комп'ютер або інший точний, певний механізм), теоретично охарактеризований британським математиком Аланом М. Тьюрингом в 1930 х рр. В основному, машина Тьюринга складається з стрічки і голівки, що зчитує. Стрічка ... ... Тлумачний словник по психології
Теорія автоматів - [automa-ta theory] розділ теоретичної кібернетики, який вивчає математичні моделі (звані тут автоматами або машинами) реальних або можливих пристроїв, що переробляють дискретну ін-формацію дискретними ж тактами. Основними ... ... Економіко-математичний словник
Теорія автоматів - [automa-ta theory] розділ теоретичної кібернетики, який вивчає математичні моделі (звані тут автоматами або машинами) реальних або можливих пристроїв, що переробляють дискретну ін-формацію дискретними ж тактами. Основними ... ... Економіко-математичний словник
теорія автоматів - Розділ теоретичної кібернетики, який вивчає математичні моделі (звані тут автоматами або машинами) реальних або можливих пристроїв, що переробляють дискретну інформацію дискретними ж тактами. Основними поняттями цієї теорії ... ... Довідник технічного перекладача
Теорія автоматів - Теорія автоматів розділ дискретної математики, що вивчає абстрактні автомати обчислювальні машини, представлені у вигляді математичних моделей і завдання, які вони можуть вирішувати. Теорія автоматів найтісніше пов'язана з ... ... Вікіпедія
Комп'ютер - Схема персонального комп'ютера: 1. Монітор 2. Материнська плата 3 ... Вікіпедія
Формальні методи - Приклад формальної специфікації з використанням Z нотації В інформатиці та інженерії програмного забезпечення формальними методами називається група технік, заснованих на математичному апараті для ... Вікіпедія
- Кінцевий автомат. Джессі Рассел. Ця книга буде виготовлена в відповідності з Вашим замовленням за технологією Print-on-Demand. High Quality Content by WIKIPEDIA articles! Кінцевий автомат - абстрактний автомат без вихідного ... Детальніше Купити за 1147 руб
- Абстрактний автомат. Джессі Рассел. Ця книга буде виготовлена в відповідності з Вашим замовленням за технологією Print-on-Demand. High Quality Content by WIKIPEDIA articles! Абстр? Ктний автомати? Т (в теорії алгоритмів) - ... Детальніше Купити за 870 руб