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

{{Теорія автоматів}}
'''Скінче́нний автома́т''' ({{lang-en|finite-state machine}}, [[Абстрактний автомат|автомат]] зі [[Скінченна множина|скінченною множиною]] станів)&nbsp;— модель що використовується для опису зміни стану об'єкта в залежності від поточного стану та інформації отриманої ззовні. Поняття скінченного автомата було запропоновано як [[Математична модель|математичну модель]] дискретних приладів, оскільки будь-який такий прилад (через скінченність своїх розмірів) може мати тільки скінченну кількість станів.

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

== Класифікація ==
Існує дві різних групи автоматів: Акцептори/Розпізнавачі і Перетворювачі (Трансдуктори).

=== Акцептори і розпізнавачі ===
[[Файл:Fsm parsing word nice.svg|thumb|400px|right|Скінченний автомат акцептор: приймає слово «nice»]]

'''Акцептори''' і '''розпізнавачі''' (також '''виявлювачі послідовностей''') дають двійковий результат, відповідаючи ''так'' або ''ні'' на питання чи вхідні дані приймаються автоматом. Всі стани автомата можуть бути або приймаючими або ні. Якщо поточний стан автомата є приймаючим, значить послідовність подана на вхід приймається. Як правило, на вхід подаються символи (літери); дії не виконуються. Приклад на зображенні показує автомат, який приймає слово «nice». В цьому автоматі єдиний допустимий стан це 7.

Автомат також може бути описаний як такий, що визначає мову, яка містить всі слова розпізнавані цим автоматом, але не ті які ним відхиляються; тоді ми кажемо, що ця мова ''розпізнається'' автоматом. За визначенням, мови розпізнавані СА це [[регулярні мови]], тобто мова є регулярною якщо існує деякий СА, який розпізнає її.

==== Початковий стан ====
Початковий стан зазвичай позначається стрілкою «звідкись».

==== Допустимі (або кінцеві) стани{{anchor |Допустимі стани}} ====
[[Файл:DFAexample.svg|thumb|300px|right|Приклад скінченного автомата; цей приклад показує автомат, який визначає чи двійкове число має парну кількість 0, де <math>S_1</math> це '''допустимий стан'''.]]

'''Допустимі стани''' (також відомі як '''кінцеві''' стани) це такі, що якщо автомат знаходиться в них це означає, що вхідний рядок, наскільки він опрацьований, належить мові що розпізнається. Зазвичай позначається двома колами.

Приклад допустимого стану з'являється в діаграмі праворуч: a [[детермінований скінченний автомат]] (ДСА), що визначає чи [[Двійкова система числення|двійковий]] вхідний рядок містить парну кількість 0.

''S''<sub>1</sub> (який є початковим станом) показує стан в якому парна кількість 0 була введена. Цей автомат опиниться в допустимому стані, якщо двійковий рядок містить парну кількість 0 (включно з рядком, що не містить 0 взагалі). Приклади рядків розпізнаваних цим ДСА це порожній рядок, 1, 11, 11…, 00, 010, 1010, 10110, і подібні …

=== Перетворювачі (Трансдуктори) ===
Перетворювачі продукують вихід або виконують інші дії, на основі символу на вході і/або на станах. Вони використовуються для керування і в галузі [[Математична лінгвістика|математичної лінгвістики]]. Тут вирізняють два типи:

;[[Автомат Мура]]: вихід залежить тільки від стану. Перевагою моделі Мура є спрощення поведінки. Уявімо двері підйомника. Автомат розпізнає дві команди: «відчинити» і «зачинити», які викликають зміну стану. Вхідна дія (E:) в стані «Відчиняються» змушує двигун відчиняти двері, вхідна дія в стані «Зачиняються» змушує двигун зачиняти двері. Стани Відчинено і Зачинено зупиняють мотор коли двері повністю відчинені або зачинені. Вони повідомляють зовнішній світ (наприклад, інші автомати) про ситуацію: «двері відчинені» або «двері зачинені».

[[Файл:Fsm mealy model door control.svg|thumb|lang=uk|350px|right|скінченний автомат перетворювач: приклад моделі Мілі]]
;[[Автомат Мілі]]: вихід залежить від входу і стану. Використання скінченного автомата Мілі часто призводить до зменшення кількості станів. Приклад на схемі показує скінченний автомат Мілі, який має однакову поведінку із прикладом автомата Мура. Присутні дві вхідні дії (I:): «запустити двигун для закриття дверей якщо прийшла команда зачинити» і «запустити мотор в іншому напрямку якщо для відчинення дверей якщо прийшла команда відчинити». Проміжні стани «Відчинення» і «Зачинення» не показані.

На практиці часто використовується суміш моделей.<ref>{{cite web |title=Moore or Mealy model: that's the question |url=http://www.stateworks.com/technology/TN10-Moore-Or-Mealy-Model/ |website=www.stateworks.com |accessdate=8 вересня 2023}}</ref>

=== Детермінованість ===
Подальша відмінність між '''Детермінованими''' ([[детермінований скінченний автомат|ДСкА]]) і '''недетермінованими''' ([[недетермінований скінченний автомат|НДСкА]]) автоматами. В детермінованих автоматах, кожен стан має один перехід для кожного входу. В недетермінованих автоматах вхід може призвести до одного, більше ніж одного або жодного переходу для даного стану. Ця різниця важлива на практиці, але не в теорії, через існування [[Детермінізація НДСкА|алгоритму трансформації]] будь-якого НДСкА в складніший ДСкА з аналогічною функціональністю.

Якщо автомат має лише один стан, то, згідно [[Енциклопедія кібернетики|Енциклопедії кібернетики]] він називається ''автоматом без пам'яті'' (({{lang-en|combinatorial finite-state machine}}). Оскільки під час роботи стан такого автомату змінюватись не може, то вихідний символ залежить саме від вхідного символу в поточному такті, і не залежить від символів, які надходили перед тим. [[Оператор (математика)|Оператор]], який реалізується таким автоматом, виконує перетворення літери за літерою вхідних символів у вихідні.

== Математична модель ==
Згідно із загальною класифікацією, дані наступні визначення:
* ''детермінований скінченний автомат'' або ''детермінований скінченний автомат акцептор'' є [[Кортеж|п'ятіркою]] <math>(\Sigma, S, s_0, \delta, F)</math>, де:
** <math>\Sigma</math> вхідна [[абетка (інформатика)|абетка]] (скінченний, не порожній набір символів).
** <math>S</math>&nbsp;— скінченний, не порожній набір станів.
** <math>s_0</math>&nbsp;— початковий стан, елемент з <math>S</math>.
** <math>\delta</math>&nbsp;— функція переходу: <math>\delta: S \times \Sigma \rightarrow S</math> (в [[недетермінований скінченний автомат|недетермінованих скінченних автоматах]] це буде <math>\delta: S \times \Sigma \rightarrow \mathcal{P}(S)</math>, тобто, <math>\delta</math> повертає набір станів).
** <math>F</math> набір кінцевих станів, (можливо порожня) підмножина <math>S</math>.

Для обох детермінованих і недетермінованих СА, зручно дозволити <math>\delta</math> бути неповною функцією, тобто <math>\delta(q,x)</math> не має бути визначеною для кожної комбінації <math>q \isin S</math> і <math>x \isin \Sigma</math>. Якщо СА <math>M</math> перебуває в стані <math>q</math>, наступний символ <math>x</math> і <math>\delta(q,x)</math> не визначена, тоді <math>M</math> може повідомити про помилку (тобто відхілити ввід).

* ''скінченний перетворювач'' це шістка <math>(\Sigma, \Gamma, S, s_0, \delta, \omega)</math>, де:
** <math>\Sigma</math>&nbsp;— вхідна абетка (скінченний, не порожній набір символів).
** <math>\Gamma</math>&nbsp;— вихідна абетка (скінченний, не порожній набір символів).
** <math>S</math>&nbsp;— скінченний, не порожній набір станів.
** <math>s_0</math>&nbsp;— початковий стан, елемент з <math>S</math> (в недетермінованих скінченних автоматах, <math>s_0</math> це набір початкових станів).
** <math>\delta</math>&nbsp;— функція переходу: <math>\delta: S \times \Sigma \rightarrow S</math>.
** <math>\omega</math> функція виходу.

Якщо функція виходу є функцією стану і вхідної абетки(<math>\omega: S \times \Sigma \rightarrow \Gamma</math>) таке визначення відповідає '''моделі Мілі''', і може бути виконана як [[автомат Мілі]]. Якщо функція виходу залежить тільки від стану (<math>\omega: S \rightarrow \Gamma</math>) тоді таке визначення відповідає '''моделі Мура''', і може бути виконана як [[автомат Мура]]. Скінченний автомат без функції виходу відомий як напівавтомат або як [[модель станів і переходів]].

=== Автоматні оператори ===
'''Означення:''' Відповідність, яка відображає вхідні ланцюжки '''a''' автомата '''M''' у вихідні ланцюжки '''w''' називають автоматним відображенням, а також автоматним оператором''' M'''. Якщо результат застосування цього оператора до ланцюжка '''a'''&nbsp;— вихідний ланцюжок '''w''',

то це позначають '''M(a) = w'''. Кількість символів у ланцюжку '''a''', як завжди, називають довжиною ланцюжка '''a''' та позначають '''|a|''' чи l'''(a)'''.

<u>Автоматне відображення має дві властивості:</u>

1. Ланцюжки '''a''' та '''w = M(a)''' мають однакову довжину: '''|a| = |w|''' (збереження довжини).

2. Якщо '''a = a1a2''' й '''M(a1a2) = w1w2''', де''' |a1| = |w1|''', то '''M(a1) = w1''', тобто образ відрізка довжиною l дорівнює відрізку образу з такою самою довжиною.

Властивість 2 означає, що автоматні оператори&nbsp;— це оператори без випередження, тобто такі, котрі, обробляючи ланцюжок зліва направо, «не підглядають уперед»: i-та буква вихідного ланцюжка залежить тільки від перших i букв вхідного ланцюжка. Приклад оператора з випередженням&nbsp;— той, який ланцюжку ''a = x1x2…xk'' ставить у відповідність ланцюжок ''xk…x1x2'', перша буква вихідного ланцюжка тут дорівнює останній букві вхідного ланцюжка. Зазначимо, що ці дві властивості&nbsp;— це не достатні умови автоматності відображення: існують відображення, які задовольняють умови 1 і 2, але не реалізовані в скінченному автоматі.

== Див. також ==
{{Multicol}}
* [[Теорія автоматів]]
* [[Абстрактного автомата граф]]
* [[Автомата таблиця]]
* [[Автомата пам'ять]]
* [[Автомата матриця переходів]]
* [[Регулярний вислів]]
* [[Аналіз автоматів]]
* [[Автоматів суперпозиція]]
* [[Автомат мікропрограмний]]
{{Multicol-break}}
* [[Автомат ініціальний]]
* [[Автомат лінійний]]
* [[Автомат вільний]]
* [[Автомат без пам'яті]]
* [[Автомат частковий]]
* [[Автомат операційний]]
* [[Автомат мінімальний]]
* [[Рідкий скінченний автомат]]
* [[Алгоритми мінімізації скінченних автоматів]]
{{Multicol-end}}

== Примітки ==
<references />
{{Недостатньо виносок|дата=вересень 2021}}

== Посилання ==
=== Українською ===
* {{книга
|автор        = [[Гаврилків Володимир Михайлович|Гаврилків В. М.]]
|назва        = Формальні мови та алгоритмічні моделі
|рік          = 2023
|видавництво  = Голіней
|місто        = {{Comment|І.-Ф. |Івано-Франківськ}}
|сторінок     = 180
|мова         = uk
}}

=== Іншими мовами ===
* {{Cinderella Book}}
* {{Роджерс.Теорія рекурсивних функцій}}
* ''Серебряков&nbsp;В. А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г.'' [http://trpl7.ru/t-books/TRYAP_BOOK_Details.htm Теория и реализация языков программирования] {{Webarchive|url=https://web.archive.org/web/20220103184855/http://trpl7.ru/t-books/TRYAP_BOOK_Details.htm |date=3 січня 2022 }}&nbsp;— М.: МЗ-Пресс, 2006 г., 2-е изд.&nbsp;— ISBN 5-94073-094-9
* Теория автоматов / ''Э.&nbsp;А.&nbsp;Якубайтис, В.&nbsp;О.&nbsp;Васюкевич, А.&nbsp;Ю.&nbsp;Гобземис, Н.&nbsp;Е.&nbsp;Зазнова, А.&nbsp;А.&nbsp;Курмит, А.&nbsp;А.&nbsp;Лоренц, А.&nbsp;Ф.&nbsp;Петренко, В.&nbsp;П.&nbsp;Чапенко'' // Теория вероятностей. Математическая статистика. Теоретическая кибернетика.&nbsp;— М.: ВИНИТИ, 1976.&nbsp;— Т. 13.&nbsp;— С. 109—188.&nbsp;— URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
* [http://robot-develop.org/archives/1440#more-1440 Применение конечных автоматов для решения задач автоматизации] {{Webarchive|url=https://web.archive.org/web/20210912132221/http://robot-develop.org/archives/1440#more-1440 |date=12 вересня 2021 }}
* ''[[Глушков Віктор Михайлович|Глушков В. М.]]'' Синтез цифровых автоматов.&nbsp;— М.: {{нп|Фізматліт|ГИФМЛ|ru|Физматлит}}, 1962.&nbsp;— 476 с.

{{Портал|Математика}}
{{Comp-sci-stub}}
{{Math-stub}}
{{Цифрова електроніка}}
{{ВП-портали|Програмування|Інформаційні технології}}

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