Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Тео́рія автома́тів — логіко-математична теорія, об'єктом дослідження якої є абстрактні автомати — покрокові перетворювачі інформації; розділ кібернетики.
| Теорія автоматів | |
| Тема вивчення/дослідження | автомат і автоматон |
|---|---|
| Підтримується Вікіпроєктом | |
 Теорія автоматів у Вікісховищі | |
Виникнення
Виникнення й розвиток теорії автоматів пов'язані зі створенням технічних засобів автоматизації, проектуванням складних цифрових обчислювальних систем з програмним керуванням, розробкою математичних моделей процесів переробки інформації в складних динамічних системах тощо.
Як цілісна конструктивна структурна теорія теорія автоматів склалася на початку 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.
Джерела
- Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973.
- Філософський словник / за ред. В. І. Шинкарука. — 2-ге вид., перероб. і доп. — К. : Головна ред. УРЕ, 1986.
- Hopcroft, John E.; ; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
- . Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
- Автоматів теорія [ 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, Інтернет
Teo riya avtoma tiv logiko matematichna teoriya ob yektom doslidzhennya yakoyi ye abstraktni avtomati pokrokovi peretvoryuvachi informaciyi rozdil kibernetiki Klasi avtomativ Klacannya na kozhnomu shari skerovuye do statti na vidpovidnu temu Teoriya avtomativTema vivchennya doslidzhennyaavtomat i avtomatonPidtrimuyetsya VikiproyektomVikipediya Proyekt Matematika Teoriya avtomativ u VikishovishiViniknennyaViniknennya j rozvitok teoriyi avtomativ pov yazani zi stvorennyam tehnichnih zasobiv avtomatizaciyi proektuvannyam skladnih cifrovih obchislyuvalnih sistem z programnim keruvannyam rozrobkoyu matematichnih modelej procesiv pererobki informaciyi v skladnih dinamichnih sistemah tosho Yak cilisna konstruktivna strukturna teoriya teoriya avtomativ sklalasya na pochatku 50 h rr XX storichchya Zavdannya sho virishuye teoriya avtomativ Kolo problem sho rozv yazuyutsya teoriyeyu avtomativ dosit shiroke vid problem gedelivskogo tipu povnota rozv yaznist tosho do problem samoorganizaciyi komp yuteriv vklyuchno U diskretnij matematici informatici teoriya avtomativ vivchaye abstraktni mashini u viglyadi matematichnih modelej i problemi yaki voni mozhut virishuvati Sposobi zadannya avtomativTablichnij sposib Pri tablichnomu sposobi zavdannya avtomat Mili opisuyetsya dvoma tablicyami tabliceyu perehodiv i tabliceyu vihodiv Tablicya perehodiv 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 Tablicya vihodiv 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 Ryadki cih tablic vidpovidayut vhidnim signalam x t displaystyle mathbf x t a stovpci stanam Na peretini stovpcya ai displaystyle mathbf a i i ryadka xj displaystyle mathbf x j v tablici perehodiv stavitsya stan a s d a i x j v yaki avtomat perejde zi stanu a i pid vplivom signalu x j a v tablici vihodiv vidpovidnij comu perehodu vihidnij signal y g l a i x j Inodi avtomat Mili zadayut sumishenoyu tabliceyu perehodiv i vihodiv vona v deyakih vipadkah bilsh zruchna Sumishena tablicya perehodiv i vihodiv avtomata Mili x j a i a 0 a n x 1 d a 0 x 1 a 0 x 1 d a n x 1 a n x 1 x m d a 0 x m a 0 x m d a n x m a n x m Zavdannya tablic perehodiv i vihodiv povnistyu opisuye robotu kincevogo avtomata oskilki zadayutsya ne tilki sami funkciyi perehodiv i vihodiv ale takozh i vsi tri alfavitu vhidnij vihidnij i alfavit staniv Tak yak v avtomati Mura vihidnij signal odnoznachno viznachayetsya stanom avtomata to dlya jogo zavdannya potribno tilki odna tablicya yaka nazivayetsya zaznachenoyi tabliceyu perehodiv avtomata Mura Zaznachena tablicya perehodiv avtomata Mura 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 U cij tablici kozhnomu stovpcyu pripisanij krim stanu a i she j vihidnij signal y t l a t sho vidpovidaye comu stanu Tablicya perehodiv avtomata Mura nazivayetsya zaznachenoyi tomu sho kozhnij staan vidznacheno vihidnim signalom Prikladi tablichnogo zavdannya avtomativ Mili i Mura Avtomat Mura 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 Avtomat Mili 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 Za cimi tablicyami mozhlivo znajti reakciyu avtomata na bud yake vhidne slovo Grafichnij sposib Pri grafichnomu sposobi zavdannya avtomata zdijsnyuyetsya za dopomogoyu grafa Cej sposib zasnovanij na vikoristanni oriyentovanih zv yazkovih grafiv Vershini grafiv vidpovidayut stanam avtomata a dugi perehodam mizh nimi Dvi vershini graf a i i a s z yednuyutsya dugoyu spryamovanoyi vid a i do a s yaksho v avtomati ye perehid z a i v a s tobto a s d a i x j V avtomati Mili duga vidznachayetsya vhidnim signalom x j sho viklikav perehid i vihidnim signalom y g yakij vinikaye pri perehodi Useredini kruzhechka sho poznachaye vershinu grafa zapisuyetsya stan Sintez logikiDokladnishe Sintez logiki Riven peredachi registriv ta Movi opisu aparaturi U sintezi logichnih shem formuyut sistemu z elementarnih logichnih elementiv napriklad takih yak registri abo elementi kombinacijnoyi logiki ekvivalentnu zadanomu abstraktnomu avtomatu Taka sistema mozhe buti nazvana strukturnim avtomatom dzherelo Osnovnoyu sferoyu praktichnogo zastosuvannya teoriyi avtomativ ye proektuvannya cifrovih elektronnih shem takih napriklad yak centralni procesori dzherelo Zavdyaki uspishnomu rozv yazannyu problemi spryazhennya etapiv abstraktnogo sho ce j strukturnogo sho ce sinteziv dosyagnennyam teoriyi nadijnogo i blokovogo sintezu stalo mozhlivim viklasti teoriyu sintezu cifrovih shem yak yedinu dzherelo matematichnu teoriyu Div takozhSkinchennij avtomat Regulyarnij viraz Mikrokod Linijnij avtomat Avtomat vilnij Avtomat chastkovij Operacijnij avtomat Minimalnij avtomat Strukturna teoriya avtomativ Avtomatni vidobrazhennyaPrimitkiGlushkov 1973 s 54 DzherelaEnciklopediya kibernetiki u 2 t za red V M Glushkova Kiyiv Gol red Ukrayinskoyi radyanskoyi enciklopediyi 1973 Filosofskij slovnik za red V I Shinkaruka 2 ge vid pererob i dop K Golovna red URE 1986 Hopcroft John E Ullman Jeffrey D 2001 Vstup do teoriyi avtomativ mov i obchislen vid 2nd Addison Wesley s 521 angl inshi movi Teoriya rekursivnyh funkcij i effektivnaya vychislimost M Mir 1972 416 s ros Avtomativ teoriya 24 veresnya 2020 u Wayback Machine VUE Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Ce nezavershena stattya pro informacijni tehnologiyi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi