Перегляд вихідного коду сторінки Теорія автоматів

{{Теорія автоматів}}
{{unibox}}'''Тео́рія автома́тів'''&nbsp;— логіко-математична теорія, об'єктом дослідження якої є [[Абстрактний автомат|абстрактні автомати]]&nbsp;— покрокові перетворювачі [[інформація|інформації]]; розділ [[Кібернетика|кібернетики]]{{sfn|Глушков|1973|p=54}}.

== Виникнення ==

Виникнення й розвиток теорії автоматів пов'язані зі створенням технічних засобів [[Автоматизація|автоматизації]], [[проектування]]м складних цифрових [[Комп'ютер|обчислювальних систем]] з [[Комп'ютерна програма|програмним керуванням]], розробкою [[математична модель|математичних моделей]] процесів переробки інформації в складних [[динамічна система|динамічних системах]] тощо.

Як цілісна конструктивна структурна [[теорія]] теорія автоматів склалася на початку 50-х рр. XX сторіччя{{sfn|Глушков|1973|p=54}}.

=== Завдання, що вирішує теорія автоматів ===

Коло проблем, що розв'язуються теорією автоматів, досить широке: від проблем «геделівського типу» ([[Теорема Геделя про повноту|повнота]], розв'язність тощо) до проблем [[самовдосконалення]], [[самоорганізація|самоорганізації]], [[самопроектування]] [[комп'ютер]]ів включно.

У [[дискретна математика|дискретній математиці]], [[інформатика|інформатиці]], '''теорія автоматів''' вивчає абстрактні машини у вигляді математичних моделей, і проблеми, які вони можуть вирішувати.

== Способи задання автоматів ==

=== Табличний спосіб ===
При табличному способі завдання автомат Мілі описується двома таблицями: таблицею переходів і таблицею виходів.&nbsp;

''Таблиця переходів''
{| class="wikitable"
!x <sub>j</sub> \ a <sub>i</sub>  
!a <sub>0</sub> 
!…
!a <sub>n</sub> 
|-
|x <sub>1</sub> 
|d (a <sub>0,</sub> x <sub>1)</sub> 
|…
|d (a <sub>n,</sub> x <sub>1)</sub>
|-
|…
|…
|…
|…
|-
|x <sub>m</sub> 
|d (a <sub>0,</sub> x <sub>m)</sub>
|…
|d (a <sub>n,</sub> x <sub>m)</sub>
|}
''Таблиця виходів:''

{| class="wikitable"
!x <sub>j</sub> \ a <sub>i</sub> 
!a <sub>0</sub> 
!…
!a <sub>n</sub> 
|-
|x <sub>1</sub> 
|(a <sub>0,</sub> x <sub>1)</sub>
|…
|(a <sub>n,</sub> x <sub>1)</sub> 
|-
|…
|…
|…
|…
|-
|x <sub>m</sub> 
|(a <sub>0,</sub> x <sub>m)</sub> 
|…
|(a <sub>n,</sub> x <sub>m)</sub>
|}

Рядки цих таблиць відповідають вхідним сигналам <math>\mathbf x (t)</math>, а стовпці&nbsp;— станам. На перетині стовпця <math>\mathbf a_i </math> і рядка <math>\mathbf x_j </math> в таблиці переходів ставиться стан '''a''' <sub>s</sub> = '''d [a''' <sub>i,</sub> '''x''' <sub>j</sub>], в які автомат перейде зі стану '''a''' <sub>i</sub> під впливом сигналу '''x''' <sub>j</sub>; а в таблиці виходів&nbsp;— відповідний цьому переходу вихідний сигнал '''y''' <sub>g</sub> = '''l [a''' <sub>i,</sub> '''x''' <sub>j</sub>]. Іноді автомат Мілі задають суміщеною таблицею переходів і виходів, вона в деяких випадках більш зручна. 

''Суміщена таблиця переходів і виходів автомата Мілі.''

{| class="wikitable"
!x <sub>j</sub> \ a <sub>i</sub>
!
{|
|a <sub>0</sub> 
|}
!…
!a <sub>n</sub> 
|-
|x <sub>1</sub> 
|d (a <sub>0,</sub> x <sub>1)</sub> \<br/>
<br/>
(a <sub>0,</sub> x <sub>1)</sub> 
|…
|d (a <sub>n,</sub> x <sub>1)</sub> \ <br/>
<br/>
(a <sub>n,</sub> x <sub>1)</sub> 
|-
|…
|…
|…
|,..
|-
|x <sub>m</sub> 
|d (a <sub>0,</sub> x <sub>m)</sub> \ <br/>
<br/>
(a <sub>0,</sub> x <sub>m)</sub> 
|…
|d (a <sub>n,</sub> x <sub>m)</sub> \ <br/>
<br/>
(a <sub>n,</sub> x <sub>m)</sub> 
|}            

Завдання таблиць переходів і виходів повністю описує роботу кінцевого автомата, оскільки задаються не тільки самі функції переходів і виходів, але також і всі три алфавіту: вхідний, вихідний і алфавіт станів. Так як в автоматі Мура вихідний сигнал однозначно визначається станом автомата, то для його завдання потрібно тільки одна таблиця, яка називається зазначеної таблицею переходів автомата Мура. 

Зазначена таблиця переходів ''автомата Мура ''

{| class="wikitable"
!y <sub>g</sub> 
!l (a <sub>0)</sub> 
!…
!l (a <sub>n)</sub> 
|-
|x <sub>j</sub> \ a <sub>c</sub> 
|a <sub>0</sub> 
|…
|a <sub>n</sub> 
|-
|x <sub>1</sub> 
|d (a <sub>0,</sub> x<sub>1)</sub> 
|…
|…
|-
|x <sub>m</sub> 
|d (a <sub>0,</sub> x<sub>m)</sub> 
|…
|d (a <sub>n,</sub> x<sub>m)</sub> 
|}

У цій таблиці кожному стовпцю приписаний, крім стану '''a''' <sub>i,</sub> ще й вихідний сигнал '''y (t)''' = '''l (a''' (t)), що відповідає цьому стану. Таблиця переходів автомата Мура називається зазначеної тому, що кожний стаан відзначено вихідним сигналом. Приклади табличного завдання автоматів Мілі і Мура. 

'''Автомат Мура: '''
{| class="wikitable"
!yg 
!y <sub>2</sub>
!y <sub>1</sub>
!y <sub>3</sub>
!y <sub>3</sub> 
!y <sub>2</sub> 
|-
|x <sub>j</sub> \ x <sub>j</sub> 
|a <sub>0</sub>
|a <sub>1</sub> 
|a <sub>2</sub>
|a <sub>3</sub> 
|a <sub>4</sub> 
|-
|x <sub>1</sub> 
|a <sub>2</sub> 
|a <sub>1</sub> 
|a <sub>3</sub> 
|a <sub>4</sub>
|a <sub>2</sub> 
|-
|x <sub>2</sub> 
|a <sub>3</sub> 
|a <sub>4</sub> 
|a <sub>4</sub>
|a <sub>0</sub>
|a <sub>1</sub> 
|}

'''Автомат Мілі: ''' 

{| class="wikitable"
!x <sub>j</sub> \ a <sub>i</sub>
!a <sub>0</sub> 
!a <sub>1</sub> 
!a <sub>2</sub> 
!a <sub>3</sub> 
|-
|x <sub>1</sub> 
|a <sub>1</sub> / y <sub>1</sub>
|a <sub>2</sub> / y<sub>3</sub>
|a <sub>3</sub> / y<sub>2</sub> 
|a <sub>0</sub> / y<sub>1</sub> 
|-
|x <sub>2</sub> 
|a <sub>0</sub> / y <sub>2</sub> 
|a <sub>0</sub> / y<sub>1</sub> 
|a <sub>3</sub> / y<sub>1</sub> 
|a <sub>2</sub> / y<sub>3</sub>
|}      

За цими таблицями можливо знайти реакцію автомата на будь-яке вхідне слово.   

=== Графічний спосіб ===

При графічному способі завдання автомата здійснюється за допомогою графа. Цей спосіб заснований на використанні орієнтованих зв'язкових графів. Вершини графів відповідають станам автомата, а дуги&nbsp;— переходам між ними. Дві вершини граф '''a''' <sub>i</sub> і '''a''' <sub>s</sub> з'єднуються дугою, спрямованої від '''a''' <sub>i</sub> до '''a''' <sub>s,</sub> якщо в автоматі є перехід з '''a''' <sub>i</sub> в '''a''' <sub>s,</sub>тобто '''a''' <sub>s</sub> = '''d (a''' <sub>i,</sub> '''x''' <sub>j).</sub> В автоматі Мілі дуга відзначається вхідним сигналом '''x''' <sub>j,</sub> що викликав перехід, і вихідним сигналом '''y''' <sub>g,</sub> який виникає при переході. Усередині кружечка, що позначає вершину графа, записується стан. 

== Синтез логіки ==
{{main|Синтез логіки|Рівень передачі регістрів|Мови опису апаратури}}

У синтезі логічних схем формують систему з елементарних логічних елементів (наприклад, таких, як [[Регістр (цифрова техніка)|регістри]], або елементи [[Комбінаційна логіка|комбінаційної логіки]]), еквівалентну заданому абстрактному автомату. Така система може бути названа ''структурним автоматом''.{{джерело}}

Основною сферою практичного застосування теорії автоматів є проектування цифрових електронних схем (таких, наприклад, як [[Центральний процесор|центральні процесори]]).{{джерело}}

Завдяки успішному розв'язанню проблеми спряження етапів абстрактного{{що це?}} й структурного{{що це?}} синтезів, досягненням теорії надійного і блокового синтезу стало можливим викласти теорію синтезу цифрових схем як єдину{{джерело}} математичну теорію.

== Див. також ==
{{cols|cols=3}}
* [[Скінченний автомат]]
* [[Регулярний вираз]]
* [[Суперпозиція автоматів]]
* [[Мікрокод]]
* [[Лінійний автомат]]
* [[Автомат вільний]]
* [[Автомат частковий]]
* [[Операційний автомат ]]
* [[Мінімальний автомат]]
* [[Структурна теорія автоматів]]
* [[Автоматні відображення]]
{{colend}}

== Примітки ==
{{reflist}}

== Джерела ==
* {{ЕК}}
* {{ФС}}
* {{Cinderella Book}}
* {{Роджерс.Теорія рекурсивних функцій}}
* [https://vue.gov.ua/Автоматів_теорія Автоматів теорія] {{Webarchive|url=https://web.archive.org/web/20200924132335/https://vue.gov.ua/Автоматів_теорія |date=24 вересня 2020 }} // [[ВУЕ]]

{{Math-stub}}
{{Compu-stub}}

{{Інформатика|state=collapsed}}
{{ВП-портали|Програмування|Математика}}

[[Категорія:Теорія автоматів| ]]
[[Категорія:Кібернетика]]
[[Категорія:Математична логіка]]