Теорія автоматів: відмінності між версіями
[неперевірена версія] | [перевірена версія] |
Немає опису редагування |
Олюсь (обговорення | внесок) мНемає опису редагування |
||
(Не показані 45 проміжних версій ще одного користувача) | |||
Рядок 1: | Рядок 1: | ||
⚫ | |||
'''Тео́рія автома́тів''' |
{{unibox}}'''Тео́рія автома́тів''' — логіко-математична теорія, об'єктом дослідження якої є [[Абстрактний автомат|абстрактні автомати]] — покрокові перетворювачі [[інформація|інформації]]; розділ [[Кібернетика|кібернетики]]{{sfn|Глушков|1973|p=54}}. |
||
== Виникнення == |
== Виникнення == |
||
Виникнення й розвиток теорії автоматів пов'язані зі створенням технічних засобів [[ |
Виникнення й розвиток теорії автоматів пов'язані зі створенням технічних засобів [[Автоматизація|автоматизації]], [[проектування]]м складних цифрових [[Комп'ютер|обчислювальних систем]] з [[Комп'ютерна програма|програмним керуванням]], розробкою [[математична модель|математичних моделей]] процесів переробки інформації в складних [[динамічна система|динамічних системах]] тощо. |
||
Як цілісна конструктивна структурна [[теорія]] теорія автоматів склалася на початку 50-х рр. XX сторіччя. |
Як цілісна конструктивна структурна [[теорія]] теорія автоматів склалася на початку 50-х рр. XX сторіччя{{sfn|Глушков|1973|p=54}}. |
||
=== Завдання, що вирішує теорія автоматів === |
=== Завдання, що вирішує теорія автоматів === |
||
Коло проблем, що розв'язуються теорією автоматів, досить широке: від проблем «геделівського типу» ([[Теорема Геделя про повноту|повнота]], розв'язність тощо) до проблем [[самовдосконалення]], [[самоорганізація|самоорганізації]], [[самопроектування]] [[ |
Коло проблем, що розв'язуються теорією автоматів, досить широке: від проблем «геделівського типу» ([[Теорема Геделя про повноту|повнота]], розв'язність тощо) до проблем [[самовдосконалення]], [[самоорганізація|самоорганізації]], [[самопроектування]] [[комп'ютер]]ів включно. |
||
У [[дискретна математика|дискретній математиці]], [[інформатика|інформатиці]], '''теорія автоматів''' вивчає абстрактні машини у вигляді математичних моделей, і проблеми, які вони можуть вирішувати. |
У [[дискретна математика|дискретній математиці]], [[інформатика|інформатиці]], '''теорія автоматів''' вивчає абстрактні машини у вигляді математичних моделей, і проблеми, які вони можуть вирішувати. |
||
Рядок 15: | Рядок 16: | ||
== Способи задання автоматів == |
== Способи задання автоматів == |
||
=== |
=== Табличний спосіб === |
||
При табличному способі завдання автомат Мілі описується двома таблицями: таблицею переходів і таблицею виходів. |
При табличному способі завдання автомат Мілі описується двома таблицями: таблицею переходів і таблицею виходів. |
||
''Таблиця переходів'' |
''Таблиця переходів'' |
||
Рядок 22: | Рядок 23: | ||
!x <sub>j</sub> \ a <sub>i</sub> |
!x <sub>j</sub> \ a <sub>i</sub> |
||
!a <sub>0</sub> |
!a <sub>0</sub> |
||
! |
!… |
||
!a <sub>n</sub> |
!a <sub>n</sub> |
||
|- |
|- |
||
|x <sub>1</sub> |
|x <sub>1</sub> |
||
|d (a <sub>0,</sub> x <sub>1)</sub> |
|d (a <sub>0,</sub> x <sub>1)</sub> |
||
| |
|… |
||
|d (a <sub>n,</sub> x <sub>1)</sub> |
|d (a <sub>n,</sub> x <sub>1)</sub> |
||
|- |
|- |
||
| |
|… |
||
| |
|… |
||
| |
|… |
||
| |
|… |
||
|- |
|- |
||
|x <sub>m</sub> |
|x <sub>m</sub> |
||
|d (a <sub>0,</sub> x <sub>m)</sub> |
|d (a <sub>0,</sub> x <sub>m)</sub> |
||
| |
|… |
||
|d (a <sub>n,</sub> x <sub>m)</sub> |
|d (a <sub>n,</sub> x <sub>m)</sub> |
||
|} |
|} |
||
Рядок 45: | Рядок 46: | ||
!x <sub>j</sub> \ a <sub>i</sub> |
!x <sub>j</sub> \ a <sub>i</sub> |
||
!a <sub>0</sub> |
!a <sub>0</sub> |
||
! |
!… |
||
!a <sub>n</sub> |
!a <sub>n</sub> |
||
|- |
|- |
||
|x <sub>1</sub> |
|x <sub>1</sub> |
||
|(a <sub>0,</sub> x <sub>1)</sub> |
|(a <sub>0,</sub> x <sub>1)</sub> |
||
| |
|… |
||
|(a <sub>n,</sub> x <sub>1)</sub> |
|(a <sub>n,</sub> x <sub>1)</sub> |
||
|- |
|- |
||
| |
|… |
||
| |
|… |
||
| |
|… |
||
| |
|… |
||
|- |
|- |
||
|x <sub>m</sub> |
|x <sub>m</sub> |
||
|(a <sub>0,</sub> x <sub>m)</sub> |
|(a <sub>0,</sub> x <sub>m)</sub> |
||
| |
|… |
||
|(a <sub>n,</sub> x <sub>m)</sub> |
|(a <sub>n,</sub> x <sub>m)</sub> |
||
|} |
|} |
||
Рядки цих таблиць відповідають вхідним сигналам <math>\mathbf x (t)</math>, а стовпці — станам. На перетині стовпця <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>; а в таблиці виходів — відповідний цьому переходу вихідний сигнал '''y''' <sub>g</sub> = '''l [a''' <sub>i,</sub> '''x''' <sub>j</sub>]. Іноді автомат Мілі задають суміщеною таблицею переходів і виходів, вона в деяких випадках більш зручна. |
|||
''Суміщена таблиця переходів і виходів автомата Мілі.'' |
''Суміщена таблиця переходів і виходів автомата Мілі.'' |
||
Рядок 74: | Рядок 75: | ||
|a <sub>0</sub> |
|a <sub>0</sub> |
||
|} |
|} |
||
! |
!… |
||
!a <sub>n</sub> |
!a <sub>n</sub> |
||
|- |
|- |
||
|x <sub>1</sub> |
|x <sub>1</sub> |
||
|d (a <sub>0,</sub> x <sub>1)</sub> \<br> |
|d (a <sub>0,</sub> x <sub>1)</sub> \<br/> |
||
<br> |
<br/> |
||
(a <sub>0,</sub> x <sub>1)</sub> |
(a <sub>0,</sub> x <sub>1)</sub> |
||
| |
|… |
||
|d (a <sub>n,</sub> x <sub>1)</sub> \ <br> |
|d (a <sub>n,</sub> x <sub>1)</sub> \ <br/> |
||
<br> |
<br/> |
||
(a <sub>n,</sub> x <sub>1)</sub> |
|||
|- |
|- |
||
| |
|… |
||
| |
|… |
||
| |
|… |
||
|,.. |
|,.. |
||
|- |
|- |
||
|x <sub>m</sub> |
|x <sub>m</sub> |
||
|d (a <sub>0,</sub> x <sub>m)</sub> \ <br> |
|d (a <sub>0,</sub> x <sub>m)</sub> \ <br/> |
||
<br> |
<br/> |
||
(a <sub>0,</sub> x <sub>m)</sub> |
(a <sub>0,</sub> x <sub>m)</sub> |
||
| |
|… |
||
|d (a <sub>n,</sub> x <sub>m)</sub> \ <br> |
|d (a <sub>n,</sub> x <sub>m)</sub> \ <br/> |
||
<br> |
<br/> |
||
(a <sub>n,</sub> x <sub>m)</sub> |
|||
|} |
|} |
||
Завдання таблиць переходів і виходів повністю описує роботу кінцевого автомата, оскільки задаються не тільки самі функції переходів і виходів, але також і всі три алфавіту: вхідний, вихідний і алфавіт станів. Так як в автоматі Мура вихідний сигнал однозначно визначається станом автомата, то для його завдання потрібно тільки одна таблиця, яка називається зазначеної таблицею переходів автомата Мура. |
|||
Зазначена таблиця переходів ''автомата Мура '' |
Зазначена таблиця переходів ''автомата Мура '' |
||
Рядок 108: | Рядок 109: | ||
!y <sub>g</sub> |
!y <sub>g</sub> |
||
!l (a <sub>0)</sub> |
!l (a <sub>0)</sub> |
||
! |
!… |
||
!l (a <sub>n)</sub> |
!l (a <sub>n)</sub> |
||
|- |
|- |
||
|x <sub>j</sub> \ a <sub>c</sub> |
|x <sub>j</sub> \ a <sub>c</sub> |
||
|a <sub>0</sub> |
|a <sub>0</sub> |
||
| |
|… |
||
|a <sub>n</sub> |
|a <sub>n</sub> |
||
|- |
|- |
||
|x <sub>1</sub> |
|x <sub>1</sub> |
||
|d (a <sub>0,</sub> x<sub>1)</sub> |
|d (a <sub>0,</sub> x<sub>1)</sub> |
||
| |
|… |
||
| |
|… |
||
|- |
|- |
||
|x <sub>m</sub> |
|x <sub>m</sub> |
||
|d (a <sub>0,</sub> x<sub>m)</sub> |
|d (a <sub>0,</sub> x<sub>m)</sub> |
||
| |
|… |
||
|d (a <sub>n,</sub> x<sub>m)</sub> |
|d (a <sub>n,</sub> x<sub>m)</sub> |
||
|} |
|} |
||
У цій таблиці кожному стовпцю приписаний, крім стану '''a''' <sub>i,</sub> ще й вихідний сигнал '''y (t)''' = '''l (a''' (t)), що відповідає цьому стану. Таблиця переходів автомата Мура називається зазначеної тому, що кожний стаан відзначено вихідним сигналом. Приклади табличного завдання автоматів Мілі і Мура. |
|||
'''Автомат Мура: ''' |
'''Автомат Мура: ''' |
||
Рядок 182: | Рядок 183: | ||
|} |
|} |
||
За цими таблицями можливо знайти реакцію автомата на будь-яке вхідне слово. |
|||
=== |
=== Графічний спосіб === |
||
⚫ | При графічному способі завдання автомата здійснюється за допомогою графа. Цей спосіб заснований на використанні орієнтованих зв'язкових графів. Вершини графів відповідають станам автомата, а дуги |
||
⚫ | При графічному способі завдання автомата здійснюється за допомогою графа. Цей спосіб заснований на використанні орієнтованих зв'язкових графів. Вершини графів відповідають станам автомата, а дуги — переходам між ними. Дві вершини граф '''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> який виникає при переході. Усередині кружечка, що позначає вершину графа, записується стан. |
||
'''^ Граф для автомата Мілі''' |
|||
[[Файл:Fuzzy logic temperature en.svg|center]] |
|||
== Синтез автоматів == |
|||
== Синтез логіки == |
|||
{{main|Синтез логіки|Рівень передачі регістрів|Мови опису апаратури}} |
|||
У синтезі логічних схем формують систему з елементарних логічних елементів (наприклад, таких, як [[Регістр (цифрова техніка)|регістри]], або елементи [[Комбінаційна логіка|комбінаційної логіки]]), еквівалентну заданому абстрактному автомату. Така система може бути названа ''структурним автоматом''.{{джерело}} |
|||
У синтезі автоматів формують систему з елементарних автоматів, еквівалентну заданому [[автомат абстрактний|абстрактному автомату]]. Такий автомат називається [[автомат структурний|структурним]]. |
|||
Основною сферою практичного застосування теорії автоматів є проектування цифрових електронних схем (таких, наприклад, як [[Центральний процесор|центральні процесори]]).{{джерело}} |
|||
⚫ | |||
⚫ | |||
== Тенденції == |
|||
Сучасній теорії автоматів властива тенденція до інтенсивного розвитку насамперед тих її розділів, які виникли скоріше у зв'язку з внутрішньою необхідністю розробки апарату самої теорії, ніж завдяки практичним потребам. У широкому розумінні теорія автоматів охоплює не лише теорію дискретних, а й теорії неперервних (аналогових) і гібридних автоматів. |
|||
== Література == |
|||
* «[[Енциклопедія кібернетики]]», відповідальний ред. [[Глушков Віктор Михайлович|В. Глушков]], 2 тт., [[1973]], рос. вид. [[1974]]; |
|||
⚫ | |||
== Див. також == |
== Див. також == |
||
{{ |
{{cols|cols=3}} |
||
* [[Скінченний автомат]] |
|||
* [[Автомат скінченний]] |
|||
* [[Регулярний |
* [[Регулярний вираз]] |
||
* [[Суперпозиція автоматів]] |
|||
* [[Автоматів суперпозиція]] |
|||
* [[Мікрокод]] |
|||
* [[Автомат мікропрограмний]] |
|||
* [[Лінійний автомат]] |
|||
* [[Автомат лінійний]] |
|||
* [[Автомат вільний]] |
* [[Автомат вільний]] |
||
{{Multicol-break}} |
|||
* [[Автомат без пам'яті]] |
|||
* [[Автомат частковий]] |
* [[Автомат частковий]] |
||
* [[Операційний автомат ]] |
|||
* [[Автомат операційний]] |
|||
* [[Мінімальний автомат]] |
|||
* [[Автомат мінімальний]] |
|||
* [[Структурна теорія автоматів]] |
* [[Структурна теорія автоматів]] |
||
* [[Автоматні відображення]] |
|||
{{Multicol-end}} |
|||
{{colend}} |
|||
== Примітки == |
|||
⚫ | |||
{{reflist}} |
|||
⚫ | |||
== Джерела == |
|||
[[it:Automa (informatica)]] |
|||
* {{ЕК}} |
|||
[[simple:Automaton]] |
|||
⚫ | |||
* {{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}} |
|||
{{ВП-портали|Програмування|Математика}} |
|||
[[Категорія:Теорія автоматів| ]] |
|||
⚫ | |||
[[Категорія:Математична логіка]] |
[[Категорія:Математична логіка]] |
||
__ОБОВ_ЗМІСТ__ |
|||
__ІНДЕКС__ |
Поточна версія на 17:01, 29 червня 2024
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d3/Automata_theory_ua.svg/300px-Automata_theory_ua.svg.png)
Теорія автоматів | |
Тема вивчення/дослідження | автомат і автоматон |
---|---|
Підтримується Вікіпроєктом | Вікіпедія:Проєкт:Математика |
![]() |
Тео́рія автома́тів — логіко-математична теорія, об'єктом дослідження якої є абстрактні автомати — покрокові перетворювачі інформації; розділ кібернетики[1].
Виникнення й розвиток теорії автоматів пов'язані зі створенням технічних засобів автоматизації, проектуванням складних цифрових обчислювальних систем з програмним керуванням, розробкою математичних моделей процесів переробки інформації в складних динамічних системах тощо.
Як цілісна конструктивна структурна теорія теорія автоматів склалася на початку 50-х рр. XX сторіччя[1].
Коло проблем, що розв'язуються теорією автоматів, досить широке: від проблем «геделівського типу» (повнота, розв'язність тощо) до проблем самовдосконалення, самоорганізації, самопроектування комп'ютерів включно.
У дискретній математиці, інформатиці, теорія автоматів вивчає абстрактні машини у вигляді математичних моделей, і проблеми, які вони можуть вирішувати.
При табличному способі завдання автомат Мілі описується двома таблицями: таблицею переходів і таблицею виходів.
Таблиця переходів
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.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
- Роджерс Х. . Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
- Автоматів теорія [Архівовано 24 вересня 2020 у Wayback Machine.] // ВУЕ
![]() |
Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |
![]() |
Це незавершена стаття про інформаційні технології. Ви можете допомогти проєкту, виправивши або дописавши її. |