Теорія автоматів: відмінності між версіями
[перевірена версія] | [перевірена версія] |
Yuriz (обговорення | внесок) →Тенденції: Коли - сучасній?? |
Олюсь (обговорення | внесок) мНемає опису редагування |
||
(Не показано 23 проміжні версії 12 користувачів) | |||
Рядок 1: | Рядок 1: | ||
⚫ | |||
{{без джерел|дата=травень 2018}} |
|||
'''Тео́рія автома́тів''' — логіко-математична теорія, об'єктом дослідження якої є [[ |
{{unibox}}'''Тео́рія автома́тів''' — логіко-математична теорія, об'єктом дослідження якої є [[Абстрактний автомат|абстрактні автомати]] — покрокові перетворювачі [[інформація|інформації]]; розділ [[Кібернетика|кібернетики]]{{sfn|Глушков|1973|p=54}}. |
||
== Виникнення == |
== Виникнення == |
||
Виникнення й розвиток теорії автоматів пов'язані зі створенням технічних засобів [[ |
Виникнення й розвиток теорії автоматів пов'язані зі створенням технічних засобів [[Автоматизація|автоматизації]], [[проектування]]м складних цифрових [[Комп'ютер|обчислювальних систем]] з [[Комп'ютерна програма|програмним керуванням]], розробкою [[математична модель|математичних моделей]] процесів переробки інформації в складних [[динамічна система|динамічних системах]] тощо. |
||
Як цілісна конструктивна структурна [[теорія]] теорія автоматів склалася на початку 50-х рр. XX сторіччя. |
Як цілісна конструктивна структурна [[теорія]] теорія автоматів склалася на початку 50-х рр. XX сторіччя{{sfn|Глушков|1973|p=54}}. |
||
=== Завдання, що вирішує теорія автоматів === |
=== Завдання, що вирішує теорія автоматів === |
||
Рядок 187: | Рядок 187: | ||
=== Графічний спосіб === |
=== Графічний спосіб === |
||
При графічному способі завдання автомата здійснюється за допомогою графа. Цей спосіб заснований на використанні орієнтованих зв'язкових графів. Вершини графів відповідають станам автомата, а дуги — переходам між ними. Дві вершини |
При графічному способі завдання автомата здійснюється за допомогою графа. Цей спосіб заснований на використанні орієнтованих зв'язкових графів. Вершини графів відповідають станам автомата, а дуги — переходам між ними. Дві вершини граф '''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}} |
||
* [[Скінченний автомат]] |
|||
* [[Автомат скінченний]] |
|||
* [[Регулярний |
* [[Регулярний вираз]] |
||
* [[Суперпозиція автоматів]] |
|||
* [[Автоматів суперпозиція]] |
|||
* [[Мікрокод]] |
|||
* [[Автомат мікропрограмний]] |
|||
* [[Лінійний автомат]] |
|||
* [[Автомат лінійний]] |
|||
* [[Автомат вільний]] |
* [[Автомат вільний]] |
||
{{Multicol-break}} |
|||
* [[Автомат без пам'яті]] |
|||
* [[Автомат частковий]] |
* [[Автомат частковий]] |
||
* [[Операційний автомат ]] |
|||
* [[Автомат операційний]] |
|||
* [[Мінімальний автомат]] |
|||
* [[Автомат мінімальний]] |
|||
* [[Структурна теорія автоматів]] |
* [[Структурна теорія автоматів]] |
||
* [[Автоматні відображення]] |
|||
{{Multicol-end}} |
|||
{{colend}} |
|||
== |
== Примітки == |
||
{{reflist}} |
|||
* «[[Енциклопедія кібернетики]]», відповідальний ред. [[Глушков Віктор Михайлович|В. Глушков]], 2 тт., [[1973]], рос. вид. [[1974]]; |
|||
== Джерела == |
|||
* {{ЕК}} |
|||
* {{ФС}} |
* {{ФС}} |
||
* {{Cinderella Book}} |
|||
* {{Роджерс.Теорія рекурсивних функцій}} |
|||
⚫ | |||
⚫ | |||
== Посилання == |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
{{Refimprove|дата=листопад 2015}} |
|||
⚫ | |||
⚫ | |||
[[Категорія:Теорія автоматів| ]] |
[[Категорія:Теорія автоматів| ]] |
||
[[Категорія:Кібернетика]] |
[[Категорія:Кібернетика]] |
Поточна версія на 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.] // ВУЕ
![]() |
Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |
![]() |
Це незавершена стаття про інформаційні технології. Ви можете допомогти проєкту, виправивши або дописавши її. |